Functional Programming in Scala: Weeks 5 and 6
List methods: #
-
How to create the methods like
take
,drop
,reverse
,append
, etc. on Lists. -
Implementation of mergesort.
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:
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:
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.
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:
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:
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(_ * _)
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:
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:
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 usefold
likexs.foldLeft("")(_ ++ _)
-
Why did they use a
List[Char]
instead of aString
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 usingmapname(key)
. But this explodes if there is no key. One way of safely handling this is to use theget
method, which returns anOption
and the value can be extracted in case it isSome(v)
. The alternative is to usewithDefaultValue(v)
in the map which returnsv
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)
, andmap
thecons
method on the combinations of tail elements. The case ofNil
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.