Fixed-point combinator in F#

Question

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?

Answer 1

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