List methods:

 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:

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)

1

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

Other Sequences:

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