# Opfix

let rec fact = fun x ->
    match x with
    |0 -> 1
    |_ -> x * fact (x-1)

let fact_rec = fun f -> fun x ->
    match x with
    |0 -> 1
    |_ -> x * f (x-1)

fact_rec = (int -> int) -> int -> int 
= 'a -> 'a
avec 'a = (int -> int)

(* En général, *)

(opfix fact_rec)= fact_rec (opfix fact_rec)
opfix: ('a->'a) -> 'a
opfix fact_rec : 'a 



(opfix fact_rec) 2

(* Réussite de Anatole *)

(opfix fact_rec) 2
fact_rec (opfix fact_rec) 2
2 * (opfix fact_rec) 1
2 * (fact_rec (opfix fact_rec) 1)
2 * 1 * (opfix fact_rec 0)
2 * 1 * (fact_rec (opfix fact_rec) 0)
2 * 1 * 1
2


opfix f = f (opfix f)
opfix : ('α->'α)->'α




Manière de définir quelque chose qui ressemble à opfix en OCaml : 

let rec opfix f () = f (opfix f)
(* Les unit sont là pour geler *)
(* Type : ((unit -> 'a) -> 'a) -> unit -> 'a*)

let fact_rec f x = if x = 0 then 1 else x * f () (x -1)
(* Type : (unit -> int -> int) -> int -> int*)

opfix fact_rec () 3
(* S'évalue en 6 *)

Autre méthode :

let opfix f x = f f x ;;

let rec_fact f x =
match x with
| 0 -> 1
| _ -> x * (f f (x-1)) ;;

let fact = opfix rec_fact ;;

Printf.printf "%d\n" (fact 3) ;;

Récursif terminal, via CPS, malgré un double appel récursif.

let taille_cps a =
let rec taille a cont =
match a with
| Vide -> cont 0
| Noeud(_, g, d) -> taille g (fun r -> taille d (fun r' -> cont (r + r' + 1)))
in
taille a (fun x -> x)