[Haskell-beginners] partition a list in all possible ways

[Daniel Fischer]

On Tuesday 26 April 2011 20:10:37, I. J. Kennedy wrote:
> I'm looking for a function  [a] -> [[[a]]]  that will partition a list
> into non-empty pieces in all possible ways.
> For example
> f [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]]]

Your description doesn't quite match your example, [[1,3],[2],[4]] is a 
partition of [1,2,3,4] into non-empty pieces which doesn't appear in your 
result.
By your example, you want all possible partitions into non-empty contiguous 
subsequences, which is somewhat easier (not that all partitions are really 
difficult).

> Perhaps this is a well-known function to experts, but not
> to me. Hoogle doesn't seem to have anything with this signature.
> Thanks,
> Jack

Think recursively. For (x:xs), you get two classes of partitions,
a) those where x makes up a part of its own, those are

[[x]:parts | parts <- partitions xs]

or map ([x] :) (partitions xs)

b) those where x belongs to the same part as its successor in the original 
list, those are obtained by sticking x to the front of each first part of 
the partitions of xs,

[(x:ys):yss | (ys:yss) <- partitions xs]

For an empty list, you get exactly one partition into non-empty pieces, the 
empty partition, [ [] ], so

partitions [] = [[]]
partitions (x:xs) = [[x]:p | p <- partitions xs]
                 ++ [(x:ys):yss | (ys:yss) <- partitions xs]