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.