I have a equivalence relation R
on a set A
. How can I build equivalence classes on A
? It's something like groupBy
do, but between all the elements, not only neighbors.
For example, equal
is equivalence relation (it is reflexive, symmetric and transitive binary relation):
type Sometuple = (Int, Int, Int)
equal :: Sometuple -> Sometuple -> Bool
equal (_, x, _) (_, y, _) = x == y
It is actually a predicate that connect 2 Sometuple
elements.
λ> equal (1,2,3) (1,2,2)
True
So, how can I build all equivalence classes on [Sometuple]
based on equal
predicate? Something like that:
equivalenceClasses :: (Sometuple -> Sometuple -> Bool) -> [Sometuple] -> [[Sometuple]]
λ> equivalenceClasses equal [(1,2,3), (2,1,4), (0,3,2), (9,2,1), (5,3,1), (1,3,1)]
[[(1,2,3),(9,2,1)],[(2,1,4)],[(0,3,2),(5,3,1),(1,3,2)]]
equivalence
package requires some mutable monadic context (IO
orST
). Trypersistent-equivalence
instead for something a bit cleaner. – mergeconflict Nov 25 '11 at 19:04