Search code examples
haskellfixed-point-iteration

Is there a fixed point operator in Haskell?

I recently noticed that I quite often write functions which just iterates another function f until it reaches a fixed point (such that f x == x)

I thought this is a pretty general concept, so I think there might be a built in.

So I was wondering whether there is a built in for this, or something more general?

So I'm basically looking for this:

fixedpoint f x= head . dropWhile(\y->y /= f y) $ iterate f x

I just had trouble googling this, because I only found references to the fix function whenever my search term contained fixed point or something similar.

Solution

  • Your function has the signature Eq a => (a -> a) -> a -> a.

    Using hoogle to search for that, I don't see any exact matches. The closest match is until

    until :: (a -> Bool) -> (a -> a) -> a -> a

    base Prelude

    until p f yields the result of applying f until p holds.

    You could likely use that to write your function but because you need /= you need the Eq constraint.