CODEWITHSUNDEEP
haskellfixed-point-iteration
flawr
flawr

Reputation: 11628

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.

Upvotes: 5

Views: 1078

Answers (3)

Laikoni
Laikoni

Reputation: 211

In case you are looking for a build-in because you want a short expression without any auxiliary functions, I can recommend 

until=<<((==)=<<) :: Eq a => (a -> a) -> a -> a

Arguably this looks a bit strange, but in fact it is just the point-free equivalent to until (\x -> f x == x) f, using the fact that f (g x) x can be expressed by (f=<<g) x twice.

Upvotes: 2

Daenyth
Daenyth

Reputation: 37441

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.

Upvotes: 1

dfeuer
dfeuer

Reputation: 48591

Just write it yourself. A direct version will be faster than one using dropWhile.

hammer :: Eq a => (a -> a) -> a -> a
hammer f x
  | x' == x = x'
  | otherwise = hammer f x'
  where x' = f x

Upvotes: 5

Related Questions