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]