生成集合的子集。懒惰？

Question

我编写了一个生成子集子集的函数。当我以下列方式使用时，它导致堆栈溢出subsets [1..]。当涉及到“正常”（非懒惰）语言时，这是“正常”行为。现在，我想改进我的功能，使其变得懒惰。

PS我不理解懒惰（我试图理解它）所以也许我的问题对你来说很奇怪 - 请解释一下。:)

PS 2 请随意谈谈我在 Haskell 中的残疾情况；)

subsets :: [a] -> [[a]]
subsets (x:xs) = (map (\ e -> x:e) (subsets xs)) ++ (subsets xs)
subsets [] = [[]]

Answer 1

该功能有两个问题。首先，它递归了两次，这使得它比必要的效率低得多（如果我们忽略结果的指数数量......），因为每次都为所有重叠子集重新计算每个子树；这可以let通过将递归调用设为相同值来解决：

subsets' :: [a] -> [[a]]
subsets' [] = [[]]
subsets' (x:xs) = let s = subsets' xs
                  in map (x:) s ++ s

这已经可以让你length $ subsets' [1..25]在几秒钟内计算出来，而length $ subsets [1..25]需要......好吧，我没有等;）

另一个问题是，对于您的版本，当您给它一个无限列表时，它将首先在该列表的无限尾部递归。为了以有意义的方式生成所有有限子集，我们需要确保两件事：首先，我们必须从较小的集合构建每个集合（以确保终止），其次，我们应该确保一个公平的顺序（即，不生成[[1], [2], ...]首先列出，永远不要进入其余部分）。为此，我们从[[]]当前元素开始并将其递归添加到我们已经生成的所有内容中，然后记住下一步的新列表：

subsets'' :: [a] -> [[a]]
subsets'' l = [[]] ++ subs [[]] l
  where subs previous (x:xs) = let next = map (x:) previous
                               in next ++ subs (previous ++ next) xs
        subs _ [] = []

结果按此顺序：

*Main> take 100 $ subsets'' [1..]
[[],[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1],[4],[4,1],[4,2],[4,2,1],[4,3],[4,3,1],[4,3,2],[4,3,2,1],[5],[5,1],[5,2],[5,2,1],[5,3],[5,3,1],[5,3,2],[5,3,2,1],[5,4],[5,4,1],[5,4,2],[5,4,2,1],[5,4,3],[5,4,3,1],[5,4,3,2],[5,4,3,2,1],[6],[6,1],[6,2],[6,2,1],[6,3],[6,3,1],[6,3,2],[6,3,2,1],[6,4],[6,4,1],[6,4,2],[6,4,2,1],[6,4,3],[6,4,3,1],[6,4,3,2],[6,4,3,2,1],[6,5],[6,5,1],[6,5,2],[6,5,2,1],[6,5,3],[6,5,3,1],[6,5,3,2],[6,5,3,2,1],[6,5,4],[6,5,4,1],[6,5,4,2],[6,5,4,2,1],[6,5,4,3],[6,5,4,3,1],[6,5,4,3,2],[6,5,4,3,2,1],[7],[7,1],[7,2],[7,2,1],[7,3],[7,3,1],[7,3,2],[7,3,2,1],[7,4],[7,4,1],[7,4,2],[7,4,2,1],[7,4,3],[7,4,3,1],[7,4,3,2],[7,4,3,2,1],[7,5],[7,5,1],[7,5,2],[7,5,2,1],[7,5,3],[7,5,3,1],[7,5,3,2],[7,5,3,2,1],[7,5,4],[7,5,4,1],[7,5,4,2],[7,5,4,2,1],[7,5,4,3],[7,5,4,3,1],[7,5,4,3,2],[7,5,4,3,2,1],[7,6],[7,6,1],[7,6,2],[7,6,2,1]]