Ocaml fixed point implementation

Question

I'm trying to figure out how to implement fixed point iteration in Ocaml. That is, given a function f and an x, I want to calculate what the final value of what f(f(f(x)...)) will be.

So for example, if my function is x/2 and my x=50, my answer should be 0.

So far, I have

 let rec computed_fixed_point eq f x =
        if (x == f x) then 
            x
        else
            computed_fixed_point eq f (f x)

This works for the function x/2 and x=50 (giving me 0), but for functions that go off to infinity or something other than 0, it doesn't seem to work.

Can another give me some advice? Thanks!

Answer 1

It's a little hard to understand the rationale of this problem. Not every function is going to have a fixed point. For example fun x -> (x + 1) mod 5. Not every function with a fixed point will reach the fixed point by repeated application from a distinct starting point. (I just did some googling, and fixed points like this are called "attractive fixed points".)

Here are some comments:

• You shouldn't use ==, which is the physical equality operator. You possibly want to use =, equality of values.

• However, I don't see what the eq parameter is for. Perhaps the caller is allowed to specify what equality to use. If so, you should use this instead of ==.