Begin main content

Trees in Erlang

Like every man and his dog I've been playing around with erlang (and a smattering of Haskell for good measure :). I thought I'd try to see how I might write a binary tree implementation Erlang.

I must confess it turned out much less elegant than I thought it might - maybe some erlang or other functional gurus can point out a better algorithm.

Now before you all comment, yes I know most of the below isn't tail recursive - but performance isn't really the issue here, and a binary tree implementation in erlang is going to be inefficient anyway if you're making frequent updates, since every recursion will involve copying some of the structure (maybe it optimises that away ... dunno enough about its internals to comment).

-module(tree).
-export([find/2, tree_of_squares/1, insert/3]).

-record(node, {key, val, left = nil, right = nil, height = 1}).

%% find/1
find(SearchKey, Node) whenSearchKey == Node#node.key ->
  {ok, Node#node.val};

find(_, nil) ->
       not_found;

find(SearchKey, Node) whenSearchKey < Node#node.key ->
  find(SearchKey, Node#node.left);

find(SearchKey, Node) ->
  find(SearchKey, Node#node.right).


%% tree_of_squares/1 : make a tree where key = val and contains
%% squares of all numbers from 1 to Maxtree_of_squares(Max) ->
  tree_of_squares(Max, nil).


tree_of_squares(0, Tree) ->
  Tree;

tree_of_squares(Max, Tree) ->
  insert(Max * Max, Max * Max, tree_of_squares(Max - 1, Tree)).

%% insert/3 : return a new tree made from inserting (or updating)
%% a node of Key, Val into existing tree or new tree (nil)
insert(Key, Val, nil) ->
       #node{ key = Key, val = Val };

insert(Key, Val, Node) whenKey == Node#node.key ->
       Node#node{ val = Val };

insert(Key, Val, Node) whenKey < Node#node.key ->
       balance(Node#node{ left = insert(Key, Val, Node#node.left)});

insert(Key, Val, Node) ->
       balance(Node#node{ right = insert(Key, Val, Node#node.right)}).

%% height/1 : return the height of the tree
height(nil) ->
       0;
height(Node) whenNode#node.left == nil, Node#node.right == nil ->
       1;

height(Node) ->
       height(1, Node#node.left, Node#node.right).

height(Acc, Left, Right)
 whenLeft == nil;
      Right#node.height > Left#node.height ->
       Acc + Right#node.height;

height(Acc, Left, _) ->
       Acc + Left#node.height.


%% balance/1 : return a new tree which is the balanced version of Tree
%% note also that balance is trusted to always return the root height set
%% correctly
balance(nil) ->
  nil;

balance(Node) whenNode#node.left == nil, Node#node.right == nil ->
       Node#node{ height = height(Node)};

balance(#node{ left = L, right = R} = Node) whenL#node.height ==
R#node.height ->
       Node#node{ height = height(1, L, R)};

balance(#node{ left = L, right = R} = Node)
 whenR == nil ;
      L#node.height + 1 > R#node.height ->
       swing_right(Node);


balance(#node{ left = L, right = R} = Node)
 whenL == nil ;
      R#node.height + 1 > L#node.height ->
  swing_left(Node).

swing_left(#node{right = #node{ left = RL, right = RR } = Right} = Node)

 whenRR == nil ; RR == nil, RL == nil ;
      RL#node.height > RR#node.height ->

       move_left(Node#node{right = move_right(Right)});

swing_left(Tree) ->
       move_left(Tree).

swing_right(#node{left = #node{ left = LL, right = LR} = Left} = Node)

 whenLL == nil ; LL == nil, LR == nil ;
      LR#node.height > LL#node.height ->

       move_right(Node#node{ left = move_left(Left)});

swing_right(Tree) ->
       move_right(Tree).


move_left(Node)
 whenNode == nil ;
      Node#node.left == nil, Node#node.right == nil ->
       Node;

move_left(#node{ right = #node{ left = RL } = Right} = Node) ->

       OldRoot = Node#node{ right = RL },
       NewRoot = Right#node{ left = OldRoot#node{ height = height(OldRoot)}},
       NewRoot#node{ height = height(NewRoot) }.


move_right(Node)
 whenNode == nil ;
      Node#node.left == nil, Node#node.right == nil ->
       Node;

move_right(#node{ left = #node{ right = LR } = Left } = Node) ->

       OldRoot = Node#node{ left = LR},
       NewRoot = Left#node{ right = OldRoot#node{ height = height(OldRoot)}},
       NewRoot#node{ height = height(NewRoot) }.
tree_of_squares is just to easily create an interesting tree to play with, for instance:

1> c(tree).
{ok,tree}
2> T = tree:tree_of_squares(7).
{node,25,
      25,
      {node,9,
            9,
            {node,4,4,{node,1,1,nil,nil,1},nil,2},
            {node,16,16,nil,nil,1},
            3},
      {node,36,36,nil,{node,49,49,nil,nil,1},2},
      4}
Then you can try to find a node:
3> tree:find(1, T).
{ok,1}
4> tree:find(2, T).
not_found
Not very interesting when the key = val - let's insert and update some entries:
5> T2 = tree:insert(5, bar, tree:insert(4, foo, T)).
{node,25,
      25,
      {node,9,
            9,
            {node,4,foo,{node,1,1,nil,nil,1},{node,5,bar,nil,nil,1},2},
            {node,16,16,nil,nil,1},
            3},
      {node,36,36,nil,{node,49,49,nil,nil,1},2},
      4}
6> tree:find(5, T2).
{ok,bar}
Fun huh!

An implementation of red-black trees is left as an exercise for the reader ;)

07:58 AM, 30 Nov 2007 by Mark Aufflick Permalink | Comments (2)

Computer Science

Computer Science is no more about computers than astronomy is about telescopes.

--E. W. Dijkstra

Great quote from the introduction of Algorithms with Perl

11:32 PM, 22 Nov 2007 by Mark Aufflick Permalink | Comments (0)

Apple Bric-A-Brac

While stuck in Apple-reminiscing mode (I'm reading Revolution in the Valley) I thought I'd see if someone in Apple was cool enough to have a server running on bric-a-brac.apple.com.

Unfortunately it seems noone at Apple is nearly that cool:

Failed to resolve the name of server bric-a-brac.apple.com to connect

11:19 PM, 18 Nov 2007 by Mark Aufflick Permalink | Comments (0)

Round Rects are everywhere in Leopard

I love a good Round Rect as much as the next guy (see Round Rects Are Everywhere) and I am really happy about menus being rounded in Leopard. I dunno what it is, it just makes me feel nice every time I drop open a menu!

06:36 AM, 18 Nov 2007 by Mark Aufflick Permalink | Comments (0)

Todo items - do they ever get done?

I was browsing around the various google sites tonight to see what had changed, and I thought I'd punch my name into google code, the search index for source code.

There are surprisingly few results, but even worse is that the second search result is:

v_name varchar2(4000); -- XXX aufflick fix this

So any prospective collaborator or employer discovers that I have an un-done todo dating back to March 5 2003! And there's not even any comments suggesting what needs fixing. Oh well, it's in use in hundreds of production systems with tens of thousands of users, so I guess it doesn't really need fixing after all!

04:28 AM, 15 Nov 2007 by Mark Aufflick Permalink | Comments (0)

Parsing ini files with sed

A while back I found this neat sed pipeline for extracting an ini file section into shell script variables:

INI_FILE=path/to/file.ini
INI_SECTION=TheSection

eval `sed -e 's/[[:space:]]*\=[[:space:]]*/=/g' \
    -e 's/;.*$//' \
    -e 's/[[:space:]]*$//' \
    -e 's/^[[:space:]]*//' \
    -e "s/^\(.*\)=\([^\"']*\)$/\1=\"\2\"/" \
   < $INI_FILE \
    | sed -n -e "/^\[$INI_SECTION\]/,/^\s*\[/{/^[^;].*\=.*/p;}"`
You now have variables in the scope of your shell script derived from the key/value pairs in that section of the ini script. REALLY handy. Thought it might help someone else if I recorded it here. I got it from this thread on debian-administration.org.

NB: the eval is a ksh builtin. I imagine using declare in bash will achieve the same, but I haven't tested it.

NB2: it seems Solaris sed isn't quite up to the task - the above requires gnu sed.

01:07 AM, 08 Nov 2007 by Mark Aufflick Permalink | Comments (2)

XML

Blog Categories

software (41)
..cocoa (23)
  ..heads up 'tunes (5)
..ruby (6)
..lisp (4)
..perl (4)
..openacs (1)
mac (21)
embedded (2)
..microprocessor (2)
  ..avr (1)
electronics (3)
design (1)
photography (26)
..black and white (6)
..A day in Sydney (18)
..The Daily Shoot (6)
food (2)
Book Review (2)

Notifications

Icon of envelope Request notifications

Syndication Feed

XML

Recent Comments

  1. Mark Aufflick: Re: the go/Inbox go/Sent buttons
  2. Unregistered Visitor: How do make a button to jump to folder
  3. Unregistered Visitor: Note I've updated the gist
  4. Unregistered Visitor: umbrello is now an available port on macPorts
  5. Unregistered Visitor: Updated version on Github
  6. Unregistered Visitor: Modification request.
  7. Unregistered Visitor: Accents and labels with spaces
  8. Unregistered Visitor: Mel Kaye - additional info
  9. Unregistered Visitor: mmh
  10. Mark Aufflick: Thank you