Re: in defense of types

[Michael Vanier <address@hidden>]

To beat a dead horse completely into the ground, here is a summary of all
the ways seen so far to write the Y combinator in ocaml.  This proves
definitively that I was wrong ;-)

Mike


(* ocaml versions of the applicative-order Y combinator. *)

open Printf

(* Test function: *)
let mk_fact fact n = 
  if n = 0 then 1 else n * fact (n - 1)

(* 
 * This is the key trick.  Note that you're using a recursive _type_
 * to make Y work, instead of a recursive _function_.  This seems like
 * cheating to me.
 *)

type 'a t = I of ('a t -> 'a)

(*** Jaeyoun Chung ***)

let y1 f = 
  (function I x -> f (fun y' -> x (I x) y'))
    (I (function I x -> f (fun y' -> x (I x) y')))
;;

printf "y1: %d\n" ((y1 mk_fact) 10);;


(*** Pixel ***)

(* Using 'let rec' (cheating): *)
let rec y2 f e = f (y2 f) e;;

printf "y2: %d\n" ((y2 mk_fact) 10);;

(* Without 'let rec': *)
let y3 f = 
  let g = function (I x) -> f (fun y3 -> x (I x) y3) in
  g (I g)
;;

printf "y3: %d\n" ((y3 mk_fact) 10);;

(*** Felleisen; The Little MLer ***)

let g (I a) x = (a (I a)) x;;
let h f a = f (g a);;
let y4 f = (h f) (I (h f));;

printf "y4: %d\n" ((y4 mk_fact) 10);;


(* End of file. *)