## 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:

• 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.