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