[Haskell-cafe] Space usage and CSE in Haskell

[Bertram Felgenhauer]

Melissa O'Neill wrote:
> BUT, it generates the output in an order that'll accommodate infinite  
> lists, thus we can say:
> 
>    power_list [1..]
> 
> -- Count in binary and use that to create power set
> power_list xs = loop zero where

[snip code that works lazily without wasting memory and supporting
infinite lists.]

> No doubt this can be coded better yet...

How about this: Start with

  power_list :: [a] -> [[a]]
  power_list []     = [[]]
  power_list (x:xs) = add_x (power_list xs)
     where add_x []     = []
           add_x (y:ys) = y : (x:y) : foo ys

Note that this puts the empty list first. The only change that is
necessary to make this work for infinite list is to tell the compiler
to assert that the recursive call does the same thing - this can be
done with a lazy pattern:

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

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]) [[]]

Enjoy,

Bertram