Theorem flatten

flatten.scala

// Super simple, recursive flatten
// The _ means we have a weakly polymorphic type
// i.e. we don't care about what type _ is (it will, or will not, be resolved later)
// the type signature for flatMap on Seq is Seq[A] => (A => Seq[B]) => Seq[B]
def flatten(s: Seq[_]): Seq[_] = s flatMap {
  case s: Seq[_] => flatten(s) // If s is a Seq, we recursively flatten
  case s => Seq(s) // If s is atomic, we're done; just package up s
}

// degenerate case
flatten(List()) == List()

// 0 level nesting
flatten(List(1, 2, 3, 4)) == List(1, 2, 3, 4)

// 1 level nesting
flatten(List(1, List(2, 3), List(4))) == List(1,2,3,4)

// 2 level nesting
flatten(List(1, List(2, List(3, 4)), List(5))) == List(1,2,3,4,5)