/dev/code

I had a "Duh!" moment this evening. A "Duh!" moment is an "Aha!" moment where you say "Aha! I am an idiot!". I have been translating my Fibonacci Heap code from Lisp to OCAML. In my implementation, a heap node has left and right pointers for storing nodes in a circular list, and also parent and child pointers. Since a pointer could be null, I defined a type that could be either Empty or an fh_node_rec object, like this:

type 'a fh_node_rec = {
    mutable data : 'a;
    mutable parent : 'a fh_node;
    mutable left : 'a fh_node_rec;
    mutable right : 'a fh_node_rec;
    mutable child : 'a fh_node;
    mutable degree : int;
    mutable mark : bool;
} and 'a fh_node = Empty | Node of 'a fh_node_rec;;

So, mistake number one was that the left and right pointers were a different type from the parent and child. This got really complicated when I started processing the lists. When handling the left and right nodes, I could work directly with fh_node_rec types, but for parent and child, I had to use match, like:

match x with
    Empty -> ()
  | Node(xn) -> (* do something with xh as an fh_node_rec *)

I ended up defining multiple functions, some that worked with fh_node and others that worked with fh_node_rec. I started to have trouble keeping track of whether something was an fh_node or an fh_node_rec. I really had trouble when writing the consolidate function. In fact, I never could get it right.

I came across a paper called Design Patterns in OCaml by Antonio Vicente and Earl Wagner that suggested using a list to represent items that may be null, using [] to represent null. That's when I just wanted to slap my forehead for not thinking of it before. I was able to define a single record type:

type 'a fh_node = {
    mutable data : 'a;
    mutable parent : 'a fh_node list;
    mutable left : 'a fh_node;
    mutable right : 'a fh_node;
    mutable child : 'a fh_node list;
    mutable degree : int;
    mutable mark : bool;
};;

I was able to eliminate all the duplicate functions and I got the consolidate function written. It was much easier to see if a node was equal to [] than it was to see if it was either an Empty type or an fh_node. Once I get the rest of the code finished and working, I'll post it on my web site.