Bertram Felgenhauer wrote two wonderful implementations of power_list:
power_list :: [a] -> [[a]]
power_list [] = [[]]
power_list (x:xs) = add_x (assert_first_empty $ power_list xs) x
where assert_first_empty ~([]:xs) = []:xs
add_x [] _ = []
add_x (y:ys) x = y : (x:y) : add_x ys x
It's safe to replace the ~([]:xs) by ~(_:xs) - this should result
in slightly more efficient code (but I did no timings).
With GHC, it seems to make no observable difference.
Finally for lovers of oneliners, here's the same code with foldr,
slightly obscured by using >>= for concatMap:
power_list :: [a] -> [[a]]
power_list = foldr (\x ~(_:xs) -> []:xs >>= \ys -> [ys, x:ys]) [[]]
I loved how short and sweet this version is, but sadly with GHC it's
noticeably slower than Bertram's first, more directly coded, version
(1.32 seconds vs 0.55 seconds for power_list [1..24]).
The two-line variant below is just over 25% faster than the above
oneliner under GHC, but at 1.04 seconds, it's still bested by the
explicit version:
power_list :: [a] -> [[a]]
power_list [] = [[]]
power_list (x:xs) = [] : tail [y | ps <- power_list xs, y <- [ps,
x:ps]]
Anyway, we're now far from our original topic, but thanks to Bertram,
we can see that power_list can be coded in a way that is memory
efficient, lazy-list friendly, and (relatively) easy to read.
Best Regards,
Melissa.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
