06 March 2014

For the past two weeks I was learning reactive programming using Akka - a toolkit fro building concurrent, distributed, and fault tolerant event-driven applications on the JVM. Because the things are best learnt by doing, I was building a chat application using it. But more about it in the future posts.

Today I decided to take a break from it and do some smaller tasks that do not keep me frustrated for too long. I was doing the Ninety-Nine Scala Problems. I learnt a small but beautiful thing - `flatMapSublists`. It is amazingly simple when you get it and super useful.

Everybody knows `flatMap` - a function that builds a collection by applying some function to all elements of a given list and using the elements of the resulting collections. It is an equivallent of `flatten` applied to the result of `map`. In Scala it’s signature is:

``````def flatMap[B](f: (A) ⇒ GenTraversableOnce[B]): List[B]
``````

However, imagine a situation where you need to apply some function to all the sublists of a given list instead of all the elements of it. If `flatMapSublists` existed it would do exactly that. Problem 26 of Ninety-Nine Scala Problems asks to implement a function that generates the combinations of K distinct objects chosen from the N elements of a list. My solution is here and below:

``````def combinations[T](n: Int, list: List[T]): List[List[T]] = {
def rec(list: List[T], acc: List[List[T]], comb: List[T]): List[List[T]] = {
(comb, list) match {
case (c, _) if c.length == n => List(c.reverse)
case (c, Nil) if c.length < n => List()
case (c, l) => rec(list.tail, acc, list.head::comb) ::: rec(list.tail, acc, comb)
}
}
rec(list, Nil, Nil)
}
``````

Not the most beautiful, not tail-recursive, though quite understandable I guess. However, what I found beutiful is the usage of `flatMapSublists` in their solution, which is also not tail-recursive but which very neatly introduces a layer of abstraction.

``````def flatMapSublists[T, V](ls: List[T])(f: List[T] => List[V]): List[V] = {
ls match {
case Nil => Nil
case list@(_ :: t) => f(list) ::: flatMapSublists(t)(f)
}
}

def combinations[T](n: Int, list: List[T]): List[List[T]] = {
if (n == 0) List(Nil)
else flatMapSublists(list) { sl => combinations(n-1, sl.tail) map (sl.head :: _) }
}
``````

Beautiful, huh? To easier understand it, imagine that for every element in a list you either take it or not until you reach a required number of elements in the current combination. If you take it, you map all the (n-1) element combinations from the list without this element cons’ed with it. If you do not take it, you find all the n elemet combinantions from the list without this element.

Totally beautiful!