Powerset

[Graham Klyne]

That's very similar to a version I received in an offlist email, which I 
had been seeking permission to repost.  I find this approach to be very 
elegant.

#g
--

At 14:53 10/06/03 +0200, Christian Maeder wrote:
>powerset :: [a] -> [[[a]]]
>powerset [] = [[[]]]
>powerset (x:xs) = [[]] : myzip x (powerset xs)
>
>myzip :: a -> [[[a]]] -> [[[a]]]
>myzip x [a] = [map (x:) a]
>myzip x (a:b) = (map (x:) a ++ head b) : myzip x b
>
>I suggest the above version for a sorted powerset. The result keeps a 
>further nesting of lists for subsets of the same length. (Flatten this 
>list with "concat".)
>
>Call "length (concat (powerset [1..19]))" (on Hugs).
>
>Christian
>
>oleg@pobox.com wrote:
>>The following seems to be a faster version of powerset that delivers
>>results strictly in the order of increasing cardinality (i.e., all
>>sets of size 1 first, then of size 2, etc). It seems to run faster
>>than any other ordered version of powerset posted so far. On GHCi,
>>length $ powerset [1..22] is computed roughly 4 times faster than
>>powerset3 given earlier. On Hugs, the powerset below also runs faster,
>>with less memory consumption and in fewer GC cycles, up to a limit of
>>18 for the size of the input set. Then something happens. length $
>>powerset3 [1..19] runs out of memory on my (not current) version of
>>Hugs too.
>>The algorithm is more complex, though.
>>powerset [] = [[]]
>>powerset [x] = [[],[x]]
>>powerset xs = [] : runit (tail rsxtails) ps0
>>    where
>>         xstails = tails xs
>>         rsxtails = reverse xstails
>>         ps0 = map (const [[]]) xstails
>>         psn tn psn1 = psnew
>>            where
>>             psnew = [tn]:
>>              (zipWith (++)
>>               (reverse (zipWith (\x psn1i -> map (x:) psn1i) xs (tail $ 
>> reverse$tail $ psn1)))
>>               psnew)
>>         runit [tn] _ = [xs]
>>         runit (tn:tns) psn1 = (last newps) ++ (runit tns newps)
>>             where newps = psn tn psn1
>>_______________________________________________
>>Haskell-Cafe mailing list
>>Haskell-Cafe@haskell.org
>>http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe@haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe

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