λ Tony’s blog λ

Revised Scala Exercises

Without the rules as per last time, I have rewritten the Scala exercises to be closer to the Haskell revision. Enjoy

(And yes, I will get around to giving you all feedback (you should also see my email inbox) — just hang in there!).

sealed trait List[+A] {
  override def toString = {
    def toScalaList(t: List[A]): scala.List[A] = t match {
      case Empty => Nil
      case Cons(h, t) => h :: toScalaList(t)
    }
    toScalaList(this).toString
  }
}
final case object Empty extends List[Nothing]
final case class Cons[A](h: A, t: List[A]) extends List[A]
 
object List {
  def foldRight[A, B](as: List[A], b: B, f: (A, B) => B): B = as match {
    case Empty => b
    case Cons(h, t) => f(h, foldRight(t, b, f))
  }
 
  def foldLeft[A, B](as: List[A], b: B, f: (B, A) => B): B = as match {
    case Empty => b
    case Cons(h, t) => foldLeft(t, f(b, h), f)
  }
 
  def reduceRight[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceRight on empty list")
    case Cons(h, t) => foldRight(t, h, f)
  }
 
  def reduceLeft[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceLeft on empty list")
    case Cons(h, t) => foldLeft(t, h, f)
  }
 
  def unfold[A, B](b: B, f: B => Option[(A, B)]): List[A] = f(b) match {
    case Some((a, b)) => Cons(a, unfold(b, f))
    case scala.None => Empty
  }
}
 
sealed trait Natural {
  override def toString = {
    def toInt(n: Natural): Int = n match {
      case Zero => 0
      case Succ(x) => 1 + toInt(x)
    }
    toInt(this).toString
  }
}
final case object Zero extends Natural
final case class Succ(c: Natural) extends Natural
 
object Exercises {
 
// Exercise 1
// Relative Difficulty: 1
// Correctness: 2.0 marks
// Performance: 0.5 mark
// Elegance: 0.5 marks
// Total: 3
def add(x: Natural, y: Natural): Natural = error("todo")
 
// Exercise 2
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def sum(is: List[Int]): Int = error("todo")
 
// Exercise 3
// Relative Difficulty: 2
// Correctness: 2.5 marks
// Performance: 1 mark
// Elegance: 0.5 marks
// Total: 4
def length[A](as: List[A]): Int = error("todo")
 
// Exercise 4
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.0 mark
// Elegance: 1.5 marks
// Total: 7
def map[A, B](as: List[A], f: A => B): List[B] = error("todo")
 
// Exercise 5
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def filter[A](as: List[A], f: A => Boolean): List[A] = error("todo")
 
// Exercise 6
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def append[A](x: List[A], y: List[A]): List[A] = error("todo")
 
// Exercise 7
// Relative Difficulty: 5
// Correctness: 4.5 marks
// Performance: 1.5 marks
// Elegance: 1 mark
// Total: 7
def flatten[A](as: List[List[A]]): List[A] = error("todo")
 
// Exercise 8
// Relative Difficulty: 7
// Correctness: 5.0 marks
// Performance: 1.5 marks
// Elegance: 1.5 mark
// Total: 8
def flatMap[A, B](as: List[A], f: A => List[B]): List[B] = error("todo")
 
// Exercise 9
// Relative Difficulty: 8
// Correctness: 3.5 marks
// Performance: 3.0 marks
// Elegance: 2.5 marks
// Total: 9
def maximum(is: List[Int]): Int = error("todo")
 
// Exercise 10
// Relative Difficulty: 10
// Correctness: 5.0 marks
// Performance: 2.5 marks
// Elegance: 2.5 marks
// Total: 10
def reverse[A](as: List[A]): List[A] = error("todo")
}

This entry was posted on Tuesday, July 29th, 2008 at 10:08 am 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.

7 Responses to “Revised Scala Exercises”

Jeff Says:
July 29th, 2008 at 6:47 pm
Thanks Tony

These exercises are a big improvement and really improved my understanding. I finally figured out how to stop all my methods depending on reverse.

c2VhbGVkIHRyYWl0IExpc3RbK0FdIHsNCiAgb3ZlcnJpZGUgZGVmIHRvU3RyaW5nID0gew0KICAg
IGRlZiB0b1NjYWxhTGlzdCh0OiBMaXN0W0FdKTogc2NhbGEuTGlzdFtBXSA9IHQgbWF0Y2ggew0K
ICAgICAgY2FzZSBFbXB0eSA9PiBOaWwNCiAgICAgIGNhc2UgQ29ucyhoLCB0KSA9PiBoIDo6IHRv
U2NhbGFMaXN0KHQpDQogICAgfQ0KICAgIHRvU2NhbGFMaXN0KHRoaXMpLnRvU3RyaW5nDQogIH0N
Cn0NCmZpbmFsIGNhc2Ugb2JqZWN0IEVtcHR5IGV4dGVuZHMgTGlzdFtOb3RoaW5nXQ0KZmluYWwg
Y2FzZSBjbGFzcyBDb25zW0FdKGg6IEEsIHQ6IExpc3RbQV0pIGV4dGVuZHMgTGlzdFtBXQ0KDQpv
YmplY3QgTGlzdCB7DQogIGRlZiBmb2xkUmlnaHRbQSwgQl0oYXM6IExpc3RbQV0sIGI6IEIsIGY6
IChBLCBCKSA9PiBCKTogQiA9IGFzIG1hdGNoIHsNCiAgICBjYXNlIEVtcHR5ID0+IGINCiAgICBj
YXNlIENvbnMoaCwgdCkgPT4gZihoLCBmb2xkUmlnaHQodCwgYiwgZikpDQogIH0NCg0KICBkZWYg
Zm9sZExlZnRbQSwgQl0oYXM6IExpc3RbQV0sIGI6IEIsIGY6IChCLCBBKSA9PiBCKTogQiA9IGFz
IG1hdGNoIHsNCiAgICBjYXNlIEVtcHR5ID0+IGINCiAgICBjYXNlIENvbnMoaCwgdCkgPT4gZm9s
ZExlZnQodCwgZihiLCBoKSwgZikNCiAgfQ0KDQogIGRlZiByZWR1Y2VSaWdodFtBXShhczogTGlz
dFtBXSwgZjogKEEsIEEpID0+IEEpOiBBID0gYXMgbWF0Y2ggew0KICAgIGNhc2UgRW1wdHkgPT4g
ZXJyb3IoImJ6enQuIHJlZHVjZVJpZ2h0IG9uIGVtcHR5IGxpc3QiKQ0KICAgIGNhc2UgQ29ucyho
LCB0KSA9PiBmb2xkUmlnaHQodCwgaCwgZikNCiAgfQ0KDQogIGRlZiByZWR1Y2VMZWZ0W0FdKGFz
OiBMaXN0W0FdLCBmOiAoQSwgQSkgPT4gQSk6IEEgPSBhcyBtYXRjaCB7DQogICAgY2FzZSBFbXB0
eSA9PiBlcnJvcigiYnp6dC4gcmVkdWNlTGVmdCBvbiBlbXB0eSBsaXN0IikNCiAgICBjYXNlIENv
bnMoaCwgdCkgPT4gZm9sZExlZnQodCwgaCwgZikNCiAgfQ0KDQogIGRlZiB1bmZvbGRbQSwgQl0o
YjogQiwgZjogQiA9PiBPcHRpb25bKEEsIEIpXSk6IExpc3RbQV0gPSBmKGIpIG1hdGNoIHsNCiAg
ICBjYXNlIFNvbWUoKGEsIGIpKSA9PiBDb25zKGEsIHVuZm9sZChiLCBmKSkNCiAgICBjYXNlIHNj
YWxhLk5vbmUgPT4gRW1wdHkNCiAgfQ0KfQ0KDQpzZWFsZWQgdHJhaXQgTmF0dXJhbCB7DQogIG92
ZXJyaWRlIGRlZiB0b1N0cmluZyA9IHsNCiAgICBkZWYgdG9JbnQobjogTmF0dXJhbCk6IEludCA9
IG4gbWF0Y2ggew0KICAgICAgY2FzZSBaZXJvID0+IDANCiAgICAgIGNhc2UgU3VjYyh4KSA9PiAx
ICsgdG9JbnQoeCkNCiAgICB9DQogICAgdG9JbnQodGhpcykudG9TdHJpbmcNCiAgfQ0KfQ0KZmlu
YWwgY2FzZSBvYmplY3QgWmVybyBleHRlbmRzIE5hdHVyYWwNCmZpbmFsIGNhc2UgY2xhc3MgU3Vj
YyhjOiBOYXR1cmFsKSBleHRlbmRzIE5hdHVyYWwNCg0Kb2JqZWN0IEV4ZXJjaXNlcyB7DQoNCi8v
IEV4ZXJjaXNlIDENCi8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDENCi8vIENvcnJlY3RuZXNzOiAy
LjAgbWFya3MNCi8vIFBlcmZvcm1hbmNlOiAwLjUgbWFyaw0KLy8gRWxlZ2FuY2U6IDAuNSBtYXJr
cw0KLy8gVG90YWw6IDMNCmRlZiBhZGQoeDogTmF0dXJhbCwgeTogTmF0dXJhbCk6IE5hdHVyYWwg
PSB7DQogIHggbWF0Y2ggew0KICAgIGNhc2UgWmVybyA9PiB5DQogICAgY2FzZSBTdWNjKHApID0+
IGFkZChwLCBTdWNjKHkpKQ0KICB9DQp9DQoNCi8vIEV4ZXJjaXNlIDINCi8vIFJlbGF0aXZlIERp
ZmZpY3VsdHk6IDINCi8vIENvcnJlY3RuZXNzOiAyLjUgbWFya3MNCi8vIFBlcmZvcm1hbmNlOiAx
IG1hcmsNCi8vIEVsZWdhbmNlOiAwLjUgbWFya3MNCi8vIFRvdGFsOiA0DQpkZWYgc3VtKGlzOiBM
aXN0W0ludF0pOiBJbnQgPSBMaXN0LmZvbGRMZWZ0KGlzLCAwLCAoKGE6SW50LCBiOkludCkgPT4g
YSArIGIpKQ0KDQovLyBFeGVyY2lzZSAzDQovLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAyDQovLyBD
b3JyZWN0bmVzczogMi41IG1hcmtzDQovLyBQZXJmb3JtYW5jZTogMSBtYXJrDQovLyBFbGVnYW5j
ZTogMC41IG1hcmtzDQovLyBUb3RhbDogNA0KZGVmIGxlbmd0aFtBXShhczogTGlzdFtBXSk6IElu
dCA9IExpc3QuZm9sZExlZnQoYXMsIDAsICgoYTpJbnQsIGI6QSkgPT4gYSArIDEpKQ0KDQovLyBF
eGVyY2lzZSA0DQovLyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiA1DQovLyBDb3JyZWN0bmVzczogNC41
IG1hcmtzDQovLyBQZXJmb3JtYW5jZTogMS4wIG1hcmsNCi8vIEVsZWdhbmNlOiAxLjUgbWFya3MN
Ci8vIFRvdGFsOiA3DQpkZWYgbWFwW0EsIEJdKGFzOiBMaXN0W0FdLCBmOiBBID0+IEIpOiBMaXN0
W0JdID0NCiAgICAgIExpc3QuZm9sZFJpZ2h0KGFzLCBFbXB0eSwgKChwOkEsIHE6TGlzdFtCXSkg
PT4gQ29ucyhmKHApLCBxKSkpDQoNCi8vIEV4ZXJjaXNlIDUNCi8vIFJlbGF0aXZlIERpZmZpY3Vs
dHk6IDUNCi8vIENvcnJlY3RuZXNzOiA0LjUgbWFya3MNCi8vIFBlcmZvcm1hbmNlOiAxLjUgbWFy
a3MNCi8vIEVsZWdhbmNlOiAxIG1hcmsNCi8vIFRvdGFsOiA3DQpkZWYgZmlsdGVyW0FdKGFzOiBM
aXN0W0FdLCBmOiBBID0+IEJvb2xlYW4pOiBMaXN0W0FdID0NCiAgICAgIExpc3QuZm9sZFJpZ2h0
KGFzLCBFbXB0eSwgeyAodDpBLCB5Okxpc3RbQV0pID0+DQogICAgICAgIGlmIChmKHQpKSBDb25z
KHQsIHkpDQogICAgICAgIGVsc2UgeQ0KICAgICAgfSkNCg0KLy8gRXhlcmNpc2UgNg0KLy8gUmVs
YXRpdmUgRGlmZmljdWx0eTogNQ0KLy8gQ29ycmVjdG5lc3M6IDQuNSBtYXJrcw0KLy8gUGVyZm9y
bWFuY2U6IDEuNSBtYXJrcw0KLy8gRWxlZ2FuY2U6IDEgbWFyaw0KLy8gVG90YWw6IDcNCmRlZiBh
cHBlbmRbQV0oeDogTGlzdFtBXSwgeTogTGlzdFtBXSk6IExpc3RbQV0gPQ0KICAgICAgTGlzdC5m
b2xkUmlnaHQoeCwgeSwgKChwOkEsIHE6TGlzdFtBXSkgPT4gQ29ucyhwLCBxKSkpDQoNCi8vIEV4
ZXJjaXNlIDcNCi8vIFJlbGF0aXZlIERpZmZpY3VsdHk6IDUNCi8vIENvcnJlY3RuZXNzOiA0LjUg
bWFya3MNCi8vIFBlcmZvcm1hbmNlOiAxLjUgbWFya3MNCi8vIEVsZWdhbmNlOiAxIG1hcmsNCi8v
IFRvdGFsOiA3DQpkZWYgZmxhdHRlbltBXShhczogTGlzdFtMaXN0W0FdXSk6IExpc3RbQV0gPQ0K
ICAgICAgTGlzdC5mb2xkUmlnaHQoYXMsIEVtcHR5LCAoKHA6TGlzdFtBXSwgcTpMaXN0W0FdKSA9
PiBhcHBlbmQocCwgcSkpKQ0KDQovLyBFeGVyY2lzZSA4DQovLyBSZWxhdGl2ZSBEaWZmaWN1bHR5
OiA3DQovLyBDb3JyZWN0bmVzczogNS4wIG1hcmtzDQovLyBQZXJmb3JtYW5jZTogMS41IG1hcmtz
DQovLyBFbGVnYW5jZTogMS41IG1hcmsNCi8vIFRvdGFsOiA4DQpkZWYgZmxhdE1hcFtBLCBCXShh
czogTGlzdFtBXSwgZjogQSA9PiBMaXN0W0JdKTogTGlzdFtCXSA9IGZsYXR0ZW4obWFwKGFzLCBm
KSkNCg0KLy8gRXhlcmNpc2UgOQ0KLy8gUmVsYXRpdmUgRGlmZmljdWx0eTogOA0KLy8gQ29ycmVj
dG5lc3M6IDMuNSBtYXJrcw0KLy8gUGVyZm9ybWFuY2U6IDMuMCBtYXJrcw0KLy8gRWxlZ2FuY2U6
IDIuNSBtYXJrcw0KLy8gVG90YWw6IDkNCmRlZiBtYXhpbXVtKGlzOiBMaXN0W0ludF0pOiBJbnQg
PSB7DQogICAgaXMgbWF0Y2ggew0KICAgICAgY2FzZSBFbXB0eSA9PiB0aHJvdyBuZXcgSWxsZWdh
bEFyZ3VtZW50RXhjZXB0aW9uKCJDYW4ndCBjYWxjdWxhdGUgbWF4aW11bSBvZiBlbXB0eSBsaXN0
LiIpDQogICAgICBjYXNlIF8gPT4gTGlzdC5yZWR1Y2VMZWZ0KGlzLCAoKGE6SW50LCBiOkludCkg
PT4gaWYgKGEgPiBiKSBhIGVsc2UgYikpDQogICAgfQ0KICB9DQoNCi8vIEV4ZXJjaXNlIDEwDQov
LyBSZWxhdGl2ZSBEaWZmaWN1bHR5OiAxMA0KLy8gQ29ycmVjdG5lc3M6IDUuMCBtYXJrcw0KLy8g
UGVyZm9ybWFuY2U6IDIuNSBtYXJrcw0KLy8gRWxlZ2FuY2U6IDIuNSBtYXJrcw0KLy8gVG90YWw6
IDEwDQpkZWYgcmV2ZXJzZVtBXShhczogTGlzdFtBXSk6IExpc3RbQV0gPQ0KICAgICAgTGlzdC5m
b2xkTGVmdChhcywgRW1wdHksICgocmV2Okxpc3RbQV0sIHQ6QSkgPT4gQ29ucyh0LCByZXYpKSkN
Cn0NCg==
Ben Hutchison Says:
September 2nd, 2008 at 10:00 pm
Hi Tony,

My question was about the pred() function/case (or lack thereof), which appears in the previous Scala and Haskell versions, but not in this one.

Why is that?
Tony Morris Says:
September 2nd, 2008 at 10:48 pm
Here is a message from Ben, which for the third time, failed to show after I Approved it in the Wordpress admin panel sigh.

Hi Tony,

My question was about the pred() function/case (or lack thereof), which appears in the previous Scala and Haskell versions, but not in this one.

Why is that?

Hello Ben, I didn’t write the pred/succ functions because they are a bit of a red herring. They are not required to implement any of the exercises.
λ Tony’s blog λ » Blog Archive » 20 Intermediate Scala Exercises Says:
September 10th, 2008 at 1:36 pm
[...] 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 [...]
Stefan Wagner Says:
October 4th, 2008 at 12:55 pm
Why do I get this error:

sealed trait List[+A] { | override def toString = { | def toScalaList(t: List[A]): scala.List[A] = t match { | case Empty => Nil | case Cons(h, t) => h :: toScalaList(t) | } | toScalaList(this).toString | } | } :7: error: not found: value Empty case Empty => Nil ^ :8: error: not found: value Cons case Cons(h, t) => h :: toScalaList(t) ^ :8: error: not found: value h case Cons(h, t) => h :: toScalaList(t)
And why is it List[+A], and not just List[A]?

I used scala-2.7.1-final to try this out.
Karri-Pekka Laakso Says:
October 14th, 2008 at 2:45 am
Stefan: I used the same version and couldn’t compile it inside the interpreter. However, I pasted all of the code into one file, compiled it with scalac and launched the interpreter with
```
scala -cp .
```
=> Works.
Tony Morris Says:
October 14th, 2008 at 7:10 am
Hi Stefan, sorry for the late reply. If you’re using the Scala REPL, then the definition of Empty comes after the declaration of List, so it fails.

The [+A] denotes covariance in the type parameter A. So if T is a subtype of U, then List[T] is a subtype of List[U]. In contrast to Java, where all type parameters are invariant. For example, a List<String> is not a List<CharSequence> even though a String is a CharSequence.

Revised Scala Exercises

7 Responses to “Revised Scala Exercises”

Leave a Reply