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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
