Haskell All possible partitions of a list [duplicate]

Question

I need to write a function that produces all of the possible partitions of a list, including non-contiguous partitions. It should look something like this:

*Main> ps [1,2,3,4]
[[21, 3, 4],[31, 2, 4],[41, 2, 3],[431, 2],[21, 43],[4321],[31, 42],[421, 3],[41, 32],[321, 4],[1, 32, 4],[1, 42, 3],[1, 432],[1, 2, 43],[1, 2, 3, 4]]

So far I have only been able to produce a recursive function using list comprehension to produce the contiguous partitions.

ps [] = [[]]
ps (x:xs) = [[x]:qs | qs <- ps xs] ++ [(x:gs):gss | (gs):gss <- ps xs]

I have an idea of moving the tail of each partition and prepending it to the first element of each partition, but I am not sure how I would do this in Haskell. I'm still a newbie to this language. Any help would be greatly appreciated!

Answer 1

Here is the function you need:

bloat :: a -> [[a]] -> [[[a]]]
bloat x  []      = [[[x]]]
bloat x (xs:xss) = ((x:xs):xss) : map (xs:) (bloat x xss)

E.g. bloat 'a' ["b", "c", "de"] equals

[["ab","c","de"],["b","ac","de"],["b","c","ade"],["b","c","de","a"]]

i.e. prepend a to each sublist (and at the end of the list) and duplicate the remaining sublists.

Then partitionSet is simply

partitionSet :: [a] -> [[[a]]]
partitionSet  []    = [[]]
partitionSet (x:xs) = [ys | yss <- partitionSet xs, ys <- bloat x yss]

Or in more idiomatic Haskell

partitionSet :: [a] -> [[[a]]]
partitionSet = foldr (\x r -> r >>= bloat x) [[]]