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

Question

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

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

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

Answer 1

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

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

包含一个空列表并在 rest <- ... 中返回它(它应该用于第一个元素)，在 List((char, count)) ++ rest 中添加一个值通过设计使其非空。

所以整个 for-comprehension 必须返回一个 List的非空List s 前面有一个空列表。

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

• 如果您有一个空列表 - 返回一个空列表，因为它是此输入的有效解决方案
• 如果您以 (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 s 隐藏在 for-comprehension 中。