scala - Scala展平列表

Question

我想编写一个扁平化列表的函数。

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

我不知道为什么它不起作用，它返回List(1, 1, 2, List(3, List(5, 8)))但它应该是List(1, 1, 2, 3, 5, 8)。

你能给我一个提示吗？

Answer 1

您不需要嵌套匹配语句。而是像这样进行匹配：

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

Answer 2

我的，相当于 SDJMcHattie 的解决方案。

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

Answer 3

通过删除第 4 行

case head :: Nil => List(head)

你会得到正确的答案。

考虑测试用例

List(List(List(1)))

第 4 行列表中的最后一个元素将不会被处理

Answer 4

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

Answer 5

如果有人不理解这行可接受的解决方案，或者不知道您可以使用类型注释模式：

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

然后看一个没有类型注释的等价物：

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

因此，只是为了更好地理解一些替代方案：

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) 

顺便说一句，第二个发布的答案将执行以下操作，您可能不希望这样做。

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)