Search code examples
scalafunctional-programming

Scala flatten a List

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?

Solution

  • 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