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