# powerset

**Graham Klyne
**
GK@ninebynine.org

*Fri, 06 Jun 2003 12:47:41 +0100*

At 20:25 05/06/03 -0700, Mark P Jones wrote:
>*Or, if duplicated computation offends you, replace (++) in the
*>*original version of powerset with an interleave operator:
*>*
*>* 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 :-)
*
Interesting...
Picking up my theme or generating the powersets in increasing order of
length, I tried a variation on that:
[[
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.
#g
-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E