Your original fix
takes an 'a -> 'a
:
> let rec fix f = f (fix f);;
val fix : ('a -> 'a) -> 'a
If you make it take a Lazy<'a> -> 'a
then you can just write this:
> let rec fix f = lazy f (fix f);;
val fix : (Lazy<'a> -> 'a) -> Lazy<'a>
This allows f
to not evaluate its argument if it doesn't need it, so the recursion can terminate at runtime.
If you want the result to be of type 'a
then just force the final result:
> let rec fix' f = lazy f (fix' f);;
val fix' : (Lazy<'a> -> 'a) -> Lazy<'a>
> let fix f = (fix' f).Value;;
val fix : (Lazy<'a> -> 'a) -> 'a
For example here's the factorial function:
> fix (fun f n -> if n > 1 then n * f.Value (n-1) else 1) 4;;
val it : int = 24