powerset

[Keith Wansbrough]

> A brief search of the libraries didn't reveal (top me) a ready-to-roll 
> powerset function.
> 
> I thought this may be a useful exercise to see how well I'm picking up on 
> functional programming idioms, so I offer the following for comment:
[..]
> I think the recursive use of 'combinations' may be inefficient, and could 
> maybe be improved by "memoizing"?

Looks fine, but you're right - the use of "combinations" is
inefficient.  It's better to iterate over the elements, rather than
the length.  Then as you add each element, you consider all the sets
you have so far, and either add the new element to each or not.  This
doubles the number of sets.  Hence:

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

Notice how important it is to include the empty set in the set of
subsets - it won't work at all if you omit it.

This formulation is particularly nice because in memory, you *share*
all of the lists from the previous iteration, rather than making
copies.  After doing "powerset [1,2,3,4]", the heap looks something
like this:

let a = []
    b = 1:a

    c = 2:a
    d = 2:b

    e = 3:a
    f = 3:b
    g = 3:c
    h = 3:d

    i = 4:a
    j = 4:b
    k = 4:c
    l = 4:d
    m = 4:e
    n = 4:f
    o = 4:g
    p = 4:h
in
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p]

Notice all the sharing - this is a very efficient representation!  You
save on copying, and you save on memory use.


My solution isn't perfect, though - the use of append (++) is
inefficient; if this could be avoided, it would be faster.

--KW 8-)