The Problem
In Scala, it's easy to flatten
a nested List
of List
s with the flatten
method:
scala> val nestedList = List(List(1), List(2), List(3, 4))
nestedList: List[List[Int]] = List(List(1), List(2), List(3, 4))
scala> nestedList.flatten
res28: List[Int] = List(1, 2, 3, 4)
...but what if your List
has more than one, or uneven levels of nesting? What if the first element is not a List
, but the rest of the elements are?
scala> val letterList = List("a", List("b"), List("c"), List("d", "e"))
letterList: List[java.io.Serializable] = List(a, List(b), List(c), List(d, e))
scala> letterList.flatten
<console>:13: error: No implicit view available from java.io.Serializable => scala.collection.GenTraversableOnce[B].
letterList.flatten
^
Notice the types of the first and second List
s in the interpreter:
nestedList: List[List[Int]] // vs
letterList: List[java.io.Serializable]
Scala tries to find the narrowest class which encompasses all of the data in your List
in order to infer the type. In the first example, this is easy. All of our inner List
s contain only Int
elements, so they must all be List[Int]
s. This is more difficult in the second example, because the elements of the outermost list can be String
s as well as List[String]
s. Scala finds the smallest class which encompasses both of those types of data, and that's java.io.Serializable
. Using Int
s again we get what might be a more understandable result:
scala> val raggedList = List(1, List(2), List(3), List(4, 5))
raggedList: List[Any] = List(1, List(2), List(3), List(4, 5))
scala> raggedList.flatten
<console>:13: error: No implicit view available from Any => scala.collection.GenTraversableOnce[B].
raggedList.flatten
^
...this is a List[Any]
, where Any
is the only class which can represent both Int
as well as List[Int]
values. This means that when we try to flatten
the List
, we're trying to apply a method with the signature:
def flatten[B](implicit asTraversable: Any => scala.collection.GenTraversableOnce[B]): List[B]
This signature might be a little intimidating, but the important bit is that -- in the case of nestedList
, we're trying to convert an Any
to another Scala object with a generic type B
, returning a List
of that type, List[B]
. In our raggedList
example, we simply don't have a way to convert the type Any
to the GenTraversableOnce
type required by flatten
.
The Solution
Instead of blindly using flatten
, we can instead think about the structure of our data. We have a List
which contains elements which are themselves either
-
List
s - anything else that's not a
List
...and we want to "unwrap" the inner List
s into their constituent elements. How can we do that? Pattern matching!
def squash (list: List[Any]): List[Any] = list match {
case Nil => Nil
case x :: xs => { x match {
case y :: ys => (y :: squash(ys)) ::: squash(xs)
case _ => x :: squash(xs)
}}
}
The squash
method above first looks at the outer List
, named list
. It breaks it into a head x
and a tail xs
. If x
is itself a List
, it breaks that inner list into a head y
, and a tail ys
. We recursively squash
the inner list x
until it's completely flat, then concatenate it to the rest of the squashed outer list, squash(xs)
.
If the head of list
, x
, isn't a List
, we simply append it to the beginning of the squashed outer list, squash(xs)
.
Does it work? It does indeed!
scala> squash(raggedList)
res34: List[Any] = List(1, 2, 3, 4, 5)
scala> squash(letterList)
res35: List[Any] = List(a, b, c, d, e)
scala> val crazyList = List(1, 2, List(3), 4, List(5, List(6, 7)), List(8, List(9, List(0))))
crazyList: List[Any] = List(1, 2, List(3), 4, List(5, List(6, 7)), List(8, List(9, List(0))))
scala> squash(crazyList)
res36: List[Any] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
...with one caveat, of course. All of the resulting List
s are of type Any
! Can you improve this solution to fix that?
Top comments (0)