WTFP #2: OCaml ThunkLists

After roughly one and a smidge years of hiatus, I am back with the promised WTFP #2, OCaml infinite lists.

They aren't quite the same thing as the infinite lists in Haskell, due to the fact that OCaml isn't as lazy as Haskell is, but they follow a somewhat similar principle to the FLists I mentioned back in the previous WTFP. This is the definition of a Thunklist, or thunked:

type 'a thunked = Thunk of 'a * (unit -> 'a thunked)

What is this saying? Well, since it has been more than a year since I touched OCaml, I will do my best to explain.

Translating into haskell:

data ThunkList a = Thunk a (() -> ThunkList a)

You see, since the only thing that OCaml is really lazy about are functions, we define a list consisting of a head element, and a tail element that can't be bothered to get off its ass and show up right away. If we pay it a dollar (in this case, a unit or ()), it will stick its head round the corner but keep its tail hidden. And so forth.
So, what this does is basically implement artificial laziness on the second component of the list, so we can handle infinity since we never have to see it. From this point, we can define the basic list functions head and tail:

(* first element of a thunked list *)
let head : 'a thunked -> 'a =
  fun z -> match z with | Thunk (x,_) -> x

(* remainder of a thunked list *)
let tail : 'a thunked -> 'a thunked =
  fun z -> match z with | Thunk (_,th) -> th ()

and even our old friend (!!):

(* index accessor of a thunked list *)
let rec get : int -> ('a thunked -> 'a) =
  fun i -> match i with
    | 0 -> head
    | y when y > 0 -> fun xs -> get (i-1) (tail xs)
    | _ -> failwith "cannot get negative index"

But where do we go from here? Well, exploiting the laziness mentioned earlier, we can even have bidirectionally infinite lossless lists, if we could be bothered.

(* dethunk: a doubly-lazy, doubly-infinite list *)
type 'a dethunk = (unit -> 'a thunked) * 'a * (unit -> 'a thunked)

Since I am too lazy, I will leave implementing the functions you would want out of a bidirectionally infinite lossless list. I have the implementation in front of me, but I am just too lazy.