= Solution
Each entry contributes a choice between omission and inclusion. Use <list concatenation> as $\oplus$, so that <Cartesian lifting of a binary operation to lists> joins every choice from an earlier position to every choice from later positions:
``
crossAppend :: [[a]] -> [[a]] -> [[a]]
crossAppend xss yss = [xs ++ ys | xs <- xss, ys <- yss]
f :: a -> [[a]]
f x = [[],[x]]
subs :: [a] -> [[a]]
subs xs = foldr crossAppend [[]] (map f xs)
``
The seed is `[[]]`, because the empty <list> has one <subsequence>, namely `[]`, and concatenating the empty <list> changes nothing. If `rest` lists the <subsequences> of the tail, `crossAppend [[],[x]] rest` lists all omissions of `x` first and all inclusions second. For `[a,b,c]`, the last position changes fastest, producing the specified order `[], [c], [b], [b,c], [a], [a,c], [a,b], [a,b,c]`. Repeated input values can give equal <subsequences> at distinct choices of positions; those repetitions are retained. Thus
$$
\boxed{\operatorname{subs}=\operatorname{foldr}\ X_{++}\ [[]]\circ\operatorname{map}f.}
$$
Back to article page
