Tuple based tree implementation in Erlang (from LYSE) and Python

notes.txt

The no. of lines in erlang implementation is half that in python!
Observe how pattern matching alone gets rid of the selector functions

tree.erl

-module(tree).
-export([empty/0, insert/3, lookup/2]).

%% build an empty node
empty() -> {node, 'nil'}.


%% insert will take 3 args - key, value and a node
%% and add a new node with the Key and Value to the Node
insert(Key, Val, {node, 'nil'}) ->
    {node, {Key, Val, {node, 'nil'}, {node, 'nil'}}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->
    {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->
    {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}};
insert(Key, Val, {node, {Key, _, Smaller, Larger}}) ->
    {node, {Key, Val, Smaller, Larger}}.


%% lookup function
lookup(_, {node, 'nil'}) ->
    undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
    {ok, Val};
lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->
    lookup(Key, Smaller);
lookup(Key, {node, {_, _, _, Larger}}) ->
    lookup(Key, Larger).

tree.py

#!/usr/bin/env python

def empty():
    return ('node', None)

def is_empty(node):
    return len(node) == 2 and node[1] is None

def create_node(key, val, smaller, larger):
    return ('node', (key, val, smaller, larger))

def get_key(node):
    return node[1][0]

def get_val(node):
    return node[1][1]

def get_smaller(node):
    return node[1][2]

def get_larger(node):
    return node[1][3]


def insert(key, val, node):
    
    # if node is empty, create a new node with smaller and larger
    if is_empty(node):
        return ('node', (key, val, empty(), empty()))
    
    # else if key < key of node, add a node to smaller
    nodekey, nodeval, smaller, larger = get_key(node), get_val(node), get_smaller(node), get_larger(node)
    if key < nodekey:
        return create_node(nodekey, nodeval, insert(key, val, smaller), larger)

    # else if key > key of node, add a node to larger
    if key > nodekey:
        return create_node(nodekey, nodeval, smaller, insert(key, val, larger))

    # else if key = key of node, replace with latter
    if key == nodekey:
        return create_node(nodekey, val, smaller, larger)


def lookup(key, node):
    if is_empty(node):
        return None

    if key == get_key(node):
        return ('ok', get_val(node))

    if key < get_key(node):
        return lookup(key, get_smaller(node))

    if key > get_key(node):
        return lookup(key, get_larger(node))