递归如何满足基本情况Haskell

Question

我试图理解这段代码，该代码返回[a]传递给它的所有可能的组合：

-- Infinite list of all combinations for a given value domain
allCombinations :: [a] -> [[a]]
allCombinations []     = [[]]
allCombinations values = [] : concatMap (\w -> map (:w) values)
                                        (allCombinations values)

在这里，我尝试了此示例输入：

ghci> take 7 (allCombinations [True,False])
[[],[True],[False],[True,True],[False,True],[True,False],[False,False]]

在我看来，递归最终将如何停止并返回是无法理解的[ [ ] ]，因为allCombinations函数当然没有任何指针在列表中移动，每次调用以及在遇到基本情况时[ ]都会返回[ [ ] ]。据我说，它将调用allCombinations函数无限，并且永远不会停止。还是我想念什么？

另一方面，在执行完所有计算之后，在递归调用完成之后返回，仅在执行所有计算后，take仅返回第一个7元素final list。那么实际上递归如何满足这里的基本情况？

其次concatMap，这里的目的是什么，在这里我们还可以使用Mapfunction来将函数应用于列表，而在内部函数中我们可以排列列表？实际concatMap在这里做什么。从定义来看，它concatMap告诉我们它首先映射了函数，然后将列表连接起来，正如我所看到的，我们已经在函数内部进行了此操作？

任何宝贵的意见将不胜感激？

Answer 1

简短的答案：它将永远无法满足基本情况。

但是，它并不需要。最常需要基本情况​​来停止递归，但是在这里您想返回一个无限列表，因此无需停止它。

另一方面，如果您尝试使用多个元素中的1个，则会破坏此功能allCombination []-请查看@robin的答案以更好地理解原因。这是您在此处看到基本情况的唯一原因。

主要功能的工作方式是从一个空列表开始，然后在参数列表中的每个元素的开头追加。（:w）递归执行。但是，仅此lambda会返回无限嵌套的列表。即：[],[[True],[False]],[[[True,True],[True,False]等。Concatmap在每个步骤中都删除外部列表，并且由于递归调用，因此最后只返回一个列表列表。这可能是一个很难理解的概念，因此请寻找其他使用示例，concatMap并尝试了解它们的工作原理以及map仅凭其作用还不够。

显然这仅是由于Haskell懒惰的评估而起作用。类似地，您知道foldr您需要将基本情况传递给它，但是当您的函数只接受无限列表时，您可以undefined作为基本情况来更清楚地表明不应使用有限列表。例如，foldr f undefined可以代替foldr f []