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