[Haskell-cafe] Space usage and CSE in Haskell

Bertram Felgenhauer bertram.felgenhauer at googlemail.com
Thu Jul 26 14:16:56 EDT 2007

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



More information about the Haskell-Cafe mailing list