Scala Recursive For Comprehension 只预置一次空列表，为什么? [英] Scala Recursive For Comprehension Prepends Empty List Only Once, Why?

问题描述

类似于这篇文章这里，我正在研究Scala 中的函数式编程"字谜课程作业.我无法弄清楚组合功能，但在其他地方找到了这个令人难以置信的优雅解决方案

similar to this post here, I am working on the "Functional Programming in Scala" Anagrams coursework. I could not figure out the combinations function, but found this incredibly elegant solution elsewhere

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 理解如何创建组合，但我不明白的是为什么在每次递归调用期间没有将空列表预先附加到每个内部列表.就好像编译器跳过了prepend语句，只执行右边的表达式.

I understand how the for the comprehension works to create the combinations, but what I do not understand is why the empty list is not pre-appended to every inner list during each recursive call. It's almost as if the compiler skips the prepend statement and only executes the right side for expression.

例如输入 combinations(List(('a', 2), ('b', 2))) 返回预期的结果集:

For example, the input combinations(List(('a', 2), ('b', 2))) returns the expected result set:

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

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

With only a single Empty list. Looking at the recursive call, I would expected another Empty list for each recursion. Would someone be so kind as to explain how this elegant solution works?

推荐答案

在这个里面没有任何东西产生一个空列表来理解.即使

There is nothing producing an empty list inside this for comprehension. Even if

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

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

contained an empty list and returned it in rest <- ... (it should for the first element), a value is prepended in List((char, count)) ++ rest making it non-empty by design.

所以整个 for-comprehension 必须返回一个非空的 List 的 List ，其中附加了一个空列表.

So the whole for-comprehension must return a List of non-empty Lists to which an empty list is prepended.

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

This basically builds solution by induction:

• 如果您有一个空列表 - 返回一个空列表，因为它是此输入的有效解决方案
• 如果你以 (char, maxOccurrences) :: rest 开头
  • 假设您有 combinations(rest)
  的有效解决方案
  • 然后采用每个这样的解决方案并将 (char, 1) 添加到 rest 的每个元素，
  • 然后采用每个这样的解决方案并将 (char, 2) 添加到 rest 的每个元素，
  • ...
  • 然后采用每个这样的解决方案并将 (char, maxOccurrences) 添加到 rest
  的每个元素
  • 然后将所有这些结果合并为一个解决方案
  • 所有这些都是非空的，因为你总是预先准备了一些东西
  • 因此您缺少空集，因此您将其显式添加到所有其他解决方案组合以创建 (char, maxOccurrences) :: rest
  的完整解决方案
  • if you have an empty list - return an empty list because it is a valid solution for this input
  • if you start with (char, maxOccurrences) :: rest
    • assume that you have a valid solution for combinations(rest)
    • then take each such solution and add (char, 1) to each element of rest,
    • then take each such solution and add (char, 2) to each element of rest,
    • ...
    • then take each such solution and add (char, maxOccurrences) to each element of rest
    • then combine all of these results into one solution
    • all of these are non-empty because you always prepended something
    • so you are missing empty set, so you add it explicitly to all the other solutions combined to create a complete solution for (char, maxOccurrences) :: rest

    因为你有一个有效的起点和一个有效的方法来创建下一步，你知道你总是可以创建一个有效的解决方案.

    Because you have a valid starting point and a valid way of creating next step from the previous, you know that you can always create a valid solution.

    为了理解

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

    您可以轻松地将其与上面的感应配方进行比较:

    and this you can easily compare to the induction recipe from above:

    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 隐藏-理解.

    The solution you posted does exactly the same thing just in more compacted way - instead of .map().flatten, there are .flatMaps hidden by a for-comprehension.

    这篇关于Scala Recursive For Comprehension 只预置一次空列表，为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！