Incorrect Values in Packed Data

[jazullo]

Consider this rbtree implementation Here is the same adapted for GHC The Gibbon code yields this error (from an assertion that I have defined):

~/llrbt$ ./rbtree_correct.exe
Unequal black heights!
R2 
B1 B4 
** ** B3 ** 
.. .. .. .. ** ** .. .. '#()

Note ** represents leaves and .. represents spaces. Successive lines down represent successive node depths. Children are printed in the order you would expect. The B and R prefixes indicate black and red nodes.

The error message occurs because the tree is incorrect. The GHC adaptation yields B3 as R3, which would resolve the black height invariant. Gibbon yields a black node, I assume during a rotation it obtained the color (represented as a packed bool, true for red) from the wrong location.

It may also be worth rerepresenting the color as packed nullary constructors R | B, this might work around the bug for color but values/integers are likely broken too.

[jazullo]

In an attempt to circumvent this issue, I replaced the packed boolean with the previously mentioned R | B type, but this seemed to make some things worse. I received L2 typechecking errors across several variations I tried, which seem to stem from the color variable getting lost. gist