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)

Submitted by dtlin on Fri, 10/28/2005 - 9:11am.

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]

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.