[Haskell-cafe] Fixed points

Patrick Palka patrick at parcs.ath.cx
Fri Jun 10 22:52:56 CEST 2011


FWIW, what you have written is equivalent to

equivalenceClosure = fix (const (reflexivity . symmetry . transitivity))

and because the fixed point of `const a` is `a`,

equivalenceClosure = reflexivity . symmetry . transitivity 

which obviously only performs a single pass on its input

On Fri, Jun 10, 2011 at 12:10:16PM -0700, Alexander Solla wrote:
> On Fri, Jun 10, 2011 at 12:05 PM, Alexander Solla <alex.solla at gmail.com>wrote:
> 
> > On Thu, Jun 9, 2011 at 6:04 PM, Felipe Almeida Lessa <
> > felipe.lessa at gmail.com> wrote:
> >
> >> Something like this?
> >>
> >>  equivalenceClosure = fix $ \f e ->
> >>    let e' = reflexivity . symmetry . transitivity $ e
> >>    in if e' == e then e else f e'
> >>
> >> Cheers,
> >>
> >> --
> >> Felipe.
> >>
> >
> > I managed something even "clearer".  I still have very little intuition
> > about what's going on, but I had an aha moment -- which I promptly forgot
> > :0( -- and at least there's a mechanical translation from the iterate
> > version to the fix one.
> >
> > equivalenceClosure :: (Ord a) => Relation a -> Relation a
> > equivalenceClosure = fix (\f -> reflexivity . symmetry . transitivity)
> >
> 
> Cancel that, it's not passing my tests.

> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe




More information about the Haskell-Cafe mailing list