Re: [Haskell-cafe] Fixed points

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