(** Simplest example: list reverse
   Let's assume we are writing the list reversal function for
   a list-like data structure. That is, for some data structure
   with list API (null, cons, nil, head and tail). For the latter
   reason, we don't use pattern matching in our function.
*)

(* The generic list API and its one particular implementation *)
let cons x y = x :: y
let nil () = []
let null = function [] -> true | _ -> false
let head = function (h::_) -> h
let tail = function (_::t) -> t
;;

let rec rev l acc = if null l then acc 
                    else rev (tail l) (cons (head l) acc)
;;

let test1 = rev [1;2;3] [];;

module FL :
   sig
   type 'a fullist
   val unfl : 'a fullist -> 'a list
   val indeed : 'a list -> 'a fullist option
   val head : 'a fullist -> 'a
   val tail : 'a fullist -> 'a list
   end = struct
   type 'a fullist = 'a list
   let unfl l = l
   let indeed l = if null l then None else Some l
   let head l = head l (* could use unsafe-head *)
   let tail l = tail l (* could use unsafe-tail *)
end;;

let rec rev' l acc = 
  match FL.indeed l with None -> acc 
  | Some l -> rev' (FL.tail l) (cons (FL.head l) acc)
;;

let test2 = rev' [1;2;3] [];;

(* CPS version *)
module FLC :
   sig
   type 'a fullist
   val unfl : 'a fullist -> 'a list
   val indeed : 'a list -> (unit -> 'w) -> ('a fullist -> 'w) -> 'w
   val head : 'a fullist -> 'a
   val tail : 'a fullist -> 'a list
   end = struct
   type 'a fullist = 'a list
   let unfl l = l
   let indeed l onn onf = if null l then onn () else onf l
   let head l = head l
   let tail l = tail l
end;;

let rec revc' l acc = FLC.indeed l (fun () -> acc)
  (fun l -> revc' (FLC.tail l) (cons (FLC.head l) acc))
;;
let test3 = revc' [1;2;3] [];;