Binary Trees in Erlang

More Erlang goodness, today binary trees!

The record which describes a node

-record(node, {left=nil, load, right=nil}).

Insertion and preorder

-module(binary_tree).
-export([newnode/1, insert/2, preorder/1]).
-import(lists).
-include("binary_tree.hrl").

newnode(Load) ->
    #node{load=Load}.

newleaf(Load) ->
    {leaf, Load}.

isnil(Node) ->
    Node == nil.

insert({leaf, LeafLoad}, Load) ->
    if 
        LeafLoad > Load ->
            #node{left=newleaf(Load), load=LeafLoad};
        LeafLoad =< Load ->
            #node{load=LeafLoad, right=newleaf(Load)}
    end;
insert(#node{left=LeftNode,
             load=CurrentLoad,
             right=RightNode} = Node,
       Load) ->
    if
        CurrentLoad > Load ->
            case isnil(LeftNode) of
                true ->
                    Node#node{left=newleaf(Load)};
                 false ->
                    Node#node{left=insert(LeftNode, Load)}
            end;
        CurrentLoad =< Load ->
            case isnil(RightNode) of
                true ->
                    Node#node{right=newleaf(Load)};
                false ->
                    Node#node{right=insert(RightNode, Load)}
            end
    end.

preorder([], ValueList) ->
    ValueList;
preorder([Tree|TreeList], ValueList) ->
    case Tree of
        #node{left=Left, load=Load, right=Right} ->
            NewValueList = [Load|ValueList],
            NewTreeList = [Left|[Right|TreeList]],
            preorder(NewTreeList, NewValueList);
        {leaf, LeafLoad} ->
            NewValueList = [LeafLoad|ValueList],
            preorder(TreeList, NewValueList);
        nil ->
            preorder(TreeList, ValueList)
    end.
           
preorder(Tree) ->
    case Tree of
        #node{left=_Left, load=_Load, right=_Right} ->
            lists:reverse(preorder([Tree], []));
        nil ->
            []
    end.

Weeee....

Hello, World!

I've been writing many snippets of code. Some snippets do what I consider really nifty things. Some other pieces were written while I was learning a language, a framework, or just having fun. Most of them are deleted...

Why not post them? Clean them up a bit, add a short explanation, or a long one if I can. Maybe I can get some constructive criticism, or perhaps it is useful for someone out there. Considering what I just said, I think that posting is one good incentive to keep learning languages and frameworks and computer programming in general.

So here goes a snippet. The merge sort algorithm developed using the divide and conquer strategy in python.

def merge(xs, ys):
    """
    takes two ordered lists and merges keeping the order
    >>> merge([1,3,5,8],[2,4,6,7])
    [1, 2, 3, 4, 5, 6, 7, 8]

    >>> merge([1,2,6,9],[-2,-1,6])
    [-2, -1, 1, 2, 6, 6, 9]

    >>> merge([-10,-2], [1,2,3,4,5,6,7,8])
    [-10, -2, 1, 2, 3, 4, 5, 6, 7, 8]
    """

    merged_list = []
    x_index, y_index = 0, 0

    while (x_index < len(xs)) and (y_index < len(ys)):
        x, y = xs[x_index], ys[y_index]
        if x <= y:
            merged_list.append(x)
            x_index += 1
        else:
            merged_list.append(y)
            y_index += 1
        

    return merged_list + (xs[x_index:] or ys[y_index:])

def merge_sort(xs):
    """ Divide and conquer strategy in merge sort """

    # Divide the problem
    half = len(xs) / 2
    
    # If the list is empty or singleton then it's ordered
    if len(xs) <= 1: 
        return xs
    else: # Conquer
        first = xs[0:half]
        second = xs[half:len(xs)]
        return merge(merge_sort(first), merge_sort(second))

if __name__ == '__main__':
    import doctest
    doctest.testmod()