[Haskell-cafe] Space usage and CSE in Haskell
simonpj at microsoft.com
Mon Jul 30 04:01:45 EDT 2007
| > 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,
| 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!
More information about the Haskell-Cafe