CODEWITHSUNDEEP
listscalascala-collectionsflatten
user64287
user64287

Reputation: 53

flattening list of lists in Scala with out using flatten method giving bad result

I tried to flatten the list of lists using the below code. When I put it on paper, it should work but I think I misinterpreted or am ignorant of how lists work. Could any one tell me where i went wrong.

val a = List(List(1,2,3),List(4,5,6),List(7,8,9))

def flatten(xss : List[List[Any]]) : List[Any] = {
  def flat(xs : List[Any]) : List[Any] = xs match {
    case Nil => Nil
    case head :: Nil=> head :: Nil
    case head :: tail => head :: flat(tail)
  }
  xss match {
    case Nil => Nil
    case head :: Nil => flat(head)
    case head :: tail => flat(head) :: flatten(tail)
  }
}

flatten(a)

Upvotes: 2

Views: 1081

Answers (3)

Tilo
Tilo

Reputation: 3325

You can actually pattern match deep into the structure:

def flatten[T](xss: List[List[T]]): List[T] = xss match {
   case Nil => Nil
   case Nil :: tail => flatten(tail)
   case (innerHead :: innerTail) :: tail => innerHead :: flatten(innerTail :: tail)
}

Upvotes: 0

cmbaxter
cmbaxter

Reputation: 35453

I made two minor changes to your example to get it working. The first was to use a generic (not the problem, but clears up the code a bit). The second was to use ::: instead of :: in the case where the input list has more than one item. The :: method prepends a single item to a List which is the type of items in the list. The ::: concatenates two lists together. Using a type of List[Any], you were not able to see that issue. But once I changed the type to T, it was pretty clear where the issue was.

def flatten[T](xss : List[List[T]]) : List[T] = {
  def flat(xs : List[T]) : List[T] = xs match {
    case Nil => Nil
    case head :: Nil=> head :: Nil
    case head :: tail => head :: flat(tail)
  }
  xss match {
    case Nil => Nil
    case head :: Nil => flat(head)
    case head :: tail => flat(head) ::: flatten(tail)
  }
}

Upvotes: 1

Jean Logeart
Jean Logeart

Reputation: 53829

Your flat function just recreates its argument list so it can be dropped.

You simply need to concatenate the inside lists, using ::::

def flatten(xss : List[List[_]]): List[Any] = xss match {
  case Nil => Nil
  case head :: tail => head ::: flatten(tail)
}

Upvotes: 1

Related Questions