haskell - List partitioning implemented recursively

Question

I am a Haskell beginner and I have been experimenting with recursive functions.

I am working on a function:

 separate :: [a] -> [[[a]]]

that takes in a list and outputs all of the partitions of that list.

For example 123 becomes:

1|2|3
12|3
1|23
13|2
132

I have only been able to implement a recursive function that creates the 1|2|3 variant:

separate' :: [a] -> [[a]]
separate' (r:rs) = [r]:separate' xs

>separate [1,2,3]
[[1],[2],[3]]

I am stuck with trying to create the other variants with recursion.

Answer 1

You can think of this function as choosing, for each place in between two list elements, whether to include a split there. So for starters, there should be 2^n-1 partitions for an n-element list: you can use that as a quick sanity check on a possible solution.

One good way to model non-determinism is with the list monad (or equivalently with list comprehensions), so let's do it that way.

First, let's write the type and a base case:

separate :: [a] -> [[[a]]]
separate [] = [[]]

There is a single way to separate an empty list: the empty list itself, with no possibility of splits. Easy enough.

Now, given we have one element and a list of remaining elements, one thing we'll need for sure is a list of all the ways to split the remaining elements:

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                  in undefined -- TODO

Here's where the interesting stuff starts. As I said, you can view this as choosing, for each item, whether to put a split after it. Two choices means concatenating together two lists, so let's do that:

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = undefined -- TODO
                      noSplit = undefined -- TODO
                  in split ++ noSplit

Now, how do we introduce a split after the item x? We do it by, for each partition in recur, adding [x] to the front of it as a new partition:

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = do
                        partition <- recur
                        return $ [x] : partition
                      noSplit = undefined -- TODO
                  in split ++ noSplit

What about not splitting? Pretty similar! For each partition in recur, we add x to the front of the first sub-partition:

separate :: [a] -> [[[a]]]
separate [] = [[]]
separate (x:xs) = let recur = separate xs
                      split = do
                        partition <- recur
                        return $ [x] : partition
                      noSplit = do
                        (y:ys) <- recur
                        return $ (x:y):ys
                  in split ++ noSplit

And with that, we're done:

*Temp> separate "123"
[["1","2","3"],["1","23"],["12","3"],["123"]]