powerset

[Christian Maeder]

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = concatMap ( \ s -> s:[x:s]) (powerset xs)

this variant behaves as well, doesn't it?

>>    powerset       :: [a] -> [[a]]
>>    powerset []     = [[]]
>>    powerset (x:xs) = xss /\/ map (x:) xss
>>                     where xss = powerset xs
>>
>>    (/\/)        :: [a] -> [a] -> [a]
>>    []     /\/ ys = ys
>>    (x:xs) /\/ ys = x : (ys /\/ xs)
>>
>> These two variants both run in constant space (assuming that
>> your compiler isn't "smart" enough to do common subexpr
>> elimination :-)

> Picking up my theme or generating the powersets in increasing order of 
> length, I tried a variation on that:

powerset :: [a] -> [(Int, [a])]
powerset [] = [(0, [])]
powerset (x:xs) = myconcat $ map ( \ s -> (s, (fst s + 1, x: snd s)))
				 $ powerset xs

myconcat :: [((Int, [a]), (Int, [a]))] -> [(Int, [a])]
myconcat [(a,b)] = [a, b]
myconcat (x:r) = insert x $ myconcat r

insert :: ((Int, [a]), (Int, [a])) -> [(Int, [a])] -> [(Int, [a])]
insert (a@(i,_), b) l@(c@(j, _) : r) =
     if i < j then a : b : l
        else c : insert (a, b) r

However,  length (powerset [1..32]) in Hugs ends in an:
ERROR - Control stack overflow

Cheers Christian

> 
> [[
> powerset3       :: [a] -> [[a]]
> powerset3 []     = [[]]
> powerset3 (x:xs) = xss <<< map (x:) xss
>                 where xss = powerset3 xs
> 
> (<<<)        :: [[a]] -> [[a]] -> [[a]]
> []     <<< ys     = ys
> xs     <<< []     = xs
> (x:xs) <<< (y:ys) = if length x < length y
>                         then x:(xs <<< (y:ys))
>                         else y:((x:xs) <<< ys)
> 
> testJ1 = powerset3 [1,2,3,4]
> testJ2 = powerset3 "abcdefgh"
> ]]
> 
> (The length-ordered interleave is a bit clumsy -- I think that could be 
> improved by saving the length with each powerset as it's generated, or 
> by other means.)
> 
> Empirically, I notice that this still seems to leak *some* space 
> compared with your version, but not nearly as much as the simple 
> version.  I also notice, empirically, that these interleaving versions 
> invoke garbage collection much more frequently than the naive version.