scala - 在 Scala 中展平任意嵌套的列表

Question

  def flatten(l: List[_]): List[_] = {
    def iflatten(l: List[_], ret: List[_]): List[_] = l match {
      case Nil => ret
      case h :: Nil =>
        if( h.isInstanceOf[List[_]]) { iflatten(h, ret) }
        else {
          l.head :: ret
          iflatten(l.tail, ret)
        }
    }
  }

我知道有多种方法可以做到这一点，但我不能 100% 确定我的方法是正确的。我想测试它，但我遇到的一个问题是在我调用的第二个 case 语句中:

... { iflatten(h, ret) }

我收到编译器错误:

error: type mismatch;
found   : Unit
required: List[?]

我正在尝试解决这些类型问题以了解有关类型系统的更多信息，因为它与我过去使用的不同。对于编译器为何提示的任何建议，我们将不胜感激。

Answer 1

我没有收到与您有关 iflatten(h,ret) 的相同错误。我得到 found : Unit; required : List[?] 错误，但它指的是你没有在 flatten 本身调用 iflatten :定义后，你需要调用 flatten 末尾的函数的定义。

def flatten(l: List[_]): List[_] = {
  def iflatten(l: List[_], ret: List[_]): List[_] = l match {
    case Nil => ret
    case (h:List[_]) :: tail => iflatten(tail,iflatten(h,ret))
    case h :: tail => iflatten(tail,h::ret)
  }
  iflatten(l,List()).reverse
}

至于代码本身，您可以(并且应该)在匹配时验证类型。另请注意，case h::Nil 仅匹配长度为 1 的列表。

至于算法，你需要在自身内部调用iflatten(这是任意嵌套发生的地方)。