Module Fix (.ml)


module Fix: sig .. end
Poor man fix point operators.

val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b
Basic fix point operators.

Example:

# let fact self = fun x -> if (x=0) then 1 else x * (self (x-1)) ;;
val fact : (int -> int) -> int -> int = <fun>

# let f = fix fact;;
val f : int -> int = <fun>

# f 5;;    
  : int = 120

val efix : ('a -> ('a -> 'b -> 'c) -> 'b -> 'c) -> 'a -> 'b -> 'c
Fix point operator for making function requiring a parameter (the "environment").

Example:

# let fact y self = fun x -> if (x=0) then y else x * (self y (x-1)) ;;
val fact : int -> (int -> int -> int) -> int -> int = <fun>

# let f y = (efix fact y) ;;
val f : int -> int -> int = <fun>

# f 2 5;;
  : int = 240

# f 3 5;;
  : int = 360

val ecfix : ('a -> 'b -> 'c) -> ('d -> ('d -> 'b -> 'c) -> 'a) -> 'd -> 'b -> 'c
Fix point operator with an environment and a treatment (a "cure") to perform before each recursive call. The typical example is the "memoisation" cure useful for making memoised functions defined by a recursive definition (each recursive call must share the same hash table).

Example:

# let fact y self = fun x -> if (x=0) then y else x * (self y (x-1)) ;;
val fact : int -> (int -> int -> int) -> int -> int = <fun>

(* The cure change the sign at the end of each iteration *)
# let f y = (ecfix (fun g x -> (g x)*(-1)) fact y) ;;
val f : int -> int -> int = <fun>

# f 2 3;;
  : int = 12    (* because of an even number (4) of iterations *)

# f 2 4;;
  : int = -48   (* because of an odd number (5) of iterations *)

# f 2 5;;
  : int = 240   (* because of an even number (6) of iterations *)

(* Tracing the unfolding *)
# let f y = (Fix.ecfix (fun g x -> (print_int x; print_newline ()); (g x)*(-1)) fact y) ;;

# f 2 5;;
5
4
3
2
1
0
  : int = 240