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.

I thought maybe you wanted the powerset (filterM (const [True, False])), but your definition is slightly different. You want every possible partitioning of the list? — singpolyma
What do you think is the type of insert? I think insert :: a -> [[[a]]] -> [[[a]]]. When do you think insert is used? In fact, it's used at each step of foldr's recursion through the list, so your code seems to be trying to give answers which make lots of copies of x. The idea of using foldr is good: just think about what are the partitions [] and how to compute the partitions of a nonempty list ([1,2,3,4], say), given the partitions of its tail ([2,3,4]). For the latter, consider how to add the head element (1 here) to each tail partition. List comps might indeed help. — pigworker
The partitioning of each copy of the list is in correspondence with all characteristic functions on [1..n-1] (for a length of list n). You can generate these via replicateM (pred n) [True,False] (why?), then zipWith an appropriate combining function and 2^(n-1) copies of your original list. (Extra points for a solution which bypasses the explicit creation of the characteristic functions.) — Fixnum
Fixnum, that seems really complicated. Are you sure such complexity is really needed here? — Joe
Are you sure you don't want [[1,3],[2,4]] included in the result? That's a partition too! (In the mathematical sense, at least) — yatima2975

Daniel Fischer Daniel Fischer · Accepted Answer · 2012-11-18T21:49:19

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

It can be the only element of one of the partition lists.
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.

All possible sublists of a list

1 Answers