Creating subsets of many. Laziness?

Question

I wrote a function that spawns a subset of a subset. This caused a stack overflow when I use the following subsets [1..] . And this is “normal” behavior when it comes to “normal” (without lazy) languages. And now I would like to improve my function to be lazy.

PS I do not understand laziness (and I'm trying to understand it), so maybe my problem is strange for you - explain. :)

PS 2 Feel free to tell me something about my disability at Haskell;)

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

Answer 1

There are two problems with this feature. Firstly, it is repeated twice, which makes it exponentially more inefficient than necessary (if you do not take into account the exponential number of results ...), since each subtree is recounted every time for all overlapping subsets; this can be fixed with let , when the recursive call has the same value:

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

This will already allow you to calculate length $ subsets' [1..25] in a few seconds, and length $ subsets [1..25] will take ... well, I did not wait;)

Another problem is that with your version, when you give it an infinite list, it first recurses on the infinite tail of that list. In order to generate all finite subsets in a meaningful way, we need to provide two things: first, we must create each set of smaller sets (to ensure completion), and secondly, we must ensure a fair order (i.e. do not generate a list [[1], [2], ...] first and never reach the rest). To do this, we start with [[]] and recursively add the current element to everything that 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 _ [] = [] 

This leads to the following 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]] 

Answer 2

You cannot generate all subsets of an infinite set: they form an uncountable set. Due to cardinality, this is not possible.

In the best case, you can try to generate all the finite subsets. For this, you cannot act by induction starting with [] , since you will never reach [] . You need to continue inductively from the beginning of the list, not end.

Answer 3

The correct folding solution will be:

 powerset :: Foldable t => ta -> [[a]] powerset xs = []: foldr go (const []) xs [[]] where go xfa = let b = (x:) <$> a in b ++ f (a ++ b) 

then

 \> take 8 $ powerset [1..] [[],[1],[2],[2,1],[3],[3,1],[3,2],[3,2,1]]