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

Stack Examples

Here is the previous stack implementation in use.

> let xs = Cons(0, Cons(1, Cons(2, Nil)));;

val xs : int Stack

> xs;;

val it : int Stack = Cons (0,Cons (1,Cons (2,Nil)))

> let ys = Cons(3, Cons(4, Cons(5, Nil)));;

val ys : int Stack

> ys;;

val it : int Stack = Cons (3,Cons (4,Cons (5,Nil)))

> let zs = xs -||- ys;;

val zs : int Stack

> zs;;

val it : int Stack = Cons (0,Cons (1,Cons (2,Cons (3,Cons (4,Cons (5,Nil))))))

> head xs;;

val it : int = 0

> tail xs;;

val it : int Stack = Cons (1,Cons (2,Nil))

> update(xs, 1, 99);;

val it : int Stack = Cons (0,Cons (99,Cons (2,Nil)))

Purely Functional Data Structures: An F# Stack

One of the beauties of F# is that it doesn't force you to follow one programming technique. If you want to code with objects in an imperative style, you're free to. If you want to write strict functional code, you're free to do that as well.

I'm quite familiar with imperative modes of programming so I've been bending my mind in the functional direction by reading Purely Functional Data Structures. The book's examples are written in ML (with a Haskell appendix), so I'm re-writing them in F#. I'll post them here as I do in the hopes that it will help other .NET programmers bend their mind as well.

Here is the code for a Stack implementation from Chapter 2.1:

#light

exception Empty
exception Subscript

type 'a Stack = Nil | Cons of 'a * 'a Stack

let empty = Nil

let isEmpty = function
    | Nil -> true
    | _ -> false

let head = function
    | Nil -> raise Empty
    | Cons(x, s) -> x
    
let tail = function
    | Nil -> raise Empty
    | Cons(x, s) -> s

let rec (-||-) xs ys =
    if isEmpty xs then
        ys
    else
        Cons(head xs, tail xs -||- ys)

let rec update = function
    | Nil, i, y -> raise Subscript
    | xs, 0, y -> Cons(y, tail(xs))
    | xs, i, y -> Cons(head(xs), update(tail(xs), i-1, y))