Scala Recursive For Comprehension 仅在空列表前添加一次，为什么？

Question

类似于此 post ，我正在研究“Scala 中的函数式编程”Anagrams 课程作业。我无法弄清楚组合函数，但在其他地方找到了这个非常优雅的解决方案

def combinations(occurrences: Occurrences): List[Occurrences] =
  List() :: (for {
    (char, max) <- occurrences
    count <- 1 to max
    rest <- combinations(occurrences filter {case (c, _) => c > char})
  } yield List((char, count)) ++ rest)

我理解 for 理解如何创建组合，但我不明白的是为什么在每次递归调用期间空列表没有预先附加到每个内部列表。就好像编译器跳过了前置语句，只执行表达式的右侧。

例如输入combinations(List(('a', 2), ('b', 2)))returns预期结果集：

res1: List[forcomp.Anagrams.Occurrences] = List(List(), List((a,1)), List((a,1), (b,1)), List((a,1), (b,2)), List((a,2)), List((a,2), (b,1)), List((a,2), (b,2)), List((b,1)), List((b,2)))

只有一个空列表。查看递归调用，我希望每个递归都有另一个空列表。有人能解释一下这个优雅的解决方案是如何工作的吗？

Answer 1

这里没有生成空列表以供理解。即使

combinations(occurrences filter {case (c, _) => c > char})

包含一个空列表并 return 在 rest <- ... 中编辑它（它应该用于第一个元素），在 List((char, count)) ++ rest 中预先添加一个值使其在设计上非空。

所以整个 for-comprehension 必须 return 一个 List 的非空 List，其中一个空列表被前置。

这基本上是通过归纳法构建解决方案：

如果您有一个空列表 - return一个空列表，因为它是此输入的有效解决方案
如果你从 (char, maxOccurrences) :: rest 开始
- 假设您有 combinations(rest)
- 然后采用每个这样的解决方案并将 (char, 1) 添加到 rest,
- 然后采用每个这样的解决方案并将 (char, 2) 添加到 rest,
- ...
- 然后采用每个这样的解决方案并将 (char, maxOccurrences) 添加到 rest
- 然后将所有这些结果合并为一个解决方案
- 所有这些都是非空的，因为你总是在前面加上一些东西
- 所以你缺少空集，所以你明确地将它添加到所有其他组合的解决方案中，为 (char, maxOccurrences) :: rest

因为您有一个有效的起点和从上一步创建下一步的有效方法，您知道您始终可以创建一个有效的解决方案。

在理解中

  def combinations(occurrences: Occurrences): List[Occurrences] =
    List() :: (for {
      (char, max) <- occurrences
      count <- 1 to max
      rest <- combinations(occurrences filter {case (c, _) => c > char})
    } yield List((char, count)) ++ rest)

正在做与

相同的事情

def combinations(occurrences: Occurrences): List[Occurrences] =
  List() :: occurrences.flatMap { case (char, max) =>
    (1 to map).flatMap { count =>
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        (char, count) :: rest
      }
    }
  }

与

相同

def combinations(occurrences: Occurrences): List[Occurrences] =
  occurrences.map { case (char, max) =>
    (1 to map).map { count =>
      val newOccurence = (char, count)
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        newOccurence :: rest
      }
    }
  }.flatten.flatten.::(List())

你可以轻松地将其与上面的归纳食谱进行比较：

def combinations(occurrences: Occurrences): List[Occurrences] =
  occurrences.map { case (char, max) =>
    // for every character on the list of occurrences
    (1 to max).map { count =>
      // you construct (char, 1), (char, 2), ... (char, max)
      val newOccurence = (char, count)
      // and for each such occurrence
      combinations(occurrences filter {case (c, _) => c > char}).map { rest =>
        // you prepend it into every result from smaller subproblem
        newOccurence :: rest
      }
    }
  }
   // because you would have a List(List(List(List(...)))) here
   // and you need List(List(...)) you flatten it twice
  .flatten.flatten
  // and since you are missing empty result, you prepend it here
  .::(List())

您发布的解决方案以更紧凑的方式做完全相同的事情 - 而不是 .map().flatten，有 .flatMap 被 for-comprehension 隐藏。

Answer 2

我认为跟踪电话会帮助您更好地理解它。我将对步骤进行编号，以便轻松地在它们之间来回移动。

combinations(List(('a', 2), ('b', 2)))，我们先有：
```
(char, max) <- ('a', 2)
count <- 1
```
occurrences filter {case (c, _) => c > char} 的结果将是 List(('b', 2))。
因此我们现在计算combinations(List(('b', 2))):
```
(char, max) <- ('b', 2)
count <- 1
```
现在，occurrences filter {case (c, _) => c > char} 的结果将是 List()。
我们要计算combiantions(List()):

for 理解将是 List()，List() :: List() 的结果是 List()。因此我们回到第 2 步：
（第 2 步）我们有：
```
(char, max) <- ('b', 2)
count <- 1
```
现在我们没有休息的元素了。所以第 2 步的结果将是 List() :: List()，也就是 List()。回到第 1 步。所以我们将为该选项让步 List((char, count)) ++ rest) 即：List(('b', 1)) ++ List()) 即 List(('b', 1)) 我们现在处于同一调用的下一次迭代中：
```
(char, max) <- ('b', 2)
count <- 2
```
rest 将再次成为 List()，我们现在将屈服于该选项 List((char, count)) ++ rest)，即：List(('b', 2)) ++ List()) 即 List(('b', 2))。现在我们必须添加空列表，结果是：List(List(), List((b,1)), List((b,2))).
（第 1 步）我们有：
```
(char, max) <- ('a', 2)
count <- 1
```
现在我们有：
```
rest <- List()
```
所以我们得到 List((char, count)) ++ rest 即：List(('a', 1)) ++ List() 即：List(('a', 1))

现在我们继续：
```
rest <- List((b,1))
```
所以我们得到 List((char, count)) ++ rest 即：List(('a', 1)) ++ List((b,1)) 即：List(('a', 1), ('b', 1)).

现在我们继续：
```
rest <- List((b,2))
```
所以我们得到 List((char, count)) ++ rest 即：List(('a', 1)) ++ List((b,2)) 即：List(('a', 1), ('b', 2))。到目前为止的汇总结果是：
```
 List(List(('a', 1)), List(('a', 1), ('b', 1)), List(('a', 1), ('b', 2)))
```

现在max将增加到2，我们将在步骤2-4中进行相同的计算，这将产生，具有完全相同的逻辑：

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

而现在 (char, max) 将被更改为 ('b', 2)，这将导致它（在应用与步骤 2-4 相同的逻辑之后）：

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

将所有内容聚合在一起时，使用先前的空列表，我们得到了想要的输出。

真正有助于理解我刚才解释的是添加打印消息：

def combinations(occurrences: Occurrences): List[Occurrences] = {
  println("Starting with: " + occurrences)
  val result = List() :: (for {
    (char, max) <- occurrences
    count <- 1 to max
    rest <- combinations(occurrences filter {case (c, _) => c > char })
  } yield {
    val result = List((char, count)) ++ rest
    println("Occurrences are: " + occurrences + " Result is: " + result)
    result
  })
  println("Done with: " + occurrences + " results are: " + result)
  result
}

然后调用 println("Done: " + combinations(List(('a', 2), ('b', 2)))) 结果：

Starting with: List((a,2), (b,2))
Starting with: List((b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,2))
Done with: List((b,2)) results are: List(List(), List((b,1)), List((b,2)))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1), (b,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,1), (b,2))
Starting with: List((b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((b,2)) Result is: List((b,2))
Done with: List((b,2)) results are: List(List(), List((b,1)), List((b,2)))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2), (b,1))
Occurrences are: List((a,2), (b,2)) Result is: List((a,2), (b,2))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((a,2), (b,2)) Result is: List((b,1))
Starting with: List()
Done with: List() results are: List(List())
Occurrences are: List((a,2), (b,2)) Result is: List((b,2))
Done with: List((a,2), (b,2)) results are: List(List(), List((a,1)), List((a,1), (b,1)), List((a,1), (b,2)), List((a,2)), List((a,2), (b,1)), List((a,2), (b,2)), List((b,1)), List((b,2)))
Done: List(List(), List((a,1)), List((a,1), (b,1)), List((a,1), (b,2)), List((a,2)), List((a,2), (b,1)), List((a,2), (b,2)), List((b,1)), List((b,2)))

Scala Recursive For Comprehension 仅在空列表前添加一次，为什么？

Scala Recursive For Comprehension Prepends Empty List Only Once, Why?

scala

recursion

for-comprehension