powerset

[Andrew J Bromage]

G'day all.

On Wed, Jun 04, 2003 at 02:00:08PM +0100, Keith Wansbrough wrote:

> This formulation is particularly nice because in memory, you *share*
> all of the lists from the previous iteration, rather than making
> copies.
[...]
> Notice all the sharing - this is a very efficient representation!  You
> save on copying, and you save on memory use.

I can never resist a can labelled "worms".  Let me get out my tin
opener...

You do save on memory allocations.  If, however, you consume the list
lazily and discard the results as you consume them (which is the
common way lazy programs are written), you actually use more memory
at once.

Try it if you don't believe me.  Test it with this program, using
each definition of powerset:

	summer :: [[a]] -> Integer
	summer xss = foldl' (\xs r -> r + toInteger (length xs)) 0 xss

	n :: Int
	n = 32

	main :: IO ()
	main = print (summer (powerset [1..n]))

You'll find that one of them runs in O(n) space and the other most
likely blows the heap.

Cheers,
Andrew Bromage