powerset

[Mark P Jones]

| powerset :: [a] -> [[a]]
| powerset [] = [[]]
| powerset (x:xs) = xss ++ map (x:) xss
|                 where xss = powerset xs

Elegant as it is, this program causes a serious space leak.
(In fact, it is often cited as an example of why functional
programming language implementations might choose not to use
common subexpression elimination.)

Why?  Because it holds on to the whole of xss until the first
half of the resulting list has been generated.  And xss gets
big, fast.  In Hugs, try:

   :set +g
   length (powerset [1..32])

and watch as your free heap disappears ...

One way to fix this is to rewrite the second line in the
definition of powerset as:

   powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)

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 :-)

All the best,
Mark