Chewing The Cud

Working through Chris Okasaki’s “Purely Functional Data Structures“, I found that I couldn’t find an Erlang version of the red-black tree implementation Chris shows on page 28.

The code, also available as a pastie and download (with more comments of mine) .erl and .hrl:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

%% redblack.hrl
-record(node, {color, data, left, right}).
 
%% redblack.erl
%% Adapted from Okasaki "Purely Functional Data Structures" p. 28
member(_X, undefined) ->
    false;
member(X, #node{left=A, data=Y}) when X < Y ->
    member(X, A);
member(X, #node{data=Y, right=B}) when X > Y ->
    member(X, B);
member(_X, _S) ->
    true.
 
insert(X, undefined) ->
    #node{color=black, data=X};
insert(X, S) ->
    % to do recursive anonymous functions, pass the created fun in as 2nd parameter
    Ins = fun(undefined, _F) ->
                  #node{color=red, data=Data}; % insert the new data as a red node
             (#node{color=Color, left=A, data=Y, right=B}, F) when X < Y->
                  balance(Color, F(A, F), Y, B);
             (#node{color=Color, left=A, data=Y, right=B}, F) when X > Y->
                  balance(Color, A, Y, F(B, F));
             (Node, _F) ->
                  Node
          end,
    #node{left=A, data=Y, right=B} = Ins(S, Ins),
    #node{color=black, left=A, data=Y, right=B}.
 
%% detect Black->Red->Red Patterns and balance the situation
balance(black, #node{color=red, left=#node{color=red, left=A, data=X, right=B}, data=Y, right=C}, Z, D) ->
    #node{color=red, left=#node{color=black, left=A, data=X, right=B}, data=Y, right=#node{color=black, left=C, data=Z, right=D}};
balance(black, #node{color=red, left=A, data=X, right=#node{color=red, left=B, data=Y, right=C}}, Z, D) ->
    #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}};
balance(black, A, X, #node{color=red, left=#node{color=red, left=B, data=Y, right=C}, data=Z, right=D}) ->
    #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}};
balance(black, A, X, #node{color=red, left=B, data=Y, right=#node{color=red, left=C, data=Z, right=D}}) ->
    #node{color=red, left=#node{color=black, left=A, data=X, right=B }, data=Y, right=#node{color=black, left=C, data=Z, right=D}};
balance(Color, Left, Data, Right) ->
    #node{color=Color, left=Left, data=Data, right=Right}.

So, I’m going to go through this, mainly to prove to myself that I kinda get it, and because Ben will complain I didn’t dumb it down enough for him.

Line 2 defines the node structure in an Erlang header file. Comparable to a struct in C.

Member

Lines 6-13 define the member function. Each member() -> … is a function clause, essentially a case statement on steroids. The first clause says if the tree is undefined, then whatever X is, it is not a member of undefined, so return false.
The second clause unpacks the current node ( #node{left=A, data=Y} ) and assigns the values of left and data to A and Y, respectively (I have tried to maintain Chris’s variable names as much as possible, though I think Erlang’s record syntax complements the Standard ML syntax found in the book). The clause then compares Y, the node’s data, to the query X, and if X < Y, checks the left branch (the variable A) of the node.
The third clause is nearly identical, except it handles when X > Y, and checks the right branch (B) for X’s existence.
The fourth and final clause handles a match (because when X is not greater than or less than Y, it must be equal), returning true. Simple enough to follow and grok.

Insertion

When I read several different articles online concerning red-black trees, the insertion routine sounded quite complex to me. I was quite pleased when I read the algorithm in the book, as it crystallized my thoughts and allowed me to grok the action.

The first clause of the insert function handles the empty (or undefined) tree, creating and returning a black node (since the root of the tree must be black).
The second clause takes the new data X and a tree S and creates a new function, stored in the var Ins. Now, calling an anonymous function recursively is tricky, and I will explain why this part varies slightly from the text. Since there’s no way to refer to the function (as it isn’t named), we have to pass the anonymous function as a second parameter to the anonymous function, which is what happens on line 28. So when you see F(A, F), mentally think Ins(A).
The first parameter to Ins() is our current node in the tree. If it is undefined, we insert our new data as a red node. Why? That is discussed at length elsewhere, but it boils down to being easier to fix a red violation than a black violation (look up the constraints a red-black tree has on it, and the violations will make more sense).
The second clause unpacks the node and makes our less than/greater than comparison like a normal BST. What’s different is that we call the appropriate recursive insert call (remember F(A, F)? This inserts X somewhere into the left side of Node, and F(B, F) inserts X somewhere into the right side), and pass the result to the balance function.
The final clause handles a match between X and Y and returns the Node and its branches unmodified.

Balance

Why do we need a balance function? In case our data being inserted into the tree is more ordered than we may have expected. A vanilla BST with inputs [3,2,1] will be a glorified list. We force the situation by inserting a red node in the tree and causing a situation where the parent of the newly inserted red node is also a red node. This violates the constraint that a red node’s children must be black nodes. There are four possible combinations of this violation:

1. (B)-Left->(Red)-Left->(Red)
2. (B)-Left->(Red)-Right->(Red)
3. (B)-Right->(Red)-Left->(Red)
4. (B)-Right->(Red)-Right->(Red)

Each of those possibilities maps to the first four clauses of the balance function. The fifth clause passes a node back unchanged. So let’s look at the first clause. This clause is activated when a black node’s left child is red, and that red node’s left child is also red.

      B3
     /   \
   R2     *
  /   \
R1     *

So we unpack the three nodes and return the three nodes rotated to remove the red violation.

Unpacking from the pattern match, we then pack up a new tree structure according to the clause’s definition:

33

#node{color=red, left=#node{color=black, left=A, data=X, right=B}, data=Y, right=#node{color=black, left=C, data=Z, right=D}};

This essentially replaces the black node having a red child and red grandchild with a red node that has two black nodes for children. The next illustration shows the result of the balance call:

      R2
     /   \
   B1    B3

Now, the bubbling up of the red node may cause a red violation with the parent and grandparent of R2, which will be handled as the recursion of Ins() unwinds.

When the initial Ins() ends (line 28), the resulting node is the root of the new tree, which we then unpack into the data, left, and right fields. We then force the root node to be black by creating the root node with the unpacked parts, forcing color=black.

So there you have it. Simplified, with a lot of things glossed over/ignored, but this is my port of the red-black code listing on page 28. Looking forward to progressing through the book more and increasing my data structure- and Erlang-fu.

Further fun: Read Chris’s reflections 10 years after publishing his book.

If you have gotten the above error in your syslog, you probably are not able to connect to wireless APs that require WPA passphrases, but can connect to ones that require WEP or no security. While searching for solutions, there were some that offered solutions for controlling the power of the card (for temperature-related issues), but those did not address my issue. Fortunately, the solution was fairly simple for my problem.

I have Ubuntu Jaunty, with the 2.6.28-15 kernel. The resolution came when I looked in synaptic at the installed linux-restricted-modules and found I had two instances from older kernels still installed. Purging those completely from the system, and retrying to connect to my WPA2-enabled AP succeeded.

Give it a shot.

The Fibonacci sequence: teacher of recursion for so many Computer Science students. But can it also teach us about streams? Yes! The function to build a stream (in Javascript):

var fib_stream_maker = function() {
  return (function() {
    var a = 0;
    var b = 0;
    var c = 1;
 
    return function() {
      a = b;
      b = c;
      c = a + b;
      return c;
    }
  })();
}

Let’s break this down so Ben can follow along. First, the inner most function:

return function() {
  a = b;
  b = c;
  c = a + b;
  return c;
}

This anonymous function returns the next number in the sequence. Looking one level of scope higher, we see the variables a, b, and c declared:

function() {
  var a = 0;
  var b = 0;
  var c = 1;
 
  return function() {
    a = b;
    b = c;
    c = a + b;
    return c;
  }
}

So we initialize the variables and then return a function that increments those variables, local to the inner function’s scope, so we can have multiple instances of the function running without collision of variables. To build the stream factory, we wrap the initialization function in parentheses, creating a continuation, and then execute the wrapped function, creating an initialized fib stream function. This is then set to return when the fib_stream_maker is called as a function.

var fib_stream = fib_stream_maker();
 
fib_stream(); // returns 1
fib_stream(); // returns 2
fib_stream(); // returns 3
fib_stream(); // returns 5
fib_stream(); // returns 8, etc...

This is only touching the surface of streams but I thought it was pretty cool that the Fibonacci sequence can be utilized to teach such important concepts as continuations and streams. Code on!

*Update*

While explaining the inner workings of the above code to CD, she asked a very astute question, one that Ben probably would not have, “What about going backwards in the stream?” A just question. Let’s look at a table of how the values of a, b, and c act as the stream goes forward first (this will help us design our algorithm later).

So to go backwards, what do we need to do to values of a, b, and c? We need to assign b’s value to c, a’s value to b, and the difference of c and b to a, and still return c. In code, this would look like:

c = b;
b = a;
a = c - b;
return c;

To integrate this into the above example, we need to pass a boolean parameter to the inner-most lamda function and test to see whether to forward or reverse the stream. Let’s see the inner-lamda now:

return function(go_forward) {
  if ( go_forward ) {
    a = b;
    b = c;
    c = a + b;
  } else {
    c = b;
    b = a;
    a = c - b;
  }
 
  return c;
}

We may want to put an additional test to see if we are at the beginning of the stream again:

return function(go_forward) {
  if ( go_forward ) {
    a = b;
    b = c;
    c = a + b;
  } else if ( a == 0 && b == 0 ) {
    ; // do nothing
  } else {
    c = b;
    b = a;
    a = c - b;
  }
 
  return c;
}

Let’s see it all as one big fun function:

var fib_stream_maker = function() {
  return (function() {
    var a = 0;
    var b = 0;
    var c = 1;
 
    return function(go_forward) {
      if ( go_forward ) {
        a = b;
        b = c;
        c = a + b;
      } else if ( a == 0 && b == 0 ) {
        ; // do nothing
      } else {
        c = b;
        b = a;
        a = c - b;
      }
      return c;
    }
  })();
}

And there you have it. Thanks CD for bringing up this interesting idea! What a nerd!