Partition a set in Haskell

Question

I'm trying to write a Haskell program that could return the partition set of a user defined set. The partition of a set S is defined as a set of nonempty, pairwise disjoint subsets of S whose union is S. So, [1,2,3] returns [[[2],[3,1]],[[2,1],[3]],[[3,2,1]],[[1],[3,2]],[[1],[2],[3]]]. I think I can utilize a different program I wrote a while ago that finds the cartesian product from two sets. So, [1,2,3] ['a', 'b'] returns [(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]. However, I'm not sure quite how. I think it would require recursion though, if this can even be adapted properly. Here is the subset code:

type Set a = [a]

isElement :: Eq a => a -> [a] -> Bool
isElement x [] = False
isElement x (y:ys) = if(x==y) then True else isElement x ys

subset :: Eq a => Set a -> Set a -> Bool
subset [] xs = True
subset (y:ys) xs = if(isElement y xs == True)
                  then do subset ys xs
                  else do False

Answer 1

The idea is that in order to find all partitions of set X ∪ {x}, we find parritions of X first. Then add x to each of them in every possible way (that is, add x to the first element of a partition, add x to the second element etc) and take a union of the result.

Here's a rather straightforward implementation:

partitions :: [a] -> [[[a]]]
partitions [] = [[]]
partitions (x:xs) = expand x $ partitions xs where

    expand :: a -> [[[a]]] -> [[[a]]]
    expand x ys = concatMap (extend x) ys

    extend :: a -> [[a]] -> [[[a]]]
    extend x [] = [[[x]]]
    extend x (y:ys) = ((x:y):ys) : map (y:) (extend x ys)

Demo: https://ideone.com/ClYOoQ

Answer 2

Pseudocode for one recursive algorithm:

If |S| = 1
  Return ∅
Otherwise
  For each nonempty proper subset X ⊂ S
    Let Y = S - X
    Add {X, Y} to R
    For each Z in {partitionSet(X)}
      Add Z ∪ {Y} to R.
  Return R

Since “adding” elements to a list isn’t a very functional idiom, you would want to do those steps with a concatMap or a list comprehension. You might also build R as an accumulating parameter to a tail-recursive function, or as a union of the return values of each step. The proper subsets function is in the Haskell standard library as Data.List.subsequences.

If you have a total ordering on all proper subsets of S, you can use symmetry-breaking to add only partitions that are unique up to permutation. That is, if X > Y, you could add only {X,Y} and not {Y,X}, and only {X,Y,Z} and not {Y,X,Z}. Be careful that you still sub-partition every set in your partition exactly once!

This finds only partition sets of S, if ⋃Z = X and X ∪ Y = S, the union of all sets in Z and Y is S, it returns only sets of nonempty proper subsets of S, and every partition and subpartition is a set difference, hence pairwise disjoint.

Any partition set of cardinality two has the form {X, S-X}, and the algorithm finds it because it tries every possible X. Any partition set of cardinality i>2 has the form {a_1, a_2, ..., a_i}, where {a_1, a_2} is a partition set of {a_1 ⋃ a_2} and {{a_1 ⋃ a_2}, ..., a_i} is a partition set of cardinality i-1, and will be found when subpartitioning the parent node of the search tree. Therefore, by induction, the algorithm finds all partition sets of S.