Sunday, October 14, 2007

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

2 comments:

Alyn said...

Good for people to know.

rei said...

Interesting.

I tried changing Elem from int to System.IComparable; that makes the code as generic as possible given this particular structure.

I wonder though, would this need to be memoized in order for the performance to be half-decent?