Purely Functional Data Structures: An F# Binary Tree

Continuing my series on Purely Functional Data Structures, here's my F# implementation of a binary tree:

#light

type Elem = int

type Tree = E | T of Tree * Elem * Tree

let empty = E

let rec mem = function
    | x, E -> false
    | x, T(a, y, b) when x < y -> mem(x, a)
    | x, T(a, y, b) when y < x -> mem(x, b)
    | _ -> true

let rec insert = function
    | x, E -> T(E, x, E)
    | x, T(a, y, b) when x < y -> T(insert(x, a), y, b)
    | x, T(a, y, b) when y < x -> T(a, y, insert(x, b))
    | _, s -> s

Here's what the tree looks like in use:

> let t = T(E, 1, E);;

val t : Tree

> t;;

val it : Tree = T (E,1,E)

> let t1 = insert(0, t);;

val t1 : Tree

> t1;;

val it : Tree = T (T (E,0,E),1,E)

> let t2 = insert(10, t1);;

val t2 : Tree

> t2;;

val it : Tree = T (T (E,0,E),1,T (E,10,E))

> let t3 = insert(5, t2);;

val t3 : Tree

> t3;;

val it : Tree = T (T (E,0,E),1,T (T (E,5,E),10,E))

> mem(10, t1);;

val it : bool = false

> mem(10, t2);;

val it : bool = true