By contrast this binary search tree code I wrote in OCaml seems to have worked as soon as I got it to compile, although its worst-case performance is pretty bad, and, unlike the much longer hash table code, very likely:

    let rec getp k = function `Empty -> None
      | `Node(k1, v1, x, y) ->
        if k1 = k then Some v1 else getp k (if k < k1 then x else y)
    and putp k v = function `Empty -> `Node(k, v, `Empty, `Empty)
      | `Node(k1, v1, x, y) when k1 = k -> `Node(k, v, x, y)
      | `Node(k1, v1, x, y) -> if k < k1 then `Node(k1, v1, putp k v x, y)
                                         else `Node(k1, v1, x, putp k v y)

And it's about a third the size of the hash-table code. OTOH I spent the last hour writing it.

With four more lines of code it's also a sorting algorithm:

    and dictofp = function [] -> `Empty | (k, v)::xs -> putp k v (dictofp xs)
    and itemsp d = let rec iter d tl = match d with `Empty -> tl
      | `Node(k, v, x, y) -> iter x ((k, v) :: iter y tl)
                   in iter d []

Look:

    # List.map (fun (x, y) -> x) (itemsp (dictofp (List.map (fun x -> (x, x)) ["this"; "is"; "a"; "list"; "of"; "strings"])));;
    - : string list = ["a"; "is"; "list"; "of"; "strings"; "this"]

Of course the same comments about worst-case performance apply...