All possible sublists of a list

Question

I need to write a function that generates a list containing lists of all the possible sublists of a list. So the type must be:

partitions :: [a] -> [[[a]]]

and it should give:

partitions [1..4] = [[[1],[2],[3],[4]], [[1,2],[3],[4]], [[1],[2,3],[4]], [[1,2,3],[4]], [[1],[2],[3,4]], [[1,2],[3,4]], [[1],[2,3,4]], [[1,2,3,4]]]

I'm thinking a list comprehension is the best way to go. So far I have:

partitions :: [a]  -> [[[a]]]
partitions (x:xs) = foldr insert [[]] (x:xs)
   where insert ys zs = ys:x:zs

This throws up type errors as you would expect, but I don't know how to fix it. I feel I'm missing something obvious, any help would be appreciated.

Answer 1

I would start with a direct recursion. Break it down, what possibilities are there for the first element in a longer list?

1. It can be the only element of one of the partition lists.
2. It can be part of a partition list with more than one element.

From your example, it seems you want to keep the original elements in order, so the members of each partition can only be contiguous sublists, which makes it somewhat easier.

So we can start

partitions :: [a] -> [[[a]]]
partitions [] = [[]]    -- only one partition of an empty list, an empty partition
partitions (x:xs) = [[x]:part | part <- partitions xs] ++ [(x:ys):yss | (ys:yss) <- partitions xs]

which yields

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1],[2],[3,4]],[[1],[2,3],[4]],[[1],[2,3,4]],[[1,2],[3],[4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4]]]

not the desired order. If that matters, we have to rewrite. The desired order lists both choices for the first element in direct succession, so we could write it

partitions (x:xs) = partitions xs >>= \zs -> case zs of
                                               [] -> [[[x]]]
                                               (ys:yss) -> [[x]:ys:yss, (x:ys):yss]

where we need to explicitly distinguish between the cases of an empty partition (at the end of the recursion) and nonempty partitions, which in the above was done implicitly by binding to the pattern (ys:yss). That yields the desired order

*Partitions> partitions [1,2,3,4]
[[[1],[2],[3],[4]],[[1,2],[3],[4]],[[1],[2,3],[4]],[[1,2,3],[4]],[[1],[2],[3,4]],[[1,2],[3,4]],[[1],[2,3,4]],[[1,2,3,4]]]

Using the fact that the bind (>>=) for the list monad is flip concatMap, the version

partitions (x:xs) = concatMap insert (partitions xs)
  where
    insert [] = [[[x]]]
    insert (ys:yss) = [[x]:ys:yss, (x:ys):yss]

may be more readable.