| 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