5

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.

duplode
  • 33,731
  • 7
  • 79
  • 150
flawr
  • 10,814
  • 3
  • 41
  • 71
  • `ghci` says that the type of that function is `Eq a => (a -> a) -> a -> a`. Hoogle doesn't seem to return useful results for that signature. – Daenyth Aug 15 '16 at 12:49
  • 2
    The closest thing is `until :: (a -> Bool) -> (a -> a) -> a -> a` `until p f yields the result of applying f until p holds.` - it seems like you could write your function using it but you still need the `Eq` constraint – Daenyth Aug 15 '16 at 12:51
  • 1
    @Daenyth Thanks, I didn't know you could use hoogle that way=) If you add it as an answer I'd accept that. – flawr Aug 15 '16 at 12:59

3 Answers3

5

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
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • I know there are many ways to do it, but I'm explicitly looking for a built in, as I'm assuming it is a quite commonly funciton. – flawr Aug 15 '16 at 16:27
  • @flawr, I don't think it's particularly common, actually. `until` seems closest, but actually using it for this purpose is more trouble than it's worth. – dfeuer Aug 15 '16 at 17:17
1

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.

Community
  • 1
  • 1
Daenyth
  • 35,856
  • 13
  • 85
  • 124
  • You could use `until` with pairs, but I think it's simpler to just do the whole thing by hand. – dfeuer Aug 15 '16 at 13:03
  • or `last . takeWhileDifferent . iterate f`, or similar write own `last . takeWhileDifferent` variant... takeWhileDifferent = https://github.com/ekmett/ad/blob/ac5e0c7091430d0c569ba893f78385ead70b918e/src/Numeric/AD/Internal/Combinators.hs#L51 – phadej Aug 15 '16 at 17:21
1

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.

Laikoni
  • 201
  • 1
  • 7