Tailing Ordered Fork Lists

A fork list is a combination of a list and a binary tree. It has constructors for the empty list (Nil), a single link (Cons), and a double link (Fork).

type 'a forklist
  = Nil
  | Cons of 'a * 'a forklist
  | Fork of 'a * 'a forklist * 'a forklist

A fork list l with distinct elements is ordered if it satisfies the following properties:

1. if l is of the form Cons (x, xs) then every element in xs is greater than x;
2. if l is of the form Fork (x, lxs, rxs) then every element in lxs is less than x and every element in rxs is greater than x.

A fork list l is tailed if it satisfies the property that if Cons (x, xs) appears in l, then xs contains no Fork constructors.

Implement the function

val delay_cons : int forklist -> int forklist

so that, given an ordered fork list of integers f, delay_cons f is a tailed ordered fork list with the following properties:

1. it has the same elements as f;
2. it has the same number of Cons, Fork, and Nil constructors as f, respectively.

Note that the output does not need to look exactly like the one in the example below; it just has to satisfy the above properties.

let f = Cons (2, Fork (4, Cons (3, Nil), Cons (5, Nil)))
let g = Fork (4, Cons (2, Cons (3, Nil)), Cons (5, Nil))
let _ = assert (delay_cons f = g)