λ Tony’s blog λ

20 Intermediate Scala Exercises

I will be publishing answers to these exercises as well as the Revised Scala Exercises in the near future. In the meantime, see if you can tackle the exercises below. In almost all cases, the type signature is enough to derive what the implementation should be. In all other cases, the solution is as difficult to derive anyway, so consider it an equivalent achievement.

The source file below compiles, but is missing certain function implementations (where you see error("todo")). Enjoy and if you have questions, please feel free to post them

trait PartialType[T[_, _], A] {
  type Apply[B] = T[A, B]
  type Flip[B] = T[B, A]
}
 
trait Fluffy[F[_]] {
  def furry[A, B](f: A => B, fa: F[A]): F[B]
}
 
object Fluffy {
  // Exercise 1
  // Relative Difficulty: 1
  def ListFluffy: Fluffy[List] = error("todo")
 
  // Exercise 2
  // Relative Difficulty: 1
  def OptionFluffy: Fluffy[Option] = error("todo")
 
  // Exercise 3
  // Relative Difficulty: 1
  def StreamFluffy: Fluffy[Stream] = error("todo")
 
  // Exercise 4
  // Relative Difficulty: 1
  def ArrayFluffy: Fluffy[Array] = error("todo")
 
  // Exercise 5
  // Relative Difficulty: 5
  def Function1Fluffy[X]: Fluffy[PartialType[Function1, X]#Apply] =
    error("todo")
 
  // Exercise 6
  // Relative Difficulty: 6
  def EitherLeftFluffy[X]: Fluffy[PartialType[Either.LeftProjection, X]#Flip] =
    error("todo")
 
  // Exercise 7
  // Relative Difficulty: 4
  def EitherRightFluffy[X]: Fluffy[PartialType[Either.RightProjection, X]#Apply] =
    error("todo")
}
 
trait Misty[M[_]] extends Fluffy[M] {
  def banana[A, B](f: A => M[B], ma: M[A]): M[B]
 
  def unicorn[A](a: A): M[A]
 
  // Exercise 8
  // Relative Difficulty: 3
  // (use banana and/or unicorn)
  def furry[A, B](f: A => B, ma: M[A]) = error("todo")
}
 
object Misty {
  // Exercise 9
  // Relative Difficulty: 2
  def ListMisty: Misty[List] = error("todo")
 
  // Exercise 10
  // Relative Difficulty: 2
  def OptionMisty: Misty[Option] = error("todo")
 
  // Exercise 11
  // Relative Difficulty: 2
  def StreamMisty: Misty[Stream] = error("todo")
 
  // Exercise 12
  // Relative Difficulty: 2
  def ArrayMisty: Misty[Array] = error("todo")
 
  // Exercise 13
  // Relative Difficulty: 6
  def Function1Misty[X]: Misty[PartialType[Function1, X]#Apply] =
    error("todo")
 
  // Exercise 14
  // Relative Difficulty: 7
  def EitherLeftMisty[X]: Misty[PartialType[Either.LeftProjection, X]#Flip] =
    error("todo")
 
  // Exercise 15
  // Relative Difficulty: 5
  def EitherRightMisty[X]: Misty[PartialType[Either.RightProjection, X]#Apply] =
    error("todo")
 
  // Exercise 16
  // Relative Difficulty: 3
  def jellybean[M[_], A](ma: M[M[A]], m: Misty[M]): M[A] = error("todo")
 
  // Exercise 17
  // Relative Difficulty: 6
  def apple[M[_], A, B](ma: M[A], mf: M[A => B], m: Misty[M]): M[B] =
    error("todo")
 
  // Exercise 18
  // Relative Difficulty: 6
  def moppy[M[_], A, B](as: List[A], f: A => M[B], m: Misty[M]): M[List[B]] =
    error("todo")
}
 
object AdvancedFun {
  case class State[S, A](f: S => (S, A))
 
  // Exercise 19
  // Relative Difficulty: 9
  def StateFluffy[S]: Fluffy[PartialType[State, S]#Apply] = error("todo")
 
  // Exercise 20
  // Relative Difficulty: 10
  def StateMisty[S]: Misty[PartialType[State, S]#Apply] = error("todo")
}

This entry was posted on Wednesday, September 10th, 2008 at 1:36 pm and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

12 Responses to “20 Intermediate Scala Exercises”

German Buela Says:
September 12th, 2008 at 1:32 am
Boy, do you make my brain hurt.
Tony Morris Says:
September 12th, 2008 at 6:31 am
Good exercise

I am considering writing some “tests” for these functions to make their intention clear. Would this help? It will just add to the verbosity of the code though.
German Buela Says:
September 12th, 2008 at 1:46 pm
Please write them. I’m getting my implementations to compile but I’m not quite sure they all do the right thing.
Jeff Says:
September 12th, 2008 at 6:43 pm
These exercises are great. Thanks a lot Tony. Currently I’m stumped on test 13 and tests would help give me confidence that I am on the right track so far.
Tony Morris Says:
September 12th, 2008 at 9:35 pm
G’day Jeff, I’m working on some tests. Expect them soon!
German Buela Says:
September 15th, 2008 at 11:49 pm
I’m stumped on #13 as well, but I doubt the tests will help me go further :(… at least I’ll be able to validate the first twelve.
Tony Morris Says:
September 16th, 2008 at 3:35 pm
Hi Jeff and German,
Sorry I have just had got out of hospital following an ankle reconstruction. Can you at least get #13 to type check? e.g. Misty[PartialType[Function1, X]#Apply] { * have you written these type signatures? */}.

I’m not sure I’ll be able to get around to providing tests (I am currently high on morphine and things will be a bit difficult for a while :), but I can paraphrase them:

1. All instances of Fluffy must satisfy two rules:
1.1 For any value of x, furry(identity, x) == x
1.2. For any value x and any two functions f and g, furry(t => f(g(t)), x) == furry(f, furry(g, x))

2. All instances of Misty must satisfy three rules:
2.1 For any value x and any function f, banana(f, unicorn(x)) == f(x)
2.2 For any value x, banana(t => unicorn(t), x) == x
2.3 For any value x and any two functions f and g, banana(g, banana(f, x)) == banana(t => banana(g, f(a)), x)

I hope jellybean, apple and moppy are good enough given by their type signatures (actually apple can be written two different ways, but if you find one of those ways the other is almost immediately obvious anyway).

If you have any more questions or need some hints, then please feel free to drop me a line.
Jeff Says:
September 17th, 2008 at 7:37 pm
Hi Tony

I’m very grateful that you are bothering to respond to these comments while convalescing. The information you provided is useful for convincing myself of the correctness of my answers but I don’t know how to prove them. I think I have finally figured out exercise 13; I have at least got it to type check. I’m trying to figure out apple now.

Cheers,
Jeff
Tony Morris Says:
September 17th, 2008 at 8:04 pm
No worries Jeff, I hope you can pull through with these exercises. I’m assuming you are unaware of what some of the euphemisms stand for in which case, there will be a couple of surprises once you are done!

If your intuition says that your code meets the properties that I gave, then I suspect you are right. It would be difficult and more convoluted to not meet these properties in many cases.

Let me know if you get stuck again since I’d really like to see you get through.
Klaus Says:
September 24th, 2008 at 4:07 am
Hi Tony,

I got all exercises to compile. Do you have time to have a look? Can I post them here?
Tony Morris Says:
September 24th, 2008 at 6:11 am
Sure Klaus, I’ll be posting some answers soon.
Klaus Says:
September 25th, 2008 at 3:29 am
Hi Tony,

here are my solutions - base64 encoded:

dHJhaXQgUGFydGlhbFR5cGVbVFtfLCBfXSwgQV0gew0KICB0eXBlIEFwcGx5W0JdID0gVFtBLCBC
XQ0KICB0eXBlIEZsaXBbQl0gPSBUW0IsIEFdDQp9DQoNCnRyYWl0IEZsdWZmeVtGW19dXSB7DQog
IGRlZiBmdXJyeVtBLCBCXShmOiBBID0+IEIsIGZhOiBGW0FdKTogRltCXQ0KfQ0KDQpvYmplY3Qg
Rmx1ZmZ5IHsNCg0KICAvLyBFeGVyY2lzZSAxDQogIC8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDEN
CiAgZGVmIExpc3RGbHVmZnk6IEZsdWZmeVtMaXN0XSA9IG5ldyBGbHVmZnlbTGlzdF0gew0KICAg
IGRlZiBmdXJyeVtBLCBCXShmOiBBID0+IEIsIGZhOiBMaXN0W0FdKTogTGlzdFtCXSA9IGZhIG1h
cCBmDQogIH0NCg0KICAvLyBFeGVyY2lzZSAyDQogIC8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDEN
CiAgZGVmIE9wdGlvbkZsdWZmeTogRmx1ZmZ5W09wdGlvbl0gPSBuZXcgRmx1ZmZ5W09wdGlvbl0g
ew0KICAgIGRlZiBmdXJyeVtBLCBCXShmOiBBID0+IEIsIGZhOiBPcHRpb25bQV0pOiBPcHRpb25b
Ql0gPSBmYSBtYXAgZg0KICB9DQoNCiAgLy8gRXhlcmNpc2UgMw0KICAvLyBSZWxhdGl2ZSBEaWZm
aWN1bHR5OiAxDQogIGRlZiBTdHJlYW1GbHVmZnk6IEZsdWZmeVtTdHJlYW1dID0gbmV3IEZsdWZm
eVtTdHJlYW1dIHsNCiAgICBkZWYgZnVycnlbQSwgQl0oZjogQSA9PiBCLCBmYTogU3RyZWFtW0Fd
KTogU3RyZWFtW0JdID0gZmEgbWFwIGYNCiAgfQ0KDQogIC8vIEV4ZXJjaXNlIDQNCiAgLy8gUmVs
YXRpdmUgRGlmZmljdWx0eTogMQ0KICBkZWYgQXJyYXlGbHVmZnk6IEZsdWZmeVtBcnJheV0gPSBu
ZXcgRmx1ZmZ5W0FycmF5XSB7DQogICAgZGVmIGZ1cnJ5W0EsIEJdKGY6IEEgPT4gQiwgZmE6IEFy
cmF5W0FdKTogQXJyYXlbQl0gPSBmYSBtYXAgZg0KICB9DQoNCiAgLy8gRXhlcmNpc2UgNQ0KICAv
LyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA1DQogIGRlZiBGdW5jdGlvbjFGbHVmZnlbWF06IEZsdWZm
eVtQYXJ0aWFsVHlwZVtGdW5jdGlvbjEsIFhdI0FwcGx5XSA9IG5ldyBGbHVmZnlbUGFydGlhbFR5
cGVbRnVuY3Rpb24xLCBYXSNBcHBseV0gew0KICAgIGRlZiBmdXJyeVtBLCBCXShmOiBBID0+IEIs
IGZhOiBGdW5jdGlvbjFbWCwgQV0pID0gZiBjb21wb3NlIGZhDQogIH0NCg0KICAvLyBFeGVyY2lz
ZSA2DQogIC8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDYNCiAgZGVmIEVpdGhlckxlZnRGbHVmZnlb
WF06IEZsdWZmeVtQYXJ0aWFsVHlwZVtFaXRoZXIuTGVmdFByb2plY3Rpb24sIFhdI0ZsaXBdID0g
bmV3IEZsdWZmeVtQYXJ0aWFsVHlwZVtFaXRoZXIuTGVmdFByb2plY3Rpb24sIFhdI0ZsaXBdIHsN
CiAgICBkZWYgZnVycnlbQSwgQl0oZjogQSA9PiBCLCBmYTogRWl0aGVyLkxlZnRQcm9qZWN0aW9u
W0EsIFhdKSA9IGZhIG1hcCBmIGxlZnQNCiAgfQ0KDQogIC8vIEV4ZXJjaXNlIDcNCiAgLy8gUmVs
YXRpdmUgRGlmZmljdWx0eTogNA0KICBkZWYgRWl0aGVyUmlnaHRGbHVmZnlbWF06IEZsdWZmeVtQ
YXJ0aWFsVHlwZVtFaXRoZXIuUmlnaHRQcm9qZWN0aW9uLCBYXSNBcHBseV0gPSBuZXcgRmx1ZmZ5
W1BhcnRpYWxUeXBlW0VpdGhlci5SaWdodFByb2plY3Rpb24sIFhdI0FwcGx5XSB7DQogICAgZGVm
IGZ1cnJ5W0EsIEJdKGY6IEEgPT4gQiwgZmE6IEVpdGhlci5SaWdodFByb2plY3Rpb25bWCwgQV0p
ID0gZmEgbWFwIGYgcmlnaHQNCiAgfQ0KDQp9DQoNCnRyYWl0IE1pc3R5W01bX11dIGV4dGVuZHMg
Rmx1ZmZ5W01dIHsNCiAgZGVmIGJhbmFuYVtBLCBCXShmOiBBID0+IE1bQl0sIG1hOiBNW0FdKTog
TVtCXQ0KDQogIGRlZiB1bmljb3JuW0FdKGE6IEEpOiBNW0FdDQoNCiAgLy8gRXhlcmNpc2UgOA0K
ICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAzDQogIC8vICh1c2UgYmFuYW5hIGFuZC9vciB1bmlj
b3JuKQ0KICBkZWYgZnVycnlbQSwgQl0oZjogQSA9PiBCLCBtYTogTVtBXSkgPSBiYW5hbmEoKGE6
IEEpID0+IHVuaWNvcm4oZihhKSksIG1hKQ0KfQ0KDQpvYmplY3QgTWlzdHkgew0KICAvLyBFeGVy
Y2lzZSA5DQogIC8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDINCiAgZGVmIExpc3RNaXN0eTogTWlz
dHlbTGlzdF0gPSBuZXcgTWlzdHlbTGlzdF0gew0KICAgIGRlZiB1bmljb3JuW0FdKGE6IEEpID0g
TGlzdChhKQ0KICAgIGRlZiBiYW5hbmFbQSwgQl0oZjogQSA9PiBMaXN0W0JdLCBtYTogTGlzdFtB
XSkgPSBtYSBmbGF0TWFwIGYNCiAgfQ0KDQogIC8vIEV4ZXJjaXNlIDEwDQogIC8vIFJlbGF0aXZl
IERpZmZpY3VsdHk6IDINCiAgZGVmIE9wdGlvbk1pc3R5OiBNaXN0eVtPcHRpb25dID0gbmV3IE1p
c3R5W09wdGlvbl0gew0KICAgIGRlZiB1bmljb3JuW0FdKGE6IEEpID0gU29tZShhKQ0KICAgIGRl
ZiBiYW5hbmFbQSwgQl0oZjogQSA9PiBPcHRpb25bQl0sIG1hOiBPcHRpb25bQV0pID0gbWEgZmxh
dE1hcCBmDQogIH0NCg0KICAvLyBFeGVyY2lzZSAxMQ0KICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5
OiAyDQogIGRlZiBTdHJlYW1NaXN0eTogTWlzdHlbU3RyZWFtXSA9IG5ldyBNaXN0eVtTdHJlYW1d
IHsNCiAgICBkZWYgdW5pY29ybltBXShhOiBBKSA9IFN0cmVhbShhKQ0KICAgIGRlZiBiYW5hbmFb
QSwgQl0oZjogQSA9PiBTdHJlYW1bQl0sIG1hOiBTdHJlYW1bQV0pID0gbWEgZmxhdE1hcCBmDQog
IH0NCg0KICAvLyBFeGVyY2lzZSAxMg0KICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAyDQogIGRl
ZiBBcnJheU1pc3R5OiBNaXN0eVtBcnJheV0gPSBuZXcgTWlzdHlbQXJyYXldIHsNCiAgICBkZWYg
dW5pY29ybltBXShhOiBBKSA9IEFycmF5Lm1ha2UoMSwgYSkNCiAgICBkZWYgYmFuYW5hW0EsIEJd
KGY6IEEgPT4gQXJyYXlbQl0sIG1hOiBBcnJheVtBXSkgPSBtYSBmbGF0TWFwIGYNCiAgfQ0KDQog
IC8vIEV4ZXJjaXNlIDEzDQogIC8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDYNCiAgZGVmIEZ1bmN0
aW9uMU1pc3R5W1hdOiBNaXN0eVtQYXJ0aWFsVHlwZVtGdW5jdGlvbjEsIFhdI0FwcGx5XSA9IG5l
dyBNaXN0eVtQYXJ0aWFsVHlwZVtGdW5jdGlvbjEsIFhdI0FwcGx5XSB7DQogICAgZGVmIHVuaWNv
cm5bQV0oYTogQSkgPSAoeDogWCkgPT4gYQ0KICAgIGRlZiBiYW5hbmFbQSwgQl0oZjogQSA9PiBG
dW5jdGlvbjFbWCwgQl0sIG1hOiBGdW5jdGlvbjFbWCwgQV0pID0gKHg6IFgpID0+IGYobWEoeCkp
KHgpDQogIH0NCg0KICAvLyBFeGVyY2lzZSAxNA0KICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA3
DQogIGRlZiBFaXRoZXJMZWZ0TWlzdHlbWF06IE1pc3R5W1BhcnRpYWxUeXBlW0VpdGhlci5MZWZ0
UHJvamVjdGlvbiwgWF0jRmxpcF0gPSBuZXcgTWlzdHlbUGFydGlhbFR5cGVbRWl0aGVyLkxlZnRQ
cm9qZWN0aW9uLCBYXSNGbGlwXSB7DQogICAgZGVmIHVuaWNvcm5bQV0oYTogQSkgPSBMZWZ0KGEp
IGxlZnQNCiAgICBkZWYgYmFuYW5hW0EsIEJdKGY6IEEgPT4gRWl0aGVyLkxlZnRQcm9qZWN0aW9u
W0IsIFhdLCBtYTogRWl0aGVyLkxlZnRQcm9qZWN0aW9uW0EsIFhdKSA9IG1hIGZsYXRNYXAgKGYo
XykgbWFwIGlkZW50aXR5W0JdKSBsZWZ0DQogIH0NCg0KICAvLyBFeGVyY2lzZSAxNQ0KICAvLyBS
ZWxhdGl2ZSBEaWZmaWN1bHR5OiA1DQogIGRlZiBFaXRoZXJSaWdodE1pc3R5W1hdOiBNaXN0eVtQ
YXJ0aWFsVHlwZVtFaXRoZXIuUmlnaHRQcm9qZWN0aW9uLCBYXSNBcHBseV0gPSBuZXcgTWlzdHlb
UGFydGlhbFR5cGVbRWl0aGVyLlJpZ2h0UHJvamVjdGlvbiwgWF0jQXBwbHldIHsNCiAgICBkZWYg
dW5pY29ybltBXShhOiBBKSA9IFJpZ2h0KGEpIHJpZ2h0DQogICAgZGVmIGJhbmFuYVtBLCBCXShm
OiBBID0+IEVpdGhlci5SaWdodFByb2plY3Rpb25bWCwgQl0sIG1hOiBFaXRoZXIuUmlnaHRQcm9q
ZWN0aW9uW1gsIEFdKSA9IG1hIGZsYXRNYXAgKGYoXykgbWFwIGlkZW50aXR5W0JdKSByaWdodA0K
ICB9DQoNCiAgLy8gRXhlcmNpc2UgMTYNCiAgLy8gUmVsYXRpdmUgRGlmZmljdWx0eTogMw0KICBk
ZWYgamVsbHliZWFuW01bX10sIEFdKG1hOiBNW01bQV1dLCBtOiBNaXN0eVtNXSk6IE1bQV0gPSBt
LmJhbmFuYShpZGVudGl0eVtNW0FdXSwgbWEpDQoNCiAgLy8gRXhlcmNpc2UgMTcNCiAgLy8gUmVs
YXRpdmUgRGlmZmljdWx0eTogNg0KICBkZWYgYXBwbGVbTVtfXSwgQSwgQl0obWE6IE1bQV0sIG1m
OiBNW0EgPT4gQl0sIG06IE1pc3R5W01dKTogTVtCXSA9DQogICAgbS5iYW5hbmEoKGE6IEEpID0+
IG0uZnVycnkoKGY6IEEgPT4gQikgPT4gZihhKSwgbWYpLCBtYSkNCg0KICAvLyBFeGVyY2lzZSAx
OA0KICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA2DQogIGRlZiBtb3BweVtNW19dLCBBLCBCXShh
czogTGlzdFtBXSwgZjogQSA9PiBNW0JdLCBtOiBNaXN0eVtNXSk6IE1bTGlzdFtCXV0gPSB7DQog
ICAgdmFsIGxtYjogTGlzdFtNW0JdXSA9IGFzIG1hcCBmDQogICAgdmFsIGU6ICAgTVtMaXN0W0Jd
XSA9IG0udW5pY29ybltMaXN0W0JdXShOaWwpDQoNCiAgICBsbWIuZm9sZFJpZ2h0KGUpKChtYjog
TVtCXSwgbWxiOiBNW0xpc3RbQl1dKSA9Pg0KICAgICAgbS5iYW5hbmEoKGI6IEIpID0+IG0uZnVy
cnkoKGJzOiBMaXN0W0JdKSA9PiBiIDo6IGJzLCBtbGIpLCBtYikpDQogIH0NCn0NCg0Kb2JqZWN0
IEFkdmFuY2VkRnVuIHsNCiAgY2FzZSBjbGFzcyBTdGF0ZVtTLCBBXShmOiBTID0+IChTLCBBKSkN
Cg0KICAvLyBFeGVyY2lzZSAxOQ0KICAvLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA5DQogIGRlZiBT
dGF0ZUZsdWZmeVtTXTogRmx1ZmZ5W1BhcnRpYWxUeXBlW1N0YXRlLCBTXSNBcHBseV0gPSBuZXcg
Rmx1ZmZ5W1BhcnRpYWxUeXBlW1N0YXRlLCBTXSNBcHBseV0gew0KICAgIGRlZiBmdXJyeVtBLCBC
XShmOiBBID0+IEIsIGZhOiBTdGF0ZVtTLCBBXSkgPQ0KICAgICAgU3RhdGUoKHM6IFMpID0+IHsN
CiAgICAgICAgZmEuZihzKSBtYXRjaCB7DQogICAgICAgICAgY2FzZSAobnMsIGEpID0+IChucywg
ZihhKSkNCiAgICAgICAgfQ0KICAgICAgfSkNCiAgfQ0KDQogIC8vIEV4ZXJjaXNlIDIwDQogIC8v
IFJlbGF0aXZlIERpZmZpY3VsdHk6IDEwDQogIGRlZiBTdGF0ZU1pc3R5W1NdOiBNaXN0eVtQYXJ0
aWFsVHlwZVtTdGF0ZSwgU10jQXBwbHldID0gbmV3IE1pc3R5W1BhcnRpYWxUeXBlW1N0YXRlLCBT
XSNBcHBseV0gew0KICAgIGRlZiB1bmljb3JuW0FdKGE6IEEpOiBTdGF0ZVtTLCBBXSA9IFN0YXRl
KChzOiBTKSA9PiAocywgYSkpDQogICAgZGVmIGJhbmFuYVtBLCBCXShmOiBBID0+IFN0YXRlW1Ms
IEJdLCBtYTogU3RhdGVbUywgQV0pOiBTdGF0ZVtTLCBCXSA9DQogICAgICBTdGF0ZSgoczogUykg
PT4gew0KICAgICAgICBtYS5mKHMpIG1hdGNoIHsNCiAgICAgICAgICBjYXNlIChucywgYSkgPT4g
ZihhKS5mKG5zKQ0KICAgICAgICB9DQogICAgICB9KQ0KICB9DQp9DQo=

20 Intermediate Scala Exercises

12 Responses to “20 Intermediate Scala Exercises”

Leave a Reply