在Scala中展平任意嵌套的列表 [英] Flatten arbitrarily nested List in Scala

问题描述

  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 语句中:

I know there are multiple ways to do this, and I'm not 100% sure my way is correct. I would like to test it but one issue I'm running into is in the second case statement where I call:

... { iflatten(h, ret) }

我收到编译器错误:

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

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

I'm trying to work through these type issues to learn more about the typesystem as it's different than what I've worked with in the past. Any suggestions as to why the compiler is complaining would be greatly appreciated.

推荐答案

抱歉，这段代码很复杂.我试图简化它并得到了这个解决方案:

Sorry, but this code is very complicated. I tried to simplify it and got to this solution:

    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的调用)，我进行了以下重构:

After fixing the code (adding the call to iflat), I did the following refactorings:

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

1. Removed the inner method
2. Used the built in flatMap for the iteration (and hence could eliminate or simplify some case expressions)
3. Replaced the instanceOf with type guards

我认为更简单的解决方案是使用 shapeless 库(提示:寻找样板"部分).

I think a simpler solution would be using the shapeless library (hint: look for the "boilerplate" part).

这篇关于在Scala中展平任意嵌套的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！