Leftist priority queues in SML

lheap.sml

signature KEY =
sig
    type t
    val compare : t * t -> order
end

signature PQUEUE =
sig
    type t
    type key

    val empty  : t
    val insert : key -> t -> t
    val min    : t -> key option
    val delete : t -> t
end

functor LHeap (Key : KEY) : PQUEUE =
struct

type key = Key.t
datatype t = Empty
           | Node of { rank  : int
                     , left  : t
                     , value : key
                     , right : t }

val empty = Empty

fun rank Empty = 0
  | rank (Node {rank = r, ...}) = r

fun mkNode l v r =
    case Int.compare (rank l, rank r) of
        LESS => Node { rank  = rank l + 1
                     , left  = r
                     , value = v
                     , right = l }
     | _ => Node { rank  = rank r + 1
                 , left  = l
                 , value = v
                 , right = r }

fun single v = Node {rank = 1, left = Empty, value = v, right = Empty}

fun merge Empty r = r
  | merge l Empty = l
  | merge (l as Node {left = ll, value = lv, right = lr, ...})
          (r as Node {left = rl, value = rv, right = rr, ...}) =
    case Key.compare (lv, rv) of
        LESS => mkNode ll lv (merge lr r)
      | _ => mkNode rl rv (merge l rr)

fun insert v t = merge t (single v)

fun min Empty = NONE
  | min (Node {value = v, ...}) = SOME v

fun delete Empty = Empty
  | delete (Node {left = l, right = r, ...}) = merge l r

end