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)(_ + _)
