Generic, type-safe way to flatten arbitrarily nested collections in Scala?

Question

On occasion I take some time to play with Scala, whose mix of features appeals to me despite an inability to use it in my own work (thus far). For kicks I decided to try the first few 99 Haskell Problems in the most generic way possible — operating on and returning any kind of applicable collection. The first few questions weren’t too difficult, but I find myself utterly stymied by flatten. I just can’t figure out how to type such a thing.

To be specific about my question: is it possible to write a type-safe function that flattens arbitrarily-nested SeqLikes? So that, say,

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))))

would return

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int]

? Note that this isn’t quite the same question as in the Haskell and Scala problem sets; I’m trying to write a function that flattens not heterogeneous lists but, rather, homogeneous-but-nested sequences.

Searching the web I found a translation into Scala of that question, but it operates on and returns a List[Any]. Am I correct that this would require some kind of type recursion? Or am I making this out to be harder than it is?

please make your `reverse` question a separate SO question since it has nothing to do with main question — dhg, Aug 28 '12 at 14:54
Please see here: http://stackoverflow.com/questions/7213134/how-does-this-recursive-list-flattening-work — Debilski, Aug 28 '12 at 15:05
That almost does it, except I can’t quite finagle it into being generic WRT the type of sequence. — James Cunningham, Aug 28 '12 at 15:18

0__ · Accepted Answer · 2016-02-28T13:51:56.060

The following works in Scala 2.10.0-M7. You will need to add extra cases for Array support, and perhaps refine it to have more specific output collection types, but I guess it can all be done starting from here:

sealed trait InnerMost {
  implicit def innerSeq[A]: CanFlatten[Seq[A]] { type Elem = A } =
    new CanFlatten[Seq[A]] {
      type Elem = A
      def flatten(seq: Seq[A]): Seq[A] = seq
    }
}
object CanFlatten extends InnerMost {
  implicit def nestedSeq[A](implicit inner: CanFlatten[A]) 
  : CanFlatten[Seq[A]] { type Elem = inner.Elem } =
    new CanFlatten[Seq[A]] {
      type Elem = inner.Elem
      def flatten(seq: Seq[A]): Seq[inner.Elem] =
        seq.flatMap(a => inner.flatten(a))
    }
}
sealed trait CanFlatten[-A] {
  type Elem
  def flatten(seq: A): Seq[Elem]
}

implicit final class FlattenOp[A](val seq: A)(implicit val can: CanFlatten[A]) {
  def flattenAll: Seq[can.Elem] = can.flatten(seq)
}

// test        
assert(List(1, 2, 3).flattenAll == Seq(1, 2, 3))
assert(List(Seq(List(1, 2, 3), List(4, 5, 6)), Seq(List(7, 8, 9),
                List(10, 11, 12))).flattenAll == (1 to 12).toSeq)

Very nice, thank you! I’ll mark this as answered, though it may take me some time to work through it. Honestly, if I’d known it was that much code even to start with, I wouldn’t have tried so hard before I asked. ;) — James Cunningham, Aug 29 '12 at 10:54
It might be easier with just two type parameters for `CanFlatten`. It got involved with the type member because otherwise the implicits wouldn't resolve completely on their own. I think that if you don't need `nestedSeq.flattenAll` but `flattenAll(nestedSeq)` is sufficient (i.e. no "pimping"), it becomes easier, more like the linked question ("How does this recursive..."). — 0__, Aug 29 '12 at 13:45

score 4 · Answer 2 · answered Aug 28 '12 at 14:49

It seems like the right thing to do is just call .flatten the right number of times:

scala> val x = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))
x: List[Array[List[Int]]] = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))

scala> x.flatten.flatten
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Since Scala is typed, you always know ahead of time how deep the nesting goes for the specific variable. Since you know this ahead of time, there's not much value in handling arbitrary structure as if you were unsure of how many times .flatten needed to be called.

That’s a fair response, although I’m still curious if such a function is possible to write. :) — James Cunningham, Aug 28 '12 at 15:04

Debilski · Answer 3 · 2012-08-28T14:36:37.647

3

You are facing the same problems they are describing in the Haskell solution: There is no heterogenous List in Scala. Luckily you can follow the exact same path they are going in the Haskell solution.

Define some data type which can be nested:

sealed trait NestedList[A]
case class Elem[A](a: A) extends NestedList[A]
case class AList[A](a: List[NestedList[A]]) extends NestedList[A]

And then write a generic flatten function for that type:

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x :: xs) => flatten(x) ::: flatten(AList(xs))
  case AList(Nil) => Nil
}

or even

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x) => x.flatMap(flatten)
}

Usage:

flatten(AList(Elem(1) :: Elem(2) :: AList(Elem(3) :: Nil) :: Nil))

Of course, we could also have added this as a method directly to the NestedList trait.

edited Aug 28 '12 at 14:36

answered Aug 28 '12 at 14:24

Debilski

66,976
12
110
133

I may not have been totally clear or precise when asking my question, as that's not what I had in mind. I'm not trying to write a flatten function that operates on heterogeneous lists but, rather, a flatten function that operates generically on homogeneous-but-nested Seqs as in my example. I'm curious (1) whether it's possible and (2) how to write it if it is. Thank you, though. – James Cunningham Aug 28 '12 at 14:41
Ah, okay. Then the haskell example was misguiding me a bit. – Debilski Aug 28 '12 at 14:57
Does not work for lists that intermix Int with String – thebluephantom Jun 29 '18 at 08:41

Generic, type-safe way to flatten arbitrarily nested collections in Scala?

3 Answers3

Linked