[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: in defense of types

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 ;-)


(* 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. *)