# Deriving the function to compute sublists of a list

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)

- metaperl's blog
- Login to post comments

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]