10 Jun
2003
10 Jun
'03
11:14 a.m.
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.
Just a word of warning: using GHCi or Hugs for comparison benchmarking will give unreliable results. Use GHC with -O. Cheers, Simon