(** Version naive:
  * non recursive terminale, quadratique. *)
let rec rev l = match l with
  | [] -> []
  | hd::tl -> rev tl @ [hd]

let () = assert (rev [1;2] = [2;1])

(** Passage en CPS *)
let rec rev l k = match l with
  | [] -> k []
  | hd::tl -> rev tl (fun l' -> k (l' @ [hd]))

let () = assert (rev [1;2] (fun x -> x) = [2;1])

(** Défonctionalisation.
  * En fixant des éléments de type int, on a
  * des continuations de type int->int vu qu'on
  * prend en compte le cas d'utilisation dans
  * les assert ci-dessus, où l'identité est
  * utilisée comme continuation. *)

type cont = Id | Acc of cont * int

let rec apply cont arg = match cont with
  | Id -> arg
  | Acc (k,hd) -> apply k (arg @ [hd])

let rec rev l k = match l with
  | [] -> apply k []
  | hd::tl -> rev tl (Acc (k,hd))

let () = assert (rev [1;2] Id = [2;1])

(** On note que cont est isomorphe à int list.
  * Si on utilise directement le type int list
  * pour cont, alors apply cont arg est la fonction
  * qui prend deux listes d'entiers et renvoie
  * cont@apply. En particulier, apply k [] est k.
  * On réécrit selon ces observations: *)

let rec rev l k = match l with
  | [] -> k
  | hd::tl -> rev tl (hd::k)

let () = assert (rev [1;2] [] = [2;1])

(** On a retrouvé la version tail-recursive de
  * rev, qui calcule en temps linéaire. *)