How does this recursive List flattening work?

Question

A while back this was asked and answered on the Scala mailing list:

Kevin:

Given some nested structure: List[List[...List[T]]] what's the best (preferably type-safe) way to flatten it to a List[T]

Jesper:

A combination of implicits and default arguments works:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T, U](implicit f : Flat[T, U] = Flat((l : T) 
=> List(l))) = 
   Flat((l : List[T]) => l.flatMap(f.fn)) 

def recFlatten[T, U](l : List[T])(implicit f : Flat[List[T], U]) = f.fn(l) 

Examples:

scala> recFlatten(List(1, 2, 3)) 
res0: List[Int] = List(1, 2, 3) 

scala> recFlatten(List(List(1, 2, 3), List(4, 5))) 
res1: List[Int] = List(1, 2, 3, 4, 5) 

scala> recFlatten(List(List(List(1, 2, 3), List(4, 5)), List(List(6, 7)))) 
res2: List[Int] = List(1, 2, 3, 4, 5, 6, 7) 

I have been looking at this code for a while. I cannot figure out how it works. There seems to be some recursion involved... Can anybody shed some light? Are there other examples of this pattern and does it have a name?

Answer 1

May be a good solution is to try to look at how the types are infered. To avoid ambiguity, let us rename the generics:

case class Flat[T, U](fn : T => List[U]) 

implicit def recFlattenFn[T2, U2](implicit f : Flat[T2, U2] = 
                                    Flat((l : T2) => List(l))) = 
  Flat((l : List[T2]) => l.flatMap(f.fn)) 

def recFlatten[T3, U3](l : List[T3])(implicit f : Flat[List[T3], U3]) = f.fn(l) 

In the first case, res0, the type of T3 is Int you cannot infer yet the type of U3, but you know that you will need a Flat[List[Int, U3]] object that will be provided implicitly. There is only one "implicit candidate": the result of the recFlattenFn function and its type is Flat[List[T2], List[U2]]. Thus T2 = Int and U2 = U3 (that we still need to infer).

Now, if we weant to be able to use recFlatten we must provide it a parameter f. Here is the trick. You can either use an implicit of type Flat[Int, U2] or the default value of type Int => List[Int]. Let us look about the available implicits. As explained before recFlattenFn can provide a Flat[List[T2], U2] (for a new T2 and U2) object. It does not fit the expected signature of fat this point. Thus, no implicit are a good candidate here and we must use the default argument. As the type of the default argument is Int => List[Int], U2and U3 are Int and there we go.

Hope that this long prose will help. I leave you with the resolution of res1 and res2.

Answer 2

Oh wow, this is an old one! I'll start by cleaning up the code a bit and pulling it into line with current idiomatic conventions:

case class Flat[T, U](fn: T => List[U]) 

implicit def recFlattenFn[T, U](
  implicit f: Flat[T, U] = Flat((xs: T) => List(xs))
) = Flat((xs: List[T]) => xs flatMap f.fn)

def recFlatten[T, U](xs: List[T3])(implicit f: Flat[List[T], U]) = f fn xs 

Then, without further ado, break down the code. First, we have our Flat class:

case class Flat[T, U](fn: T => List[U]) 

This is nothing more than a named wrapper for the function T => List[U], a function that will build a List[U] when given an instance of type T. Note that T here could also be a List[U], or a U, or a List[List[List[U]]], etc. Normally, such a function could be directly specified as the type of a parameter. But we're going to be using this one in implicits, so the named wrapper avoids any risk of an implicit conflict.

Then, working backwards from recFlatten:

def recFlatten[T, U](xs: List[T])(implicit f: Flat[List[T], U]) = f fn xs 

This method will take xs (a List[T]) and convert it to a U. To achieve this, it locates an implicit instance of Flat[T,U] and invokes the enclosed function, fn

Then, the real magic:

implicit def recFlattenFn[T, U](
  implicit f: Flat[T, U] = Flat((xs: T) => List(xs))
) = Flat((xs: List[T]) => xs flatMap f.fn)

This satisfies the implicit parameter required by recFlatten, it also takes another implicit paramater. Most crucially:

• recFlattenFn can act as its own implicit parameter
• it returns a Flat[List[X], X], so recFlattenFn will only be implicitly resolved as a Flat[T,U] if T is a List
• the implicit f can fallback to a default value if implicit resolution fails (i.e. T is NOT a List)

Perhaps this is best understood in the context of one of the examples:

recFlatten(List(List(1, 2, 3), List(4, 5))) 

• The type T is inferred as List[List[Int]]
• implicit lookup is attempted for a `Flat[List[List[Int]], U]
• this is matched by a recursively defined recFlattenFn

Broadly speaking:

recFlattenFn[List[List[Int]], U] ( f =
  recFlattenFn[List[Int], U] ( f =
    Flat[Int,U]((xs: T) => List(xs)) //default value
  )
)

Note that recFlattenFn will only match an implicit search for a Flat[List[X], X] and the type params [Int,_] fail this match because Int is not a List. This is what triggers the fallback to the default value.

Type inference also works backwards up that structure, resolving the U param at each level of recursion:

recFlattenFn[List[List[Int]], Int] ( f =
  recFlattenFn[List[Int], Int] ( f =
    Flat[Int,Int]((xs: T) => List(xs)) //default value
  )
)

Which is just a nesting of Flat instances, each one (except the innermost) performing a flatMap operation to unroll one level of the nested List structure. The innermost Flat simply wraps all the individual elements back up in a single List.

Q.E.D.