4

只要递归调用的返回类型是 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, 0, "A"), 
                    Group(2, 1, "B"), 
                    Group(3, 1, "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]

我在这里做错了什么。

4

3 回答 3

4

您需要将调用更改为children map ...for children flatMap ...，否则您不会返回 aList[Group]但可能会List[List[.....]]像@Ingo 建议的那样返回。flatMap将每个元素映射到 aList然后展平所有列表以创建一个List[Group]包含所有子元素的列表。

编辑：正如@Ingo 指出的那样，即使flatMap可以解决打字问题，您的功能仍然无法正常工作，因为您总是返回一个空列表。你应该去

children flatMap { x => x :: getAllChildren(x.id, acc) }

把孩子放在孩子的孩子面前。

于 2013-07-12T13:58:32.110 回答
4

不是真的在说 scala，但看起来，对于某些 id，您收集具有该 id 的组，然后将每个组替换为其子列表，依此类推。

具体来说，这里：

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

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

例如，如果您尝试通过提供 type 来解决此问题List[List[Group]]，它会抱怨它 found List[List[List[Group]]]，依此类推，直到您放弃。

这就是类型检查器告诉我们即将编写一个潜在的无限递归的方式。您可能已经假设您的层次结构不能涉及循环的不变量，但这并未反映在类型中。事实上，构建一个两组互为父母的例子并不难。在这种情况下，您的程序将生成一个更深的嵌套列表，直到它因内存不足而终止。

请注意，您不能简单地通过使用 flatMap 而不是 map 来修复代码：原因是 getAllChildren 永远不会生成包含 Group 元素的列表。它要么返回一个空列表，要么返回一个空列表的扁平列表，即一个空列表。因此，如果它应该返回，它将在平面地图版本中返回一个空列表。

于 2013-07-12T13:19:39.197 回答
2

如果您children map像这样展平返回的列表，您的代码将起作用：

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

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

      listList.flatten
    }
  }
  getAllChildren(groupId)
}

发生这种情况的原因是您正在使用 List[Group] 并将其映射到也返回 a 的函数上List[Group]，从而导致 a List[List[Group]]。简单地展平该列表将产生所需的结果。

于 2013-07-12T13:16:19.303 回答