rainier ababao reads and writes

Binary search implementation in Erlang - what’s going on?

Let’s hack on some Erlang

Erlang was originally built in the late 80s to handle telecom switches. As such, its major features include primitives for concurrency and error recovery, which led to it making its way into applications requiring fault-tolerance, scalability, and maximum availability. I picked it up to learn more about concurrent programming and because it seemed hip.

Plus, here’s an awkwardly-funny video about one of its original uses in telephony:

Setup

If you’re on OSX and have Homebrew, you can install Erlang with brew install Erlang.

Now cd into a directory where you want to keep your file. To make things simpler, you’ll want to save your program and run the Erlang REPL from here, too. vim binary_search.erl, and let’s begin!

Writing the header

-module(binary_search).
-export([binary_search/2]).

What’s going on?

  • A module is just a bunch of functions regrouped into a single file, and has to be the first statement of the file.
  • We can use the name binary_search to call functions from this module into in other modules, in the form M:F(A), where M is the module name, F is the function name, and A is the arguments.
  • -export([binary_search/2]) defines which functions of the module can be called by the outside world, it describes the public interface of the module. It’s similar to how encapsulation in OOP restricts an object’s externally-usable components through the notions of public and private methods.
  • The export attribute has the format -export([Function1/Arity, Function2/Arity, ..., FunctionN/Arity]). The arity of a function or operator is the number of arguments or operands it takes. Thusly, binary_search has an arity of 2.

Guarding against incorrect types

The parameters of a binary search should be some comparable target value and a sorted list.

binary_search(X, List)
    when
        is_number(X),
        is_list(List) ->
    bs(X, lists:sort(List)).

What’s going on?

  • is_number and is_list are built-in functions of Erlang, and they do exactly what you’d expect. They are part of the erlang module, which is automatically imported whenever you use Erlang.
  • But every other function will have to be called in the M:F(A) format described in the last section (M - module name, F - function name, A - arguments)
    • In fact, this is how you will call every function you use in Erlang besides those in the erlang module.
    • You know how in Python, you can just from time import sleep, or in C, you #include <stdio.h> to add function names into the current namespace? Well, Erlang has a very flat namespace. This Stack Overflow link has a good explanation of how it works.
  • when is called a “guard” type of clause, and it tells us to perform the action following the -> if all statements between when and it are true.
  • Every function ends with a period. Whatever is the last expression of a function to be executed will have its value returned to the caller without it being mentioned.

The algorithm

The classic binary search algorithm. We will implement it recursively.

So, here’s how it looks in Erlang:

bs(_, [])   -> false;
bs(X, [_])  -> false;
bs(X, [X])  -> true;
bs(X, List) ->
    ok = io:format("bs(~p, ~p)~n", [X, List]),
    Length = length(List),
    Middle = (Length + 1) div 2,
    Value = lists:nth(Middle, List),
    if
        X == Value -> true;
        X > Value -> bs(X, lists:sublist(List, Middle + 1, Length));
        X < Value -> bs(X, lists:sublist(List, 1, Middle))
    end.

What’s going on?

  • The _ is the “don’t care” variable, which is a common thing to use in many languages (for instance, whenever you’re iterating and not using the counter, e.g. for _ in range(0, 10)). This also happens to silence a “unused variable” warning made by the Erlang compiler.
    • We see these in use for two of the base cases, and their placement makes sense if you think about it. Binary search of an empty list, list containing useless information, or target variable containing useless information should never be true.
  • We see use of pattern-matching. Instead of
function(Args)
   if X then
      Expression
   else if Y then
      Expression
   else
      Expression

We write:

function(X) ->
  Expression;
function(Y) ->
  Expression;
function(_) ->
  Expression.

The final code

Your file, binary_search.erl, should look something like this at the end:

-module(binary_search).
-export([binary_search/2]).

binary_search(X, List)
    when
        is_number(X),
        is_list(List) ->
    bs(X, lists:sort(List)).

bs(_, [])   -> false;
bs(X, [X])  -> true;
bs(X, [_])  -> false;
bs(X, List) ->
    ok = io:format("bs(~p, ~p)~n", [X, List]),
    Length = length(List),
    Middle = (Length + 1) div 2,
    Value = lists:nth(Middle, List),
    if
        X == Value -> true;
        X > Value -> bs(X, lists:sublist(List, Middle + 1, Length));
        X < Value -> bs(X, lists:sublist(List, 1, Middle))
    end.

Putting it to use

$ erl
Erlang/OTP 18 [erts-7.2.1] [source] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false] [dtrace]

Eshell V7.2.1  (abort with ^G)
1> c(binary_search).
{ok,binary_search}
2> binary_search:binary_search(2, [1, 2, 3, 4, 5]).
bs(2, [1,2,3,4,5])
bs(2, [1,2,3])
true

Cool! I know I left out a lot of stuff - mostly because I don’t want to rewrite all of Learn You Some Erlang for Great Good!

And I really hope this piques your interest to learn it more formally. If you want to learn more about Erlang, I highly recommend reading some of the links below.

Sources

[1] http://www.erlang.org/course/history.html
[2] http://veldstra.org/whyerlang/
[3] http://learnyousomeerlang.com/