递归如何满足基本情况 Haskell

Question

我试图理解这段html" target="_blank">代码，它返回传递给它的[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]]

在这里，我似乎无法理解递归最终将如何停止并返回[[]]，因为所有组合函数肯定没有任何指针在列表中移动，在每次调用时，当它满足基本情况[]时，它返回[[]。根据我的说法，它将调用所有组合函数无限，并且永远不会自行停止。或者可能是我错过了什么？

另一方面，take 在完成递归调用后返回返回所有计算后，仅返回最终列表中的前 7 个元素。那么，实际上递归如何满足这里的基本情况呢？

其次，这里的< code>concatMap的用途是什么，这里我们也可以使用< code>Map函数，只是将函数应用于列表，而在函数内部我们可以排列列表。< code>concatMap在这里究竟做了什么？根据定义，它< code>concatMap告诉我们，它首先映射函数，然后连接列表，我看到我们已经在函数中这样做了。

如有任何宝贵意见，将不胜感激？

Answer 1

匿名用户

它不是基本情况，而是特殊情况，这不是递归而是共递归，^（*）永远不会停止。

也许下面的重新表述会更容易理解:

allCombs :: [t] -> [[t]]
--        [1,2] -> [[]] ++ [1:[],2:[]] ++ [1:[1],2:[1],1:[2],2:[2]] ++ ...
allCombs vals = concat . iterate (cons vals) $ [[]]
    where
    cons :: [t] -> [[t]] -> [[t]]
    cons vals combs = concat [ [v : comb | v    <- vals]
                               |           comb <- combs ]

-- iterate   :: (a     -> a    ) -> a     -> [a]
-- cons vals ::  [[t]] -> [[t]]
-- iterate (cons vals)           :: [[t]] -> [[[t]]]
-- concat    ::                              [[ a ]] -> [ a ]
-- concat . iterate (cons vals)                      :: [[t]]

看起来不同，做同样的事情。不仅产生相同的结果，而且实际上正在做同样的事情来产生它们。^（*）Concat是相同的concat，你只需要稍微倾斜你的头就可以看到它。

这也说明了为什么这里需要concat。每个step=cons-vals都会产生一批新的组合，每个stepapplication的长度都会增加1，而concat将它们粘在一起，形成一个结果列表。

每个批次的长度是前一批次长度乘以< code>n，其中< code>n是< code > val 的长度。这也表明需要对< code>vals == []情况进行特殊处理，即< code>n == 0情况:< code>0*x == 0，因此每个新批次的长度为< code>0，因此试图从结果中再获得一个值将不会产生结果，即进入无限循环。在这一点上，该功能被认为是非生产性的。

顺便说一句，cons几乎与

                   == concat [ [v : comb | comb <- combs]
                               |           v    <- vals  ]
                   == liftA2 (:) vals combs

liftA2 :: Applicative f => (a -> b -> r) -> f a -> f b -> f r

因此，如果每个步骤结果的内部顺序对您来说并不重要（但请参阅帖子底部的重要警告），则可以将其编码为

allCombsA :: [t] -> [[t]]
--         [1,2] -> [[]] ++ [1:[],2:[]] ++ [1:[1],1:[2],2:[1],2:[2]] ++ ...
allCombsA   []   =  [[]]
allCombsA  vals  =  concat . iterate (liftA2 (:) vals) $ [[]]

< sup>(*)实际上，这是指它的一个修改版本，

allCombsRes vals = res
             where res = [] : concatMap (\w -> map (: w) vals)
                              res
-- or:
allCombsRes vals = fix $ ([] :) . concatMap (\w -> map (: w) vals)
--  where
--  fix g = x where x = g x     -- in Data.Function

或伪码：

 Produce a sequence of values `res` by
      FIRST producing `[]`, AND THEN
      from each produced value `w` in `res`, 
          produce a batch of new values `[v : w | v <- vals]`
          and splice them into the output sequence
               (by using  `concat`)

因此，res列表是协同递归生成的，从它的起点[]开始，基于前一个（s）生成它的下一个元素——无论是批量，如基于迭代的版本，还是像这里一样一个接一个，通过反向指针将输入带入先前生成的结果中（将其输出作为其输入，正如俗话说的那样——这当然有点欺骗性，因为我们以比我们生产它更慢的速度获取它，否则该过程将停止生产，如上所述）。

酪有时，通过递归调用产生输入可能是有利的，在运行时创建一系列函数，每个函数都将其输出沿链向上传递给调用者。尽管如此，数据流是向上的，不像常规递归那样首先向下流向基本情况。

刚才提到的优势与内存保留有关。协递归allCompsRes好像在它自己生成的序列中保留了一个后指针，因此序列不能被动态垃圾收集。

但是，由原始版本在运行时隐式创建的流生成器链意味着，当从每个下游元素生成新元素时，每个流生成器都可以进行垃圾收集，因此整个过程就相当于每个空间状态为O(1)的嵌套循环，以生成序列的第I个元素。

这比协递归/值递归allCompsRes的O（n）内存要求要好得多，它实际上在i/n位置将返回指针保留到其输出中。在实践中，对数空间要求最有可能被视为或多或少的O（1）空间要求。

这种优势只发生在您的版本中的生成顺序中，即在cons的中，而不是liftA2（：）的，它必须回到其输入序列的开头梳理（对于的中的每个新的v），因此必须保留，因此我们可以有把握地说，您的问题中的公式是相当巧妙的。

如果我们在寻找一个无点的重新公式——正如无点有时可以说明的那样——它确实是

allCombsY values =  _Y $ ([] :) . concatMap (\w -> map (: w) values)
    where
    _Y g = g (_Y g)      -- no-sharing fixpoint combinator

因此，在使用修复的公式中，代码更容易理解，然后我们只需使用语义上等效的_Y切换修复，以提高效率，从问题中获取（等效的）原始代码。

上述关于空间需求行为的声明很容易被检验。我还没有这样做。

另请参见:

• 为什么GHC让修复如此混乱？
• 共享与非共享定点组合器

Answer 2

@Lorenzo已经解释了关键点——递归实际上永远不会结束，因此这会生成一个无限列表，由于Haskell的懒惰，您仍然可以从中取出任意有限个元素。但我认为，更详细地介绍一下这一特殊功能及其工作原理会有所帮助。

首先，定义开头的[]：告诉您第一个元素始终是[]。当然，这是从＜code＞值的元素＜/code＞生成0元素列表的唯一方法。列表的其余部分是concatMap（\w-

concat映射f正如您所观察到的那样，它只是组合concat.（映射f）：它将给定函数应用于列表的每个元素，并将结果连接在一起。这里是函数（\w）-

(\w -> map (:w) values) [1,2] == [[1,1,2], [2,1,2]]

如果我们map该函数遍历列表列表，例如

[[], [1], [2]]

然后我们得到（仍然使用值作为[1,2]）：

[[[1], [2]], [[1,1], [2,1]], [[1,2], [2,2]]] 

这当然是列表列表的列表-但是concatMap的concatMap部分来拯救我们，展平最外层，并产生列表列表如下：

[[1], [2], [1,1], [2,1], [1,2], [2,2]]     

我希望你们可能已经注意到这一点的一件事是，我开始使用的列表列表不是任意的。[[]， [1]， [2]] 是起始列表 [1，2] 中大小为 0 或 1 的所有组合的列表。这实际上是所有组合的前三个元素[1，2]。

回想一下，在查看定义时，我们所知道的“确定”是这个列表的第一个元素将是[]。列表的其余部分是concatMap（\w-

allCombinations [1,2] == [] : [1] : [2] : concatMap (\w -> map (:w) values) [1,2] (tail (allCombinations [1,2]))

（tail在求值过程中并没有严格调用，而是通过模式匹配来完成的-我试图用文字来解释，而不是通过显式的单调等式）。

看看我们知道尾部是[1]：[2]： concatMap...。关键点是，在流程的每个阶段，我们都可以确定列表的前几个元素是什么——它们恰好是所有0元素列表，其值取自值，然后是所有具有这些值的1元素列表，然后是所有2元素列表，依此类推。一旦开始，该过程必须继续，因为传递给concatMap的函数确保我们只获取通过获取到目前为止生成的每个列表并附加值的每个元素而获得的列表到它们的前面。

如果您仍然对此感到困惑，请查看如何在Haskell中计算斐波那契数。获得所有斐波那契数的无限列表的经典方法是：

fib = 1 : 1 : zipWith (+) fib (tail fib)

这比< code>allCombinations的例子更容易理解，但本质上依赖于相同的东西——纯粹根据自身定义一个列表，但根据一个简单的规则，使用惰性求值来逐步生成尽可能多的列表。

Answer 3

简短回答：它永远不会满足基本情况。

但是，它不需要。基本情况是停止递归最常用的情况，但是这里您希望返回一个无限列表，因此无需停止它。

另一方面，如果您尝试获取＜code＞allCombination〔〕

main 函数的工作方式是它从空列表开始，然后在参数列表中的每个元素的开头追加。（：w） 以递归方式执行此操作。但是，仅此 lambda 将返回无限嵌套的列表。即：[]，[[真]，[假]]，[[[真，真]，[真，假]等。Concatmap 在每个步骤中都会删除外部列表，并且由于它是递归调用的，因此它只在末尾返回一个列表列表。这可能是一个需要掌握的复杂概念，因此请寻找使用concatMap的其他示例，并尝试了解它们的工作原理以及为什么仅靠地图是不够的。

这显然只是因为Haskell懒惰的评估。类似地，你知道在一个< code>foldr中，你需要向它传递基本情况，但是当你的函数应该只接受无限列表时，你可以将< code>undefined作为基本情况，以便更清楚地表明不应该使用有限列表。例如，可以使用< code>foldr f undefined来代替< code>foldr f []