The function fix should take as argument a function f'
and return a function f so that
f x is equal to f' f x.
The solution is to store f in a reference r.
We temporarily create the reference r with a dummy function (that is
not meant to be used).
Assuming that the reference will later contain the correct version of
f, we can define f as fun x -> f' !r x.
Hence, the following solution:
| | |
| let fix f' =
let r = ref (fun _ -> raise (Failure "fix")) in
let f x = f' !r x in
r := f; !r;; |
|
| | |
| val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> |
|
Note that the exception should never be raised because
the content of the reference is overridden by
f before being reference is used. We could also use the option type to initialized the content of the
reference to None and replace it later with Some f. However,
would not avoid raising an exception if the value of the reference where to
be None when being read, even though this situation should never
occur dynamically in a correct implementation.
As an example, we define the factorial function:
| | |
| let fact' fact n = if n > 0 then n * fact (n-1) else 1 in
fix fact' 6;; |
|
| | | |