Y combinator: Difference between revisions

<lang ocaml># type 'a mu = Roll of ('a mu -> 'a);;

let unroll (Roll x) = x;;

let fix f = (fun x a -> f (unroll x x) a) (Roll (fun x a -> f (unroll x x) a));;

let fac f = function

0 -> 1

| n -> n * f (n-1)

let fib f = function

0 -> 0

| 1 -> 1

| n -> f (n-1) + f (n-2)

val unroll :type 'a mu ->= Roll of ('a mu -> 'a = <fun>);;

val fib : (int -> int) -> int -> int = <fun> *)

# fix fac 5;;

(* - : int = 120 *)

<lang ocaml>let rec fix f x = f (fix f) x;;</lang>