Group list by equivalence relation

If you can define a compatible ordering relation, you can use

equivalenceClasses equal comp = groupBy equal . sortBy comp

which would give you O(n*log n) complexity. Without that, I don't see any way to get better complexity than O(n^2), basically

splitOffFirstGroup :: (a -> a -> Bool) -> [a] -> ([a],[a])
splitOffFirstGroup equal xs@(x:_) = partition (equal x) xs
splitOffFirstGroup _     []       = ([],[])

equivalenceClasses _     [] = []
equivalenceClasses equal xs = let (fg,rst) = splitOffFirstGroup equal xs
                              in fg : equivalenceClasses equal rst

Here's a slight variation of Daniel's suggestion:

Since equivalence classes partition a set of values (meaning that every value belongs to exactly one class), you can use a value to represent its class. In many cases, however, it is quite natural to choose one canonical representative per class. In your example, you might go for (0,x,0) representing the class { (0,0,0), (0,0,1), (1,0,0), (1,0,1), (2,0,0), ... }. You can therefore define a representative function as follows:

representative :: Sometuple -> Sometuple
representative (_,x,_) = (0,x,0)

Now, by definition, equal a b is the same as (representative a) == (representative b). So if you sort a list of values by representative -- assuming we're dealing with members of Ord --, members of the same equivalence class end up next to each other and can be grouped by ordinary groupBy.

The function you were looking for thus becomes:

equivalenceClasses :: Ord a => (a -> a) -> [a] -> [[a]]
equivalenceClasses rep = groupBy ((==) `on` rep) . sortBy (compare `on` rep)

Daniel's suggestion is a generalisation of this approach. I'm essentially proposing a specific ordering relation (namely comparison by representative) that can be derived easily in many use cases.

Caveat 1: You need to make sure that representatives of the same/different equivalence classes are actually equal/different according to (==) and compare. If those two functions test for structural equality, this is always the case.

Caveat 2: Technically, you can relax the type of equivalenceClasses to

equivalenceClasses :: Ord b => (a -> b) -> [a] -> [[a]]

The correct data structure to use here is a disjoint set (Tarjan). A purely functional, persistent implementation of such a structure was described by Conchon and Filliâtre. There's an implementation on Hackage.