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.