How to create function which would make flat List from arbitrarily deeply nested lists?

Question

Is it possible to write function in scala which would take list of arbitrarily deeply nested lists and transform it recursively into flat list? For example:

flatten(List(List(1), List(List(2), 3), 4))

should return

List(1,2,3,4)

I did some tries with shapeless but without effect:

object flatten extends (List ~> List) {
    def apply[T](s: List[T]) = s.map {
       case l: List[T] => apply(s)
       case x => x
    }
}

This gives me:

type mismatch

found: List[Any]

required: List[T]

Would be also great if it can deduct right type (in case of example List[Int] and not List[Any])

Answer 1

The thing is, you don't receive a List[T] in input, but a List[Any] where Any is a mix of T and List[Any].

So if you know the type of leaf elements, you could potentially use a type parameter T to represent it and flatmap elements by recursively pattern matching on either T or List[Any]:

import scala.reflect.ClassTag

def flatten[T: ClassTag](list: List[Any]): List[T] =
  list.flatMap {
    case x: T => List(x)
    case sub: List[Any] => flatten[T](sub)
  }

flatten[Int](List(List(1), List(List(2), 3), 4))
// List[Int] = List(1, 2, 3, 4)

Answer 2

Your desired flatten is intrinsically untyped. You are putting elements (let's say they have type E), lists thereof (List[E]), lists thereof (List[List[E]]), etc. into one list, which must have type List[Any], because its elements don't have anything in common. Shapeless is all about having descriptive types and transforming between them, so it has nothing for you. Furthermore, look at your function's definition:

def apply[T](s: List[T]) = s.flatMap { // should be flatMap, conceptually
   case l: List[T] => apply(l) // should be l, conceptually
   case x => List(x) // should be singleton list, conceptually
}

So, s is a List[T], and s.map is giving you each of the Ts in turn. You then use a type-case, and, in one of the arms, you check whether l: T is actually a l: List[T]. That is, you check that List[T] <: T. This is weird, and signifies that your function is incorrect.

If you really want to use Shapeless, accurately describe your input with types. We want this interface for flatten[T]:

• If it receives a t: T, then it returns List(t): List[T].
• If it receives a l: List[X], where X is a valid input to flatten[T], it flattens each X, then outputs the concatenation of the results as one, big List[T].
• If it receives a h: H where H <: HList, where each element of H is a valid input to flatten[T], each element is flattened and the results are concatenated into one List[T].

This is its implementation:

object flatten extends Poly1 {
  implicit def caseT[T] = at[T](List(_))
  implicit def caseList[T, X](implicit e: Case.Aux[X, List[T]])
    = at[List[X]](_.flatMap(e))
  implicit def caseHNil[T, N <: HNil] = at[N](_ => List[T]())
  implicit def caseHCons[T, H, R <: HList](implicit hf: Case.Aux[H, List[T]],
                                                    rf: Case.Aux[R, List[T]])
    = at[H :: R] { case h :: r => hf(h) ++ rf(r) }

  final class Specialized[T] {
    def apply[X](x: X)(implicit c: Case.Aux[X, List[T]]): List[T] = c(x)
  }
  def apply[T]: Specialized[T] = new Specialized
}

With usage:

scala> flatten[Int]((1 :: HNil) :: ((2 :: HNil) :: 3 :: HNil) :: 4 :: HNil)
List(1, 2, 3, 4)
scala> flatten[Int](1 :: List(2, 3) :: List(List(4, 5), List(), List(6, 7)) :: List(8 :: List(9, 10) :: HNil, 11 :: List(12, 13, 14) :: HNil) :: HNil)
List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

The alternative is to simply use the correct data structure. In this context, the correct structure is called the free monad on List, also known as the rose tree:

sealed trait Free[M[+_], +A] {
  def flatten(implicit M: Monad[M]): M[A]
}
case class Pure[M[+_], +A](x: A) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = M.pure(x)
}
case class Step[M[+_], +A](step: M[Free[M, A]]) extends Free[M, A] {
  override def flatten(implicit M: Monad[M]) = step.flatMap(_.flatten)
}
// for convenience
object Rose {
  type Rose[+A] = Free[List, A]
  type Leaf[+A] = Pure[List, A]
  type Branch[+A] = Step[List, A]
  object Leaf {
    def apply[A](x: A): Leaf[A] = Pure(x)
    def unapply[A](x: Leaf[A]): Some[A] = Some(x.x)
  }
  object Branch {
    def apply[A](xs: Rose[A]*): Branch[A] = Step(xs.toList)
    def unapplySeq[A](xs: Branch[A]): Some[List[Rose[A]]] = Some(xs.step)
  }
}
// specialized:
// sealed trait Rose[+A] { def flatten: List[A] }
// case class Leaf[+A](x: A) extends Rose[A] { override def flatten = List(x) }
// case class Branch[+A](x: List[Rose[A]]) extends Rose[A] { override def flatten = x.flatMap(_.flatten) }

Usage:

scala> Branch(Branch(Leaf(1)), Branch(Branch(Leaf(2)), Leaf(3)), Leaf(4)).flatten