CODEWITHSUNDEEP
scalafunctional-programming
Lux Weidling
Lux Weidling

Reputation: 135

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?

Upvotes: 13

Views: 11270

Answers (5)

colorblind
colorblind

Reputation: 168

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)

Upvotes: 0

Sumit Pawar
Sumit Pawar

Reputation: 31

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

Upvotes: 3

sfotiadis
sfotiadis

Reputation: 977

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)
  }

Upvotes: 16

SDJMcHattie
SDJMcHattie

Reputation: 1699

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)
  }

Upvotes: 33

Tim Green
Tim Green

Reputation: 3649

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

Upvotes: 11

Related Questions