haskell - 生成集合的子集。懒惰？

Question

我编写了一个生成子集子集的函数。当我按以下方式使用子集[1..]时，它导致堆栈溢出。对于“正常”(非惰性)语言来说，这是“正常”行为。现在，我想改进我的懒惰功能。

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

附注2 请随意告诉我一些关于我在 Haskell 方面的缺陷的事情；)

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

Answer 1

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

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