More efficient powerset algorithm haskell

Question

I Have a powerset function which creates a list [[a]] but the largest [a] is worked out first, meaning the whole algorithm has to run before I can get the smaller values.

I need a function which returns a powerset, in ascending order, so I could take the first n values of the function and the whole algorithm would not need to run.

Current simple algorithm

powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = [x:ps | ps <- powerset xs] ++ powerset xs

Answer 1

I don't understand what you mean by ascending order, but consider this solution:

powerset' :: [a] -> [[a]]
powerset' = loop [[]]
  where
    loop :: [[a]] -> [a] -> [[a]]
    loop acc [] = acc
    loop acc (x:xs) = loop (acc ++ fmap (\e -> e ++ [x]) acc) xs

We start with the powerset of the empty list, which is [[]], and expand it for each new element we encounter in the input list. The expansion is by appending the new element in each sublist we already emitted.

It requires that we append elements to the sublists exponentially many times, so I also considered using Data.DList from the dlist package that provides an efficient snoc operator that appends new elements to the end of the list:

import Data.DList

powerset :: [a] -> [[a]]
powerset xs = toList <$> loop [empty] xs
  where
    loop :: [DList a] -> [a] -> [DList a]
    loop acc [] = acc
    loop acc (y:ys) = loop (acc ++ fmap (`snoc` y) acc) ys

In my (rough) experiments, though, the first solution uses way less memory in the REPL and thus finishes faster for bigger input lists.

In both cases, this is what you get at the end:

$> powerset [1,2,3]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

$> powerset_original [1,2,3]
[[1],[1,2],[1,3],[1,2,3],[],[2],[3],[2,3]]