# powerset

**Christian Maeder
**
maeder@tzi.de

*Fri, 06 Jun 2003 17:38:50 +0200*

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