Ocaml abstract list

main.ml

type 'a list= List of { l : 'z . (unit -> 'z) -> ('a * 'a list -> 'z) -> 'z }

let nil : 'a list = List{ l = fun f -> fun _ -> f()}
let cons (v : 'a) (r : 'a list) : 'a list= 
    List{ l = fun _ -> fun f -> f(v,r) }

let ex : int list = cons 3 (cons 1 (cons 2 nil))


let length (l : 'a list) : int =
    let rec loop (List{l}) acc = (l[@tailcall]) nil (cons loop) acc
        and nil         () acc = acc
        and cons fix (_,r) acc = (fix[@tailcall]) r (1 + acc) 
    in loop l 0


let () = Printf.printf "%d\n" (length ex)

main_v2.ml

type 'a list= List of { l : 'z . (unit -> 'z) -> ('a * 'a list -> 'z) -> 'z }

let nil : 'a list = List{ l = fun f -> fun _ -> f()}
let cons (v : 'a) (r : 'a list) : 'a list= 
    List{ l = fun _ -> fun f -> f(v,r) }

let ex : int list = cons 3 (cons 1 (cons 2 nil))

let len_nil         () acc = acc
let len_cons fix (_,r) acc = (fix[@tailcall]) r (1 + acc) 
let rec loop (List{l}) acc = (l[@tailcall]) len_nil (len_cons loop) acc
let length (l : 'a list) : int = loop l 0


let () = Printf.printf "%d\n" (length ex)