powerset

[Graham Klyne]

At 20:25 05/06/03 -0700, Mark P Jones wrote:
>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 :-)

Interesting...

Picking up my theme or generating the powersets in increasing order of 
length, I tried a variation on that:

[[
powerset3       :: [a] -> [[a]]
powerset3 []     = [[]]
powerset3 (x:xs) = xss <<< map (x:) xss
                 where xss = powerset3 xs

(<<<)        :: [[a]] -> [[a]] -> [[a]]
[]     <<< ys     = ys
xs     <<< []     = xs
(x:xs) <<< (y:ys) = if length x < length y
                         then x:(xs <<< (y:ys))
                         else y:((x:xs) <<< ys)

testJ1 = powerset3 [1,2,3,4]
testJ2 = powerset3 "abcdefgh"
]]

(The length-ordered interleave is a bit clumsy -- I think that could be 
improved by saving the length with each powerset as it's generated, or by 
other means.)

Empirically, I notice that this still seems to leak *some* space compared 
with your version, but not nearly as much as the simple version.  I also 
notice, empirically, that these interleaving versions invoke garbage 
collection much more frequently than the naive version.

#g


-------------------
Graham Klyne
<GK@NineByNine.org>
PGP: 0FAA 69FF C083 000B A2E9  A131 01B9 1C7A DBCA CB5E