2 
  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[?]

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

4

5 回答 5

9

我没有收到与您有关的相同错误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在其内部调用（这就是发生任意嵌套的地方）。

于 2013-08-26T23:14:10.277 回答
3

我认为你只是缺少一个演员。

if( h.isInstanceOf[List[_]]) { iflatten(h.asInstanceOf[List[_]], ret) }

或者：模式匹配会更漂亮。

h match {
  case hList: List[_] => 
    iflatten(hList, ret)
  case _ => 
    l.head :: ret
    iflatten(l.tail, ret)
}

（警告：这只是我的想法，我没有通过编译器进行任何操作）

编辑 - Marth 将其合并到前一个模式匹配中的解决方案看起来比我的要好。

于 2013-08-26T23:11:29.393 回答
3

实际上，我怀疑问题在于您定义了内部方法 iflatten，但从不调用它，因此外部方法 flatten 不会返回任何内容（即默认为 Unit 的返回类型，与声明的返回类型冲突列表[_])。

尝试添加以下内容作为外部 flatten 方法的最后一行：

iflatten(l, Nil)

除此之外，您的代码还有其他各种问题，例如无法处理所有匹配情况：您处理具有一个元素的列表的情况h :: Nil- 但不是多个元素。您可能的意思是h :: theRest, 然后在theRest某处使用 - 可能作为ret递归调用的参数。

您还使用了检查h.isInstanceOf[List[_]]（通常任何使用isInstanceOf都是 scala 中的不良代码气味），然后尝试将 h 递归地传递给 iflatten 而不将其强制转换为List[_]（例如，如@ChristopherMartin 的回答，尽管 usingasInstanceOf是更大的代码气味）。@Marth 的回答给出了如何避免这些显式类型检查的一个很好的例子。

于 2013-08-26T23:12:52.377 回答
2

我认为这是Shapeless库擅长的。

https://github.com/milessabin/shapeless/blob/master/examples/src/main/scala/shapeless/examples/flatten.scala

于 2013-08-27T08:17:21.920 回答
1

抱歉，这段代码非常复杂。我试图简化它并得到这个解决方案：

    scala> :paste
    // Entering paste mode (ctrl-D to finish)

        def flatten(l : List[_]) : List[_] = l flatMap {
          case l1 : List[_] => flatten(l1)
          case otherwise => List(otherwise)
        }


    // Exiting paste mode, now interpreting.

    flatten: (l: List[_])List[_]

    scala> flatten(List(1,2,3))
    res3: List[Any] = List(1, 2, 3)

    scala> flatten(List(1,2,List(3,4)))
    res4: List[Any] = List(1, 2, 3, 4)

    scala> flatten(List(List(1,List(2),3),4,List(4,5)))
    res5: List[Any] = List(1, 2, 3, 4, 4, 5)

修复代码（添加对 的调用iflat）后，我进行了以下重构：

  1. 删除了内部方法
  2. 使用内置flatMap的迭代（因此可以消除或简化一些case表达式）
  3. instanceOf用类型保护替换了

我认为更简单的解决方案是使用shapeless 库（提示：查找“样板”部分）。

于 2013-08-27T08:19:33.993 回答