List methods:

  • How to create the methods like take, drop, reverse, append, etc. on Lists.

  • Implementation of mergesort.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def msort(list: List[Int]): List[Int] = {
  val mid = list.length / 2
  if (mid == 0) list
  else {
    def merge(xs: List[Int], ys: List[Int]): List[Int] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x::xs1, y::ys1) =>
        if (x < y) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
    val (ys, zs) = list.splitAt(mid)
    merge(msort(ys), msort(zs))
  }
}

Tuple class:

The Tuple class is implemented using TupleN class, where N is the number of elements in the tuple:

1
2
3

case class Tuple2[T1, T2](_1: +T1, _2: +T2) {
    override def toString = "(" + _1 + "," + _2 + ")"
}

Therefore, a tuple creates fields with names \_1, \_2, etc.

Implicit Parameters

One way is to parameterize the type, which would not work unless we pass a ordering function as well since not every type has < defined:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def msort[T](list: List[T])(lt: (T, T) => Boolean): List[T] = {
  val mid = list.length / 2
  if (mid == 0) list
  else {
    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x::xs1, y::ys1) =>
        if (lt(x,y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
    val (ys, zs) = list.splitAt(mid)
    merge(msort(ys)(lt), msort(zs)(lt))
  }
}

And then we can go ahead and use Ordering trait so that the class T using msort has to have lt method defined for it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import math.Ordering

def msort[T](list: List[T])(ord: Ordering): List[T] = {
  val mid = list.length / 2
  if (mid == 0) list
  else {
    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x::xs1, y::ys1) =>
        if (ord.lt(x,y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
    val (ys, zs) = list.splitAt(mid)
    merge(msort(ys)(ord), msort(zs)(ord))
  }
}

msort(List[Int])(Ordering.Int)

Implicit Ordering:

We can also use the implicit keyword which will implicitly pass the ordering operator based on the given type:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import math.Ordering

def msort[T](list: List[T])(implicit ord: Ordering): List[T] = {
  val mid = list.length / 2
  if (mid == 0) list
  else {
    def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
      case (Nil, ys) => ys
      case (xs, Nil) => xs
      case (x::xs1, y::ys1) =>
        if (ord.lt(x,y)) x :: merge(xs1, ys)
        else y :: merge(xs, ys1)
    }
    val (ys, zs) = list.splitAt(mid)
    merge(msort(ys), msort(zs)) // the `ord` param is visible at this point
  }
}

msort(List[Int])  // defined in the companion object

For this to work, the compiler looks at any definition which - is marked implicit - has a compatible type T - is visible at the point of the function call, or is defined at the companion object.

Higher order functions:

  • I already used these in the previous section’s assignment.
  • filter, filterNot, partition
  • takeWhile, dropWhile, span
  • This is how the map method may be defined:
1
2
3
4

abstract class List[T] {
    def map[U](f: T => U): List[U] = this match {
        case Nil => this
        case x::xs => f(x) :: xs.map(f)

  • Then come folds, accumulate, etc.

  • In a function, confusingly enough, each _ defines a new parameter: (x, y) => (x * y) is equivalent to (_ * _)

1

def sum(xs: List[Int]) = (xs foldLeft 0)(_ + _)

Other Sequences:

  • Vector:

  • Provides a better access to the elements

  • In number of elements < 32,

  • Telephone problem:

I started with the implementation of charCode as:

1
2

val charCode: Map[Char, Char] =
    (for ((k, v) <- mnem) yield (v map ((c) => (c, k)))).flatten.toMap

because I totally forgot that the for expression allows for multiple generators:

1
2

val charCode: Map[Char, Char] =
    for ((k, v) <- mnem; c <- v) yield c -> k

which provides a clearer way of doing things.

In the lecture this was one of the reasons of providing for expression syntax but I could not think about it.

Exercise

  • Given a List of strings, the first way I could think of was to concatenate the strings using xs mkString "", but that seems rather odd and inelegant. The second approach was to use fold like xs.foldLeft("")(_ ++ _)

  • Why did they use a List[Char] instead of a String as the key of the dictionary object?

  • Some of the questions were using Map, which is both a function as well as a collection. Therefore, we can get the value stored in it by using mapname(key). But this explodes if there is no key. One way of safely handling this is to use the get method, which returns an Option and the value can be extracted in case it is Some(v). The alternative is to use withDefaultValue(v) in the map which returns v in case the key is not present in the map.

  • The most difficult exercise was combinations. It took me close to a day in order to think about how to get the result they asked in the exercise. The limiting thought was to think that recursion takes a little bit of “wishful thinking” which was absent for the major portion of time when I was focusing on this problem.

    Initially I started with implementing some sort of power-set for the entire thing. I remembered that there is a recursive way of finding the powerset, so a little bit of time was spent on that. Turns out, it was not the best approach of moving forward.

    The next day, I started with the way as per the instructions written in the course page: using for-comprehensions. This was in the afternoon and I had wasted a lot of my time with pen and paper, so I started with writing createIters method which would return the elements from ('a', n) down to ('a', 0). I then needed to do this each element of the list and create combinations out of it. This was time for a quick break.

    As I walked around, I knew that recursion was the best way of moving forward. This was my way of wishful thinking. I imagined that if I already have everything sorted for the tail of the list, I can createIters(head), and map the cons method on the combinations of tail elements. The case of Nil list was straightforward.

    This took a bit of time, a bit of fighting with the type-checker and then I was able to create a result. Phew!

  • I find my code to be decent, but there are still some places where I could add a bit more functional stuff. Although the code does not use any mutable data-type, which is itself a functional thing, I still need to understand a few Scala specific code patterns.