# Deriving the function to compute sublists of a list

Submitted by metaperl on Wed, 10/26/2005 - 12:42pm.

Earlier I discussed how `=` in Haskell is equational. Well, it certainly came to the rescue this time. I was trying to understand the given solution in "The Haskell Road to Logic, Maths, and Programming" for the problem of calculating all the sublists of a list.

``` powerList [] = [ [] ] powerList (x:xs) = powerList xs ++ (map (x:) powerList xs) ```

So I looked at this program, but had no idea how in the world this was the solution. So what I did is I worked upwards from the most trivial case like so:

-- The powerlist of a list with no elements is a list consisting of
-- the empty list

powerList [] = [[]]

-- Now, let's work with a list with 1 element:

powerList [a] = [ [a], [] ]

-- Fair enough, now how about a list with 2 elements:

powerList [a,b] = [ [a,b], [b], [a], [] ]

-- Hmm, but let's rewrite that

[ [a,b], [b], [a], [] ] = powerList [a] ++ [ [a, b], [b] ]

-- And rewrite once again

powerList [a] ++ [ [a, b], [b] ] = powerList [a] ++ (map (b:) powerList [a])

-- Now let's try 3 elements just to make sure we have a pattern:

powerList [c,a,b] = [[c,a,b], [c,b], [c,a], [c]] ++ powerList [a,b]

-- but with order independance we have:

powerList [c,a,b] = powerList [a,b] ++ [[c,a,b], [c,b], [c,a], [c]]

-- but [[c,a,b], [c,b], [c,a], [c]] = map (c:) powerList [a,b] so:

powerList [c,a,b] = powerList [a,b] ++ map (c:) powerList [a,b]

-- generalizing we have:

powerList (x:xs) = powerList xs ++ (map (x:) powerList xs)

Without going through it backwards like that, doesn't something like this make sense?
"Math says ℘(∅)={∅}, so `powerList [] = [[]]`."
"℘({x,x1,x2..}) can be split into
{ p | p ∈ ℘({x1,x2..}) }  — i.e. power sets without x
∪  — plus
{ {x} ∪ p | p ∈ ℘({x1,x2..}) }  — i.e. power sets with x.
That translates into `powerList (x:xs) = [p | p <- powerList xs] ++ [[x] ++ p | p <- powerList xs]`.
That can be better written as `powerList (x:xs) = powerList xs ++ map (x:) (powerList xs)`."

This one might be easier or harder to reason, depending on how you think.  Don't use it, it's a lot less efficient, though it does return results in a more natural order.
```choose 0 _      = [[]] choose n (x:xs) = map (x:) (choose (n - 1) xs) ++ choose n xs choose _ _      = [] powerList l     = concat \$ map (`choose` l) [0 .. length l]```