/dev/code

One of the things that has been bothering me about my "Duh!" moment is that it seems like a bit of a cop-out. I shouldn't have to use a list to represent a null reference - I should be able to represent it using the Empty | Node of 'a fh_node_rec. I decided to go back and make the code work the way I originally thought it should, and except for a few lingering bugs with decreasing a key value, I have the heap working with Empty representing null.

Two things that helped me a lot were the definition of an is_empty function:

let is_empty node =
    match node with
        Empty -> true
     | x -> false;;

and as as_fh_node_rec that is essentially like a cast (there may be a built-in way to do this in OCaml, I just don't know about it):

let as_fh_node_rec node =
    match node with
        Empty -> failwith "Expected fh_node_rec, found empty"
       | Node(n) -> n;;

When I need to refer to an fh_node_rec as a Node, I can just do Node(x). The combination of these things made the solution a little more palatable, but it is still a bit of an annoyance.