13

I want to write a function that flattens a List.

object Flat {
  def flatten[T](list: List[T]): List[T] = list match {
    case Nil => Nil
    case head :: Nil => List(head)
    case head :: tail => (head match {
      case l: List[T] => flatten(l)
      case i => List(i)
    }) ::: flatten(tail)
  }
}

object Main {
  def main(args: Array[String]) = {
    println(Flat.flatten(List(List(1, 1), 2, List(3, List(5, 8)))))
  }
}

I don't know why it don't work, it returns List(1, 1, 2, List(3, List(5, 8))) but it should be List(1, 1, 2, 3, 5, 8).

Can you give me a hint?

3
  • This is a fun as an exercise. For real code, of course, there is a flatten method on List.
    – AshleyF
    Oct 25, 2012 at 1:55
  • That wouldn't work in this case. The list here is a List[Any] so you'd have to define an implicit conversion from Any => TraversableOnce[_] to call flatten. It must be possible but I doubt it's simpler than this function. Oct 25, 2012 at 2:28
  • Take a look at the compiler errors and warnings: they'll give some big clues Oct 25, 2012 at 3:43

5 Answers 5

33

You don't need to nest your match statements. Instead do the matching in place like so:

  def flatten(xs: List[Any]): List[Any] = xs match {
    case Nil => Nil
    case (head: List[_]) :: tail => flatten(head) ++ flatten(tail)
    case head :: tail => head :: flatten(tail)
  }
0
16

My, equivalent to SDJMcHattie's, solution.

  def flatten(xs: List[Any]): List[Any] = xs match {
    case List() => List()
    case (y :: ys) :: yss => flatten(y :: ys) ::: flatten(yss)
    case y :: ys => y :: flatten(ys)
  } 
2
  • How would (x :: ys) ::: yss means if it is a list of elements followed by another list? (as () means a tuple AFAIK not list) Jul 22, 2015 at 4:55
  • @MuhammadHewedy There are no commas, so it's not a tuple - it's just parentheses to force the correct associativity (without them, y :: ys :: yss would match the first two elements and rest of the list, not a nested list as desired). Feb 24, 2019 at 23:22
11

By delete line 4

case head :: Nil => List(head)

You will get right answer.

Think about the test case

List(List(List(1)))

With line 4 last element in list will not be processed

3
  def flatten(ls: List[Any]): List[Any] = ls flatMap {
    case ms: List[_] => flatten(ms)
    case e => List(e)
  }
0

If someone does not understand this line of the accepted solution, or did not know that you can annotate a pattern with a type:

case (head: List[_]) :: tail => flatten(head) ++ flatten(tail)

Then look at an equivalent without the type annotation:

case (y :: ys) :: tail => flatten3(y :: ys) ::: flatten3(tail)
case Nil :: tail => flatten3(tail)

So, just for better understanding some alternatives:

def flatten2(xs: List[Any]): List[Any] = xs match {
  case x :: xs => x match {
    case y :: ys => flatten2(y :: ys) ::: flatten2(xs)
    case Nil => flatten2(xs)
    case _ => x :: flatten2(xs)
  }
  case x => x
}

def flatten3(xs: List[Any]): List[Any] = xs match {
  case Nil => Nil
  case (y :: ys) :: zs => flatten3(y :: ys) ::: flatten3(zs)
  case Nil :: ys => flatten3(ys)
  case y :: ys => y :: flatten3(ys)
}
val yss = List(List(1,2,3), List(), List(List(1,2,3), List(List(4,5,6))))
flatten2(yss) // res2: List[Any] = List(1, 2, 3, 1, 2, 3, 4, 5, 6) 
flatten3(yss) // res2: List[Any] = List(1, 2, 3, 1, 2, 3, 4, 5, 6) 

By the way, the second posted answer will do the following, which you probably don't want.

val yss = List(List(1,2,3), List(), List(List(1,2,3), List(List(4,5,6))))
flatten(yss) // res1: List[Any] = List(1, 2, 3, List(), 1, 2, 3, 4, 5, 6) 

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.