For Angry Java Developers That Are Pissed Off At The Way Scala Professors present their material. ( this example was taken from Chapter 3, Functional Programming In Scala, Paul Chiusano and Runar Bjarnason.)
Write a function flatMap that works like map except that the function given will return a list instead of a single result, and that list should be inserted into the final resulting list. Here is its signature and definition as presented by the author:
def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] =
concat(map(l)(f))
Now just looking at that definition will cause the typical Java Developer to throw his/her hands up proclaiming something to the effect: WTF is this jerk talking about!!!
But, me, being a little stubborn decided to decompose the definition:
The declaration seems to be saying: Given a list , take each element and convert that element into a List finally converting all the individual lists to one list of
elements.
def flatMap[A,B](l: List[A])(f: A => List[B]): List[B] =
concat(map(l)(f))
So what does: concat(map(l)(f)) actually do? Well, map(l)(f) will do the following:
apply the function , f , to every element in l. Lets observe that behavior:
def map[A,B](l: List[A])(f: A => List[B]): List[B] =
l match {
case Nil => Nil
case Cons(h,t) => Cons(f(h) ,map(t))
}
Now this will seemingly convert the List of elements into a List of List of elements. This in turn is passed to the concat method.
Again, lets analyze concat to see what it does:
According to the author’s definition of concat we have:
def concat[A](l: List[List[A]]): List[A] =
foldRight(l, Nil:List[A])(append)
Now the definition of concat is a function that takes a List[List[A]] and returns a List[A] which is what we actually want to happen. But how does it do this?
foldRight(l,Nil:ListA !!!
Holy Cow!
foldRight’s purpose is to take a list, apply a function to the elements of the list moving from right to left until all the elements are exhausted and then return a terminating element which is in this case: Nil:List[A]. So it boils down to what the append function is doing to pairs of elements of the input list.
In steps the definition of append:
def append[A](a1: List[A], a2: List[A]): List[A] =
a1 match {
case Nil => a2
case Cons(h,t) => Cons(h, append(t, a2))
}
QED