On Fri, Jun 10, 2011 at 21:05, Alexander Solla <alex.solla@gmail.com> wrote:
> equivalenceClosure :: (Ord a) => Relation a -> Relation a
> equivalenceClosure = fix (\f -> reflexivity . symmetry . transitivity)

If you want to learn about fix, this won't help you, but if you're
just want the best way to calculate equivalence closures of relations,
then it's probably

equivalenceClosure = transitivity . symmetry . reflexivity

assuming those are the transitive, symmetric and reflexive closure
functions. You still need some kind of iteration to get the transitive
closure. The algorithm I know of for that is Warshall's Algorithm,
which is O(N^3) (possibly with a log N factor for pure data
structures).

Cool, thanks for the suggestion. I was iterating all of them, since an iteration of "transitive" introduces new pairs to the relation (which are not guaranteed to have symmetric "complements" in my implementation). I suppose I can get away with not iterating "reflexive", for something like an O(n) speed up for each iteration.

This is a summary of the code. I haven't done order analysis on it. Relation is a newtype over a Set of pairs:

-- | Iterate 'transitivity' to compute the transitive closure for a relation.

transitivity :: (Ord a) => Relation a -> Relation a

transitivity (Relation set) = Relation $ (Set.fold _joinOn set) (set)

-- | Compute the reflexive closure for a relation. In other words, take a set

-- containing @(a,b)@, @(c,d)@, ... into one containing the originals and

-- @(b,a)@, @(d,c)@, and so on.

reflexivity :: (Ord a) => Relation a -> Relation a

reflexivity (Relation set) = Relation $ Set.unions [ set

, (Set.map (\(x,_) -> (x,x)) set)

, (Set.map (\(_,y) -> (y,y)) set)

]

-- | Compute the symmetric closure for a relation.

symmetry :: (Ord a) => Relation a -> Relation a

symmetry (Relation set) = Relation $ Set.union set (Set.map _symmetry set)

_symmetry :: (a, a) -> (a, a)

_symmetry (a, b) = (b, a)

_joinOn :: (Ord a) => (a,a) -> Set (a,a) -> Set (a,a)

_joinOn (a,b) set =

let fst' = Set.filter ((b ==) . fst) $ set

snd' = Set.filter ((a ==) . snd) $ set

in Set.unions [ set

, Set.map (\(x,y) -> (a,y)) fst'

, Set.map (\(x,y) -> (x,b)) snd'

]