通过递归调用在 Scala 中理解

Question

我正在做 coursera 课程的最后一个项目 "functional programming in scala"。我需要实现一个名为 combinations 的函数，它获取字符出现列表并输出字符出现的所有可能子集。例如，出现列表 List(('a', 2), ('b', 2)) 的子集是：

List(
  List(),
  List(('a', 1)),
  List(('a', 2)),
  List(('b', 1)),
  List(('a', 1), ('b', 1)),
  List(('a', 2), ('b', 1)),
  List(('b', 2)),
  List(('a', 1), ('b', 2)),
  List(('a', 2), ('b', 2))
)

我解决这个问题的方法是遍历每个字符（例如'a'），并获取它可能出现的次数（从0到2），然后将其预扩展到当前子集。然后继续下一个字符并重复，直到我到达列表的末尾，这被基本情况捕获。我用如下的 for comprehension 实现了这个：

type Occurrences = List[(Char, Int)]

def combinations(occurrences: Occurrences): List[Occurrences] =
  if (occurrences == List()) List() // base case
  else
    for {
      (c, n) <- occurrences
      subc <- combinations((occurrences.toMap - c).toList)
      i <- 0 to n
    } yield {
      if (i == 0) subc // not including c in the subset
      else (c, i) :: subc // including c in the subset
    }

当我调用 combinations(List(('a', 2), ('b', 2)) 时，这个函数总是给我一个空列表。知道为什么会这样吗？

Answer 1

出现意外输出的原因在这里：

subc <- combinations((occurrences.toMap - c).toList)

这将递归，加载堆栈帧，直到最终 return 基本情况 List()。现在，请记住，在 for 理解中，生成器 (<-) 是通过 map 或 flatMap 实现的，一旦你映射到一个空集合上，你就完成了。

List[Int]().map(_ + 1).foreach(_ => println("got it"))  // no output

因此未调用以下生成器 i <- 0 to n，yield 没有任何内容，空的 List() 是 return 的唯一内容。然后栈帧弹出，收到空List()等

Answer 2

问题在于线路：

subc <- combinations((occurrences.toMap - c).toList)

在基本情况上方的调用中，这被评估为 List() 这会妨碍您的理解：

scala> for {a <- 0 to 3; b <- List()} yield a
res0: scala.collection.immutable.IndexedSeq[Int] = Vector()

这会调用 return List() 等等，这意味着您 return 在调用堆栈中一直使用空列表，这就是为什么您会得到 List() 在顶部。

通过递归调用在 Scala 中理解

for comprehension in scala with recursive call

scala

for-comprehension