dict.fs

module dict

exception KeyNotFound

type dict<'a> =
    | Null
    | Node of string * 'a * dict<'a> * dict<'a>

let empty = Null

let rec lookup k dict =
    match dict with
    | Null -> raise KeyNotFound
    | Node(key, value, l, r) when key = k -> value
    | Node(key, value, l, r) -> if (k > key) then lookup k r else lookup k l

let rec insert k d dict =
    match dict with
    | Null -> Node(k, d, Null, Null)
    | Node(key, value, l, r) when k = key -> Node(key, d, l, r)
    | Node(key, value, l, r) when k < key -> Node(key, value, insert k d l, r)
    | Node(key, value, l, r) -> Node(key, value, l, insert k d r)

let rec toList dict =
    match dict with
    | Null -> []
    | Node(key, value, l, r) -> (toList l)@[(key,value)]@(toList r)