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]