[Haskell-cafe] Space usage and CSE in Haskell

[Simon Peyton-Jones]

| >   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.

I wonder if it'd be worth writing up this thread into a Wiki page?  Some neat programming here!

Simon