Thinking in Erlang - Coding in Everything Else

With apologies to Bruce Eckel.

Concurrent Programming in Erlang Part I uses a Binary Tree implementation to demonstrate Erlang's tuple data type.

Erlang

insert(Key, Value, nil) ->
    {Key, Value, nil, nil};
insert(Key, Value, {Key,_,Smaller, Bigger}) ->
    {Key, Value, Smaller, Bigger}; 
insert(Key, Value, {Key1,V, Smaller, Bigger}) when Key < Key1 ->
    {Key1, V, insert(Key, Value, Smaller), Bigger};
insert(Key, Value, {Key1, V, Smaller, Bigger}) when Key > Key1 ->
    {Key1, V, Smaller, insert(Key, Value, Bigger)}.

I was intrigued by this elegant approach to the Binary Tree.

Erlang's tuple data type collects the elements that make up a node including the node's key, value, and the references to its children nodes.

The first clause of the insert function is the "base case" that actually creates a new node. The second clause handles the case when the key is found and the value is simply replaced. Clauses three and four handle the cases that require traversal down through the tree.

Notice how the recursion is so wonderfully encoded. This is much cleaner and intuitive than the imperative solutions that I have worked with.

Python

def insert(key, value, tree):
    if tree == None:
        return (key, value, None, None)
    (key1, v1, smaller, bigger) = tree 
    if key == key1: 
        return (key1, value, smaller, bigger)
    if key1 > key: 
       return (key1, v1, insert(key, value, smaller), bigger)
    return (key1, v1, smaller, insert(key, value, bigger)) 

I would guess that this elegant Binary Tree implementation is common to functional programming languages in general. Python has some functional language capability and has a tuple data type. I was able to implement the "elegant" Binary Tree using Python.

JavaScript

function insert(key, value, tree) { 
    if(tree == null)
        return {key:key, value:value, smaller:null, bigger:null};
    if(tree.key == key){
        tree.value = value;
        return tree;
    }
    else if(key < tree.key)
        return {key:tree.key, value:tree.value, 
            smaller:insert(key, value, tree.smaller),
            bigger:tree.bigger};
    else
        return {key:tree.key, value:tree.value, 
            smaller:tree.smaller, 
            bigger:insert(key, value, tree.bigger)};
}

I have read that JavaScript is classified as a functional programming language and its object data type looks syntactically similar to Erlang's tuple. I was able to implement the "elegant" Binary Tree using JavaScript. For more fun, I created an interactive Binary Tree web page.