scala – 递归地构建列表列表

发布时间：2020-12-16 09:06:10 所属栏目：安全来源：网络整理

导读：只要递归调用的返回类型为Any,下面的代码就会编译,但显然我做错了,因为它不应该是Any. case class Group( id: Long = -1,parentId: Long = -1,name: String = "") def makeTree(groupId: Long,groups: List[Group]) = { def getAllChildren(gid: Long): Any

只要递归调用的返回类型为Any,下面的代码就会编译,但显然我做错了,因为它不应该是Any.

case class Group(
    id: Long = -1,parentId: Long = -1,name: String = "")

  def makeTree(groupId: Long,groups: List[Group]) = {
    def getAllChildren(gid: Long): Any = {
      def children = for {
        g <- groups; if g.parentId == gid
      } yield g

      if (children.isEmpty) List()
      else {
        children map { x =>
          getAllChildren(x.id)
        }
      }
    }
    getAllChildren(groupId)
  }                                               
  val groups = List(Group(1,"A"),Group(2,1,"B"),Group(3,"C"),Group(4,2,"D"))

  makeTree(1,groups)
  //Results in: Any = List(List(List()),List())
  }

如果我将getAllChildren的签名更改为：

def getAllChildren(gid: Long): List[Group]

然后我收到一个错误：

type mismatch;  found   : List[List[Group]]  required: List[Group]

我在这做错了什么.

解决方法

不是真的说scala,但看起来,对于某些id,你收集具有该id的组,然后用它的子列表替换每个组,依此类推.

具体来说,这里：

if (children.isEmpty) List()
  else {
    children map { x =>
      getAllChildren(x.id)
     }
  }

实际上,这是您的错误的根源：您的算法允许无限递归,并且每个递归在您的返回类型周围添加另一个List […].但是你不能拥有动态深度的类型.

例如,如果您尝试通过提供类型List [List [Group]]来修复此问题,它会抱怨它找到了List [List [List [Group]]],依此类推,直到您放弃为止.

这是类型测试者告诉我们的方式,即我们即将编程一个潜在的无限递归.您可能假定您的层次结构不能涉及循环的不变量,但这不会反映在类型中.事实上,构建两个群体彼此为父母的例子并不难.在这种情况下,您的程序将生成一个更深的嵌套列表,直到它由于内存不足而终止.

请注意,您无法通过使用flatMap而不是map来修复代码：原因是getAllChildren永远不会生成包含Group元素的列表.它要么返回一个空列表,要么返回一个空列表的扁平列表,即一个空列表.因此,如果它应该返回,它将返回flatmap版本中的空列表.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!