生成集合的子集.懒惰? [英] Generating subsets of set. Laziness?

问题描述

我写了一个生成子集子集的函数.当我按以下方式使用subsets [1..]时，它导致了堆栈溢出.当涉及到正常"(无延迟)语言时，这是正常"行为.现在，我想改善自己的功能以变得懒惰.

I have written a function generating subsets of subset. It caused stack overflow when I use in the following way subsets [1..]. And it is "normal" behaviour when it comes to "normal" (no-lazy) languages. And now, I would like to improve my function to be lazy.

P.S.我不理解懒惰(并且我试图理解它)，所以也许我的问题对您来说很奇怪-请解释. :)

P.S. I don't understand laziness ( And I try to understand it) so perhaps my problem is strange for you- please explain. :)

P.S. 2随便对我说说我在Haskell的残疾问题；)

P.S. 2 Feel free to say me something about my disability in Haskell ;)

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

推荐答案

该函数有两个问题.首先，它递归两次，这使它效率成倍地提高了效率(如果不考虑结果的指数数...)，因为每次都为所有重叠的子集重新计算每个子树.可以通过let将递归调用设置为相同的值来解决此问题:

There's two problems with that function. First, it recurses twice, which makes it exponentially more ineffiecient than necessary (if we disregard the exponential number of results...), because each subtree is recalculated every time for all overlapping subsets; this can be fixed by leting the recursive call be the same value:

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

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

This will already allow you to calculate length $ subsets' [1..25] in a few seconds, while length $ subsets [1..25] takes... well, I didn't wait ;)

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

The other issue is that with your version, when you give it an infinite list, it will recurse on the infinite tail of that list first. To generate all finite subsets in a meaningful way, we need to ensure two things: first, we must build up each set from smaller sets (to ensure termination), and second, we should ensure a fair order (ie., not generate the list [[1], [2], ...] first and never get to the rest). For this, we start from [[]] and recursively add the current element to everything we have already generated, and then remember the new list for the next step:

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

按以下顺序排列的结果:

Which results in this order:

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

这篇关于生成集合的子集.懒惰?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！