Pure Functional List Exercise

I was recently challenged by a colleague to:

make a (Pure) list library where appending was O(1) without using the lazy-keyword.

As suggested by the formulation he expected me to implement lazyness through explicit thunks:

type 'a mylist_lazy =
  | Nil
  | Cons of 'a * (unit -> 'a mylist_lazy)

I leave the rest of this library as an exercise for the reader.

However, there is another way to implement such lists, which is quite neat. The key idea is to have a pointer to the end of the list, but because the solution has to be pure, we cannot use references. What we can use however is functions. The intuition is that we postpone putting in the list terminator (nil). Equationally we see:

1 :: 2 :: 3 :: nil = (fun tl -> 1 :: 2 :: 3 :: tl) nil

So, instead of returning lists we return a function taking the tail of the list and returning the final list. append now just becomes the function composition of two mylists.

type 'a mylist = 'a list -> 'a list
let nil = fun tl -> tl
let cons x xs' = fun tl -> x :: xs' tl
let append xs ys = fun tl -> xs (ys tl)
let is_empty xs = (* exercise *)
let head xs = (* exercise *)
let tail xs = (* exercise *)
let map f xs = (* exercise *)
let to_list xs = (* exercise *)