[Haskell-cafe] Fixed points

[Max Rabkin]

On Fri, Jun 10, 2011 at 21:05, Alexander Solla <alex.solla at 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).

--Max