For some time I've been wanting to implement the Enfilade, a really
cool data structure discovered by the Xanadu people among others. It's
like a balanced tree, except that it's indexed relatively rather than
absolutely – making it ideal for things like text editor buffers, as
you can insert and delete with impunity, knowing that the changes to
the address of pieces to your right will percolate up the tree.

As there isn't already an implementation on Perl's CPAN I've occasionally planned to do it for fun.

Problems: 1) I'm lazy, and 2) I'm weak in Computer Science, so I
don't even know how to do the balanced binary tree that I need as a
basis. I looked on CPAN some time back, which has some implementations
of trees, but I couldn't figure out how to get them relatively indexed,
and besides which, it's always instructive to implement something for
yourself.

I bought Okasaki's “Purely Functional Data Structures” some time
back, in a fit of enthusiasm, read the first chapter (a very readable
introduction) and been utterly terrified by the rest of it. But
recently I picked it up off the shelf, read and mostly understood the
chapter on Red Black trees, and had a go implementing it with Perl.

Why a purely functional version? As Okasaki says, the algorithm is
simpler than the destructive one (and potentially very fast). Also I
think that having a persistent, functional tree will make it trivial to
implement things like “undo”.

A quick look at the algorithm suggested that I might want lazy
building of the tree structure, and that reminded me of the overview in
Moose's cookbook about a lazy binary tree.

Oddly, the Moose example has “parent” fields, which rather defeat
the point of sharing, but then again Moose is an OO base class, not an
FP language so fair enough. But I've been meaning to learn Moose for a
while so this seemed like a perfect opportunity.

Five hours later (I'm a bit slow, but I suppose that's not bad as
I'm grokking a new library and an algorithm at the same time) I have a
working implementation.

Some notes:

• Moose's “lazy” fields are cute! Actually,
  in the end, I didn't use them as the algorithm itself was strict (I
  just created a base case using an Empty node class instead.
• “coerce” is lovely. I let the left and right branches be coercable from
  • a node (oddly, you have to specify this case explicitly!)
  • undef (for an empty node)
  • hashref (to create a node initialised with that data)
  • other (set the data field to that value)

  which made the code very neat and DWIMmy.

• Perl doesn't have algebraic datatypes, so I simulated them with object classes:
  

      Node
      |-> Node::E   - empty node
      `-> Node::T   - full node
  

• Pattern matching allows the MLian languages to do the
  Red-Black balancing in 4 lines. But they are 4 dense, ugly lines, that
  check 2×2 cases manually, and from which it's very hard to understand
  the intent. Okasaki's diagram was much more helpful. I contemplated
  • implementing pattern matching for Nodes (or a generic pattern matching for Perl :-)
  • doing a hand coded mess of if {} else {} blocks just to get it working

  In the end I rejected those and looped the cases [L,L], [L,R], [R,L], [R,R]
  storing the details of the path on the way down, and then working back
  up to do the rotation. I think the intent is much clearer, but it is a
  fair bit more verbose.

• Debugging an algorithm that you don't
  understand is hard. I scratched my head for an hour with an unpleasant
  bug because I'd forgotten to clone a node before balancing it. (This is
  part of the mismatch between FP and Perl – you can do Purely
  Functional in Perl, but the language doesn't enforce it in any way, so
  you end up maintaining a situation whereby the public API is
  functional, but within a subroutine you can mutate the thing you're
  working on. End result of this is that you have to keep track of
  whether you've mutated something and therefore need to clone it first.
  And that means you'll sometimes get it wrong…)
• I don't
  really understand how the Red-Black invariants are enforced by the
  rotations, but working through this on paper (and later with a pretty
  printer) you can see that it really works… wheee!
• That is
  to say, I can see the constraint about 2 reds in a row, as it means
  that you can't ever have a mismatch of depths without triggering a
  rebalance. But the “constant number of blacks to the leaf” is
  mysterious.
• I don't understand the optimizations Okasaki
  suggests in Exercises 2.2 and 3.10 re not doing too many comparisons,
  and not rebalancing uselessly. Will come back to this.
• Okasaki suggests that the algorithm is very fast, even without those
  optimizations… but my Mooseperl version was not… Of course I'm
  doing “Object Functional” but I had the feeling that Moose was giving a
  fair amount of overhead.

  This isn't a criticism of Moose of course – it's designed for OO
  systems, and there, the amount of work that Moose does makes your code
  powerful and readable, and some Very Clever People in the Perl world
  are developing it, using it, and making it fast.

  But an FP algorithm uses many short lived structures, which may make
  this overhead untenable. Certainly my test script was noticeably slow,
  and profiling may have pointed to Moose as the culprit.

• I say may but Devel::DProf is a buggy piece of shit and suggests that my script completed in negative time, which is not confidence-inspiring.

  Actually the other profiling modules (like DProfLB – where LB stands for “Less Bad” seem to do the same thing) Pah.

• Moose is beautiful, powerful, and well documented. It seems to be
  robust, and gives a lot of the goodness of Perl6 and Ruby, while being
  respectively not vapourware, and still Perl.

  It makes certain aspects of implementing algorithms in an FP style
  very neat to prototype, but seems to be impractical due to the overhead
  on short-lived objects. I wouldn't have any reservations to using it
  for an OO class though!

• I rewrote the class in
  non-moosey Object/Functional Perl, and as expected, this runs in a more
  reasonable time. Still need to optimize etc., but it's faster, while
  some of the code is clunkier than the Moose equivalent.

You can see the Moosey and non-Moosey code in my svn repo.