Scala递归for推导仅在开头加入空列表一次，为什么？

Question

类似于这篇文章，我正在处理“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)))返回预期的结果集：

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)))

只有一个空列表。看着这个递归调用，我本应该期望每次递归都有另一个空列表。请问是否有好心人能够解释一下这个优雅的解决方案是如何工作的？

- Jonny Waffles

---

请注意，List((char, count)) ++ res 会使整个过程极其低效。请改为使用 (char, count) :: res。 - Luis Miguel Mejía Suárez

:: results in a type error found : List[List[Equals with java.io.Serializable]] required: List[forcomp.Anagrams.Occurrences] (which expands to) List[List[(Char, Int)]] List() :: (for {``` - Jonny Waffles

不，它不会：https://scastie.scala-lang.org/BalmungSan/SwM22gLuRt2rmpz2h6EFDA/8 - 顺便说一下，“combinations2”是我自己解决问题的方法。 - Luis Miguel Mejía Suárez

啊，我明白了，谢谢。 - Jonny Waffles

Jonny，请阅读当有人回答我的问题时我该怎么做？。 - Tomer Shetah

Answer 1

在这个for循环理解中没有产生空列表。即使

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

在 rest <- ... 中返回一个空列表（对于第一个元素应该这样做），通过设计，在 List((char, count)) ++ rest 中添加一个值使其成为非空列表。

因此，整个 for-comprehension 必须返回一个非空 List 的列表，其中将一个空列表放在前面。

基本上，这是通过归纳建立解决方案的：

• 如果你有一个空列表——返回一个空列表，因为这是这个输入的有效解决方案
• 如果你以 (char, maxOccurrences) :: rest 开始
  • 假设你已经有了 combinations(rest) 的有效解决方案
  • 然后取每个这样的解决方案，并向每个 rest 元素添加 (char, 1),
  • 然后取每个这样的解决方案，并向每个 rest 元素添加 (char, 2),
  • ...
  • 然后取每个这样的解决方案，并向每个 rest 元素添加 (char, maxOccurrences)
  • 然后将所有这些结果组合成一个解决方案
  • 所有这些都是非空的，因为你总是在前面添加了东西
  • 因此，你缺少空集，所以你明确地将其添加到所有其他组合来创建一个完整的解决方案 (char, maxOccurrences) :: rest

因为你有一个有效的起点和一种从先前创建下一个步骤的有效方式，所以你知道你总是可以创建一个有效的解决方案。

在 for-comprehension 中

  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 相比，只是以更紧凑的方式实现了相同的功能 - 在 for-推导式中隐藏了 .flatMap。

- Mateusz Kubuszok

---

当你写下以下内容时：“即使rest包含一个空列表并在rest <- ...中返回它（对于第一个元素应该如此），在List((char，count)) ++ rest中添加一个值，从而通过设计使其非空。”我不明白为什么rest不总是包含空列表，因为前置是出现的第一步。每次我们向rest添加东西时，难道不会包括那个空列表吗？ - Jonny Waffles

Answer 2

我认为跟踪通话记录可以帮助您更好地理解它。我将编号步骤，以便轻松地来回切换。

1. combinations(List(('a', 2), ('b', 2))), we have first:

   (char, max) <- ('a', 2)
   count <- 1
   

   The result of occurrences filter {case (c, _) => c > char} will be List(('b', 2)).

2. Therefore we now calculate combinations(List(('b', 2))):

   (char, max) <- ('b', 2)
   count <- 1
   

   Now, the result of occurrences filter {case (c, _) => c > char} will be List().

3. We are going to calculate combiantions(List()):

   The for comprehension will be List(), and List() :: List() results in List(). Therefore we are back in step 2:

4. (step 2) We had:

   (char, max) <- ('b', 2)
   count <- 1
   

   and now we have no elements for rest. So the result of step 2 will be List() :: List() which is List() as well. Back to step 1. So we are going to yield for that option List((char, count)) ++ rest) which is: List(('b', 1)) ++ List()) which is List(('b', 1)) We are now in the next iteration of the same call with:

   (char, max) <- ('b', 2)
   count <- 2
   

   rest will be List() again and we are now going to yield for that option List((char, count)) ++ rest) which is: List(('b', 2)) ++ List()) which is List(('b', 2)). Now we have to add the empty list, and the result is: List(List(), List((b,1)), List((b,2))).

5. (step 1) We had:

   (char, max) <- ('a', 2)
   count <- 1
   

   and now we have:

   rest <- List()
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List() which is: List(('a', 1))

   Now we continue to:

   rest <- List((b,1))
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List((b,1)) which is: List(('a', 1), ('b', 1)).

   Now we continue to:

   rest <- List((b,2))
   

   So we are yielding List((char, count)) ++ rest which is: List(('a', 1)) ++ List((b,2)) which is: List(('a', 1), ('b', 2)). The aggregated result so far is:

    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)))

- Tomer Shetah