Reversing Double Lists

A double list is a data type which represents a list, but elements are Cons-ed two at a time. In order to represent lists with an odd number of elements, there is also a constructor for a singleton list.

type 'a doublelist
  = Nil
  | Single of 'a
  | Cons of 'a * 'a * 'a doublelist

Implement the function

val rev : 'a doublelist -> 'a doublelist

which reverses a doublelist.

Challenge worth nothing: Give a tail recursive implementation.

let _ = assert (rev (Cons (1, 2, Nil)) = Cons (2, 1, Nil))
let _ = assert (rev (Cons (1, 2, Single 3)) = Cons (3, 2, Single 1))