Fixed-point combinator in F#

f#, fixpoint-combinators

Solution

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

Problem

This would not work: ``` let rec fix f = f (fix f) ``` The solution is to add an extra parameter: ``` let rec fix f x = f (fix f) x ``` Is there a way to do this using `lazy` and `Lazy.force` instead?

Original source