[Haskell-cafe] Space usage and CSE in Haskell

[Melissa O'Neill]

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.