Ruslan’s Blog

In this short tutorial we will take a look at comparison operations, some arithmetic operations and modules. You may also want to skim over Inro and Part I.

Comparison operations

 Python   Erlang   Description             Erlang Example
 --------+--------+-----------------------+----------------
  <        <        strictly less than
 --------+--------+-----------------------+----------------
  <=       =<       less than or equal
 --------+--------+-----------------------+----------------
  >        >        strictly greater than
 --------+--------+-----------------------+----------------
  >=       >=       greater than or equal
 --------+--------+-----------------------+----------------
  !=       /=       not equal
 --------+--------+-----------------------+----------------
  ==       ==       equal                   1> 1 == 1.
                                            true
                                            2> 1 == 1.0.
                                            true
 --------+--------+-----------------------+----------------
           =:=      exactly equal to        1> 1 =:= 1.
                                            true
                                            2> 1 =:= 1.0.
                                            false
 --------+--------+-----------------------+----------------
           =/=      exactly not equal to
 --------+--------+-----------------------+----------------
  is                object identity
 --------+--------+-----------------------+----------------
  is not            negated obj identity

Python notes

Above comparison operations are supported by all objects. In Python you can chain comparisons:

>>> x, y, z = 1, 3, 7
>>> x < y <= z
True
>>> x < y and y <= z
True

Foregoing examples are identical, except that in second case y is evaluated twice.

Erlang notes

Following order is defined:

number < atom < reference < fun < port < pid < tuple < list < binary

1> 5 < erlang.
true
2> erlang < make_ref().
true

Both Erlang comparison operators (<, =<, >, >=, /=, ==) and Python comparison operators(<, <=, >, >=, !=, ==) make type coerce, “narrower” type is widened to that of another, ie when comparing integer and float first integer is converted to float, etc.
Erlang has special operators without type coerce though: =:= and =/=

Arithmetic operations

I’ll provide only several operations, for more take a look at corresponding language references.

 Python   Python Desc.         Erlang    Erlang Desc.   Example
 --------+--------------------+---------+--------------+--------------------
  x % y    remainder            X rem Y   integer        >>> 7 % 3
           of x / y                       remainder      1
                                          of X / Y       >>> 7.0 % 3
                                                         1.0

                                                         1> 7 rem 3.
                                                         1
                                                         1> 7.0 rem 3.
                                                         =ERROR REP..
 --------+--------------------+---------+--------------+--------------------
  x / y    quotient             X / Y     floating       >>> 7 / 3
           of x and y                     point          2
                                          division       >>> 7.0 / 3
                                                         2.3333333333333335

                                                         1> 7 / 3.
                                                         2.33333
 --------+--------------------+---------+--------------+--------------------
  x // y   (floored) quotient   X div Y   integer        >>> 7 // 3
           of x and y,                    division       2
           integer division                              >>> 7.5 // 3
           (result type is                               2.0
           not forced to be
           int)                                          1> 7 div 3.
                                                         2

Modules

Code in Erlang is organized into units called modules, which is familiar word for Python programmer.

Let’s define sample module with function declaration stored in file mymath.erl :

-module(mymath).
-export([fact/1]).

fact(0) -> 1;
fact(N) -> N * fact(N-1).

What we see here:

1. module’s source code is stored in file with .erl extension
2. module consists of attributes and function declarations which are terminated by period (.)
3. we should provide module declaration defining name of the module

• module name should be atom
• module name is the same as file name minus .erl extension
• module declaration is mandatory
• module declaration attribute should be defined first.

To make functions defined in module accessible outside the module we need to export them, for this -export module attribute exists. We write exported functions inside square brackets in form of func/N where N is the number of arguments of function, called arity. I’ll repeat that functions not pointed in -export will not be accessible outside module.

Before code can be run, module must be compiled. Resulting compiled file will contain extension .beam

If you use Emacs you can compile module with C-c C-k and see results in erlang shell:

1> c(”/home/alienoid/dev/erlang/mymath”, [{outdir, "/home/alienoid/dev/erlang/"}]).
{ok,mymath}

Or you can compile it directly in shell. Make sure your shell’s current directory is where your mymath.erl lives, if it’s not the case use cd command in erlang shell, cd(”/path/to/dir/with/mymath.erl”) :

1> c(mymath).
{ok,mymath}

To invoke our function fact we use syntax mod:func :

2> mymath:fact(4).
24

Erlang has also -import attribute which allows to import functions into modules, so that you don’t need to use fully-qualified name mod:func to invoke function, again familiar behaviour and naming to Python programmer.

Erlang allows to insert code from file as-is with -include attribute at point where -import is defined, this is used to include records and macro definitions, for example.

Comments in Erlang module begin with character “%“, continue up to end-of-line and may be placed anywhere except inside string and quoted atoms.
Like in Python Erlang has no multiline comments.
If you use Emacs you can easily comment whole region with M-; command after you marked it.

-module(mymath).
-export([fact/1, print_double/1]).
-import(lists, [foreach/2]).
-include(“my_records.hrl”).

%% sum(L) ->
%%     sum(L, 0).

%% sum([H|T], Acc) ->
%%     sum(T, H+Acc);
%% sum([], Acc) -> Acc.

fact(0) -> 1;
fact(N) -> N * fact(N-1).
print_double(L) ->
    foreach(fun(X) -> io:format(“Double of ~p = ~p~n”, [X, X*2]) end, L).

Fin.

Next tutorial will be devoted to thorough exploration of functions in Erlang.

When i was describing notations and representation of numbers in Erlang(and Python) i forgot to mention very cool feature of format function in Common Lisp, with which i got acquainted exploring highly-recommended Practical Common Lisp book.

This feature is ~R directive which knows how to say really big numbers in English words.

Here is the example (I use SBCL + SLIME):

CL-USER> (format nil “~R” 1604872898756737459538)
“one sextillion six hundred four quintillion eight hundred seventy-two
quadrillion eight hundred ninety-eight trillion seven hundred fifty-six
billion seven hundred thirty-seven million four hundred fifty-nine
thousand five hundred thirty-eight”

Let’s skim over data types in Erlang today. Check previous tutorial for introduction.

Numbers

In Erlang there are two types of numeric literals: integers and floats.
In Python there are four of them: plain integers(usually called just integers), long integers, floating point numbers, and imaginary numbers.

In addition to conventional notation Erlang has its own specific notations:
1) $char
Gives ASCII value of char
2) base#value
Produces integer. Base is in range [2,36]

1> $A.
65
2> 2#111.
7
3> 16#1A.
26
4> 5.
5
5> 2.55.
2.55000

In Python we can define octinteger and hexinteger correspondingly with:

>>> 017, 0×1A
(15, 26)

To produce integer from different bases in Python we may use built-in int([x[, radix]]), where radix is in range [2,36]:

>>> int(”111″, 2), int(”1A”, 16)
(7, 26)

Atom

An atom is a literal or a constant with name. Atoms should start with small letter or it should be enclosed in single quote(’) if it contains other characters than alphanumeric characters, _, or @.
Atoms can not have values like variables, they are simply names (constant with name).

1> erlang.
erlang
2> ‘hello world’.
‘hello world’
3> ‘Erlang’.
‘Erlang’

In Python there are also atoms in form of identifiers or literals, but no correspondence with Erlang’s constant with name type of atom.

More examples with atoms to come when we get acquainted with other data types
and parts of Erlang.

Binary

From a reference manual:
“A binary is used to store an area of untyped memory.
Binaries are expressed using the bit syntax.”

This data type allows to store large raw chunks of memory in an efficient way, much more space-efficient than in lists or tuples.

Binaries are written in double less-than and greater-than brackets and printed in that form as well.
They can be constructed from set of constants or string literal:

1> <<1,2,3>>.
<<1,2,3>>
2> <<”erlang”>>.
<<”erlang”>>

Or from bound variables:

3> A = 1, B = 2, C = 3.
3
4> Bin = <<A, B, C>>.
<<1,2,3>>

Remember pattern matching ?
Binary (Bin for short) can also be used for matching:

5> <<X, Y, Z>> = Bin.
<<1,2,3>>
6> X.
1
7> Y.
2
8> Z.
3

There is more than that, namely bit syntax which allows to pack/unpack sequences of bits in Bin. Actually bit syntax is an extension to pattern matching.
Let’s pack three variables into 16 bit memory area in a variable Mem, then unpack it to another three variables using bit syntax:

1> X = 2.
2
2> Y = 40.
40
3> Z = 30.
30
4> Mem = <<X:3, Y:7, Z:6>>.
<<74,30>>
5> <<X1:3, Y1:7, Z1:6>> = Mem.
<<74,30>>
6> X1.
2
7> Y1.
40
8> Z1.
30

In foregoing output you see that after packing shell prints packed three variables as <<74,30>> which is 16 bits.

In Python 2.5 there is no built-in data type to support binary data, but in Python 3000 binary data is represented by a separate mutable “bytes” data type.

Fun

Fun is an anonymous function, ie without name.

In Python this is infamous lambda, which had many debates whether it should remain in language or not. Personally i like lambda and glad it survived and will continue its life in Python 3000.

But Ok, back to Erlang’s Fun. Here how we can define it in shell:

1> Double = fun(X) -> X * 2 end.
#Fun<erl_eval.6.56006484>
2> Double(4).
8

In contrast to Python Erlang’s Fun can contain statements and is “more advanced” in general:

1> Print_val = fun(X) -> io:format(”X = ~p~n”, [X]), X*2 end.
#Fun<erl_eval.6.56006484>
2> Print_val(3).
X = 3
6

>>> print_val = lambda x: print ‘x = %d’ % x; x*2
  File “<stdin>”, line 1
    print_val = lambda x: print ‘x = %d’ % x; x*2
                              ^
SyntaxError: invalid syntax
>>> print_val = lambda x: x*2
>>> print_val(3)
6

More advanced examples of Fun like Funs with several different clauses i’ll show when discussing in details functions in Erlang in upcoming tutorials.

Tuple

It’s a compound data type with fixed number of terms (Term is a piece of data of any data type). Number of elements in tuple is called size of tuple.
Syntax of tuples is:

1> Tuple = {ruslan, 28}.
{ruslan,28}
2> Info = {data, Tuple}.
{data,{ruslan,28}}

In Python tuples are defined with or without enclosing parentheses:

>>> tup = “ruslan”, 28
>>> tup
(’ruslan’, 28)
>>> info = (’data’, tup)
>>> info
(‘data’, (’ruslan’, 28))

To get number of elements in tuple.

Erlang:

3> size(Info).
2

Python:

>>> len(info)
2

List

List is a compound data type with variable number of terms. Number of elements in a list is called length of the list.

List is declared in square brackets like in Python.

1> List = [1, 2, 3, "erlang"].
[1,2,3,"erlang"]

Now Erlang specific part, which may be familiar to you if you know a bit Lisp and its CAR/CDR stuff:
List is either an empty list [] or may be represented as head (first element - CAR in Lisp) and tail (remainder of list - CDR in Lisp) which is also a list and often you can see it in form like [H|T].
This representation is recursive:
[]
[c | []]
[b | [c | []]]
[a | [b | [c | []]]]
are all lists actually.

Let’s define list in shell:

1> List = [a, 1, {b, 2}].
[a,1,{b,2}]

and unpack it with pattern matching to head and tail:

2> [H|T] = List.
[a,1,{b,2}]
3> H.
a
4> T.
[1,{b,2}]

As you see T(tail) above is also a list.

We can also construct list using head and tail syntax:

5> List2 = [c|T].
[c,1,{b,2}]

Working with Erlang you’ll see/use this syntax quite often.

To get number of elements in list.

Erlang:

6> length(List2).
3

Python:

>>> len([1, 2, 3, "python"])
4

String

In Python string type is immutable sequence of characters. In Python there is no separate character type, a character is represented by a string of one item. String literals are written in single or double quotes:

>>> ‘xyz’, “xyz”
(‘xyz’, ‘xyz’)

In Erlang strings are enclosed in double quotes, but unlike Python string is not separate data type actually. String “erlang” is just shorthand for list [$e, $r, $l, $a, $n, $g].

Adjacent string literals are concatenated at compile time:

1> “hello” “, world” ” in ” “erlang”.
“hello, world in erlang”

In Python behaviour with adjacent strings is the same:

>>> ‘hello’ ‘, world’ ‘ in ‘ ‘python’
‘hello, world in python’

Boolean

Again unlike Python Erlang has no built-in Boolean type, but it uses atoms true and false to denote Boolean values:

1> 1 < 2.
true
2> true or false.
true

In Python Boolean is separate data type:

>>> type(True), type(False)
(<type ‘bool’>, <type ‘bool’>)
>>> 1 < 2
True
>>> True or False
True

Record

Record is a data structure to hold fixed number of elements and it provides method to associate a name with particular element in tuple. It resembles structure in C. Record is not true data type, it is “tuple in disguise”(TM).
It’s syntax is:
-record(Name, {key1=Default1, key2, …}).

But in shell we can not use -record syntax and we do not yet know about modules where it can be defined, so we’ll use ‘rd’ shell command to define record:

1> rd(info, {name=”ruslan”, age=28, height, weight}).
info

Now let’s create instance of record:

2> X = #info{}.
#info{name = “ruslan”,age = 28,height = undefined,weight = undefined}
3> X.
#info{name = “ruslan”,age = 28,height = undefined,weight = undefined}

As you see height and weight got “undefined” value.

To extract fields of record we use pattern matching:

4> #info{name=Name, age=Age} = X.
#info{name = “ruslan”,age = 28,height = undefined,weight = undefined}
5> Name.
“ruslan”
6> Age.
28

We can also access field of record with “dot syntax”:

7> X#info.name.
“ruslan”

Erlang has more data types like Pid, Port identifier, Reference which will be described later in more advanced topics.There is no direct correspondence to Python’s built-in data types like dictionaries and sets, but Erlang has modules which provide the same semantics.

That’s it for today.

I assume you have already installed Erlang on your system and are able to run erlang shell either from command line or from within Emacs (C-c C-z).

This is a view of Eshell from my Emacs:

Erlang (BEAM) emulator version 5.5.2 [source] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.5.2  (abort with ^G)
1> 

Let’s do a simple thing and try to assign a value to a variable in the Eshell. First you should know that variables in Erlang start with uppercase letter or underscore (_), for example:

• X
• Name
• Address
• _
• _NoWarn

Ok, let’s finally assign some value to a variable X:

1> X = 4.
4
2>

So far, so good. Make sure to type final “.” at the end of expression when you are done entering code.

Let’s assign new value to X:

2> X = 5.

=ERROR REPORT==== 27-Aug-2007::00:23:02 ===
Error in process <0.29.0> with exit value: {{badmatch,5},[{erl_eval,expr,3}]}

** exited: {{badmatch,5},[{erl_eval,expr,3}]} **
3> 

Here you need to understand and remember couple of things:

1. Erlang uses single assignment, a variable can only be bound once, bar none.
2. In expression X = 5 operator = is not an assignment, but match operator and variables are bound to values using pattern matching mechanism.

I think it won’t be an exaggeration if I say that Pattern Matching permeates Erlang. To understand why we got ERROR REPORT in above example with {badmatch, 5} let’s dive into this pattern matching a bit.

When you use pattern matching’s = operator left side called pattern is matched against right side which is a term(piece of data of any Erlang’s data type: integer, float, list, tuple, etc). If your matching fails you get run-time error, if it succeeds then any unbound variable in lefthand pattern becomes bound.

Returning to our example - first we had an unbound variable:

1> X.
** 1: variable ‘X’ is unbound **
2> 

Then we bound value to variable X with pattern matching:

2> X = 4.
4
3> X.
4
4> 

Now as the variable X is bound we can’t change its value any more (remember single assignment?) otherwise we’ll get badmatch error like in foregoing X = 5 (4 does not match 5), but we may use = to match our variable:

4> X = 4.
4
5> 

Let’s add a bit of tuples to pattern matching. In Erlang tuple is defined inside {…}. ie:

5> {2, 3}.
{2,3}
6> 

and now pattern matching:

6> {X, Y} = {2, 3}.

=ERROR REPORT==== 27-Aug-2007::01:10:45 ===
Error in process <0.29.0> with exit value: {{badmatch,{2,3}},[{erl_eval,expr,3}]}

** exited: {{badmatch,{2,3}},[{erl_eval,expr,3}]} **
7> {X, Y} = {4, 3}.
{4,3}
8> X.
4
9> Y.
3
10> 

In first attempt we tried to match X with 2 and the matching failed as the value of X is 4, in a second attempt the matching succeeded and unbound variable Y also got its value (became bound).

This may look to you like tuple unpacking in Python:

>>> x, y = (4, 3)
>>> x, y
(4, 3)
>>> x, y = (5, 3)
>>> x, y
(5, 3)

but it’s only visual similarity, though i must admit, useful one.

That’s it for today, later you’ll see how pattern matching is uber-useful and how it is used in different parts of Erlang’s constructs.

Well it’s actually as simple as running M-x man RET module_name RET in minibuffer.

I’m using Erlang setup from rpm on FC7 and by default man pages are located under /usr/lib/erlang/man/ so to use above command in minibuffer you must make sure you have your erlang’s man path either in /etc/man.config or you’ve added it into MANPATH with something like export MANPATH=$MANPATH:/usr/lib/erlang/man in your .bash_profile in case your Erlang man pages are not in location accessible by default.

You may also pass man path in minibuffer manually without changing /etc/man.config or MANPATH. In my case to view man page for ‘lists’ module it will look like:

M-x man RET -M /usr/lib/erlang/man lists RET

I’ve customized some stuff for myself in emacs and made binding to F6 key so that whenever i set cursor on module name in my erlang buffer and press F6 i get man page in another window poped up describing module at point. So if you have in your code or in any buffer, for example:

(em@localhost)2> lists:reverse([1, 2, 3]).

you need to move cursor to lists and press F6. Quite handy if you consult man pages often, which is the case for me now as i learn Erlang.

Here is the corresponding elisp helper function and key binding from my dot emacs:

(defun get-erl-man ()
  (interactive)
  (let* ((man-path “/usr/lib/erlang/man”)
         (man-args (format “-M %s %s” man-path (current-word))))
    (man man-args)))

(global-set-key [(f6)] (lambda () (interactive) (get-erl-man)))

Recently I’ve begun to make blog posts and now want to have highlighting of Erlang’s code(actually any code , be it Python, Lisp, etc) in my posts. I’m using The One True Editor and it goes without saying that i want to convert my erlang code into html from within emacs to have corresponding syntax coloring. Htmlize package to the rescue!

After you downloaded package and put

(add-to-list 'load-path “path_to_your_htmlize.el”)
(require ‘htmlize)

into your dot emacs - you are ready to use it.

M-x htmlize-buffer or M-x htmlize-region will convert whole buffer or selected region with associated decorations into HTML( See C-h a htmlize RET for more functions). By default htmlize will make HTML output in css mode which is not very suitable for inserting into blog post as output includes also style sheets. Excerpt from htmlize documentation:

;; htmlize supports three types of HTML output, selected by setting
;; `htmlize-output-type‘: `css‘, `inline-css‘, and `font‘.  In `css‘
;; mode, htmlize uses cascading style sheets to specify colors; it
;; generates classes that correspond to Emacs faces and uses <span
;; class=FACE>…</span> to color parts of text.  In this mode, the
;; produced HTML is valid under the 4.01 strict DTD, as confirmed by
;; the W3C validator.  `inline-css‘ is like `css‘, except the CSS is
;; put directly in the STYLE attribute of the SPAN element, making it
;; possible to paste the generated HTML to other documents.  In `font‘
;; mode, htmlize uses <font color=”…”>…</font> to colorize HTML,
;; which is not standard-compliant, but works better in older
;; browsers.  `css‘ mode is the default.

inline-css is the type of output i want. This can be achieved by customizing htmlize-output-type variable with M-x customize htmlize RET or directly modifying dot emacs. Converting:

(add-to-list 'load-path “path_to_your_htmlize.el”)
(require ‘htmlize)

with htmlize-region and then applying nxml-mode to produced result gives:

<!DOCTYPE html PUBLIC “-//W3C//DTD HTML 4.01//EN“>
<!– Created by htmlize-1.34 in inline-css mode. –>
<html>
  <head>
    <title>.emacs</title>
  </head>
  <body style=“color: #ffffff; background-color: #000000;“>
    <pre>
(add-to-list ‘load-path <span style=“color: #ffa07a;“>“path_to_your_htmlize.el”</span>)
(<span style=“color: #00ffff;“>require</span> ‘<span style=“color: #7fffd4;“>htmlize</span>)
</pre>
  </body>
</html>

As you see I need to cut contents between <pre> </pre> including
<pre> tags itself to insert that then directly into blog post. After that i need manually copy/paste styles from <body> tag into <pre> tag and also add font-size: 8pt to meet my taste. Being lazy i’ve implemented function my-htmlize-region in elisp to make that job for me every time i press F5 key:

(defun my-htmlize-region (beg end)
  “Htmlize region and put into <pre> tag style that is left in <body> tag
plus add font-size: 8pt”
  (interactive “r”)
  (let* ((buffer-faces (htmlize-faces-in-buffer))
         (face-map (htmlize-make-face-map (adjoin ‘default buffer-faces)))
         (pre-tag (format
                   “<pre style=\”%s font-size: 8pt\”>”
                   (mapconcat #’identity (htmlize-css-specs
                                          (gethash ‘default face-map)) ” “)))
         (htmlized-reg (htmlize-region-for-paste beg end)))
    (switch-to-buffer-other-window “*htmlized output*”)
    ; clear buffer
    (kill-region (point-min) (point-max))
    ; set mode to have syntax highlighting
    (nxml-mode)
    (save-excursion
      (insert htmlized-reg))
    (while (re-search-forward “<pre>” nil t)
      (replace-match pre-tag nil nil))
    (goto-char (point-min))))

(global-set-key [(f5)] (lambda (beg end)
                         (interactive “r”) (my-htmlize-region beg end)))

So now selecting:

(add-to-list 'load-path “path_to_your_htmlize.el”)
(require ‘htmlize)

and pressing F5 i get this in another buffer:

<pre style=“color: #ffffff; background-color: #000000; font-size: 8pt“>
(add-to-list ‘load-path <span style=“color: #ffa07a;“>“path_to_your_htmlize.el”</span>)
(<span style=“color: #00ffff;“>require</span> ‘<span style=“color: #7fffd4;“>htmlize</span>)
</pre>

As you see it’s just what i want:
<pre> tags with content and <pre> tag contains style from above mentioned <body> tag plus font-size is added too.

Factorial in Erlang with syntax coloring as i have it in my Emacs:

-module(factorial).
-export([factorial/1, factorial_rec/1]).

%% tail recursion
factorial(Num) ->
    factorial(Num, 1).

factorial(1, Acc) -> Acc;
factorial(Num, Acc) ->
    factorial(Num-1, Num * Acc).

%% recursion
factorial_rec(1) -> 1;
factorial_rec(Num) ->
    Num * factorial_rec(Num-1).

This is a joy of using Emacs.

In my previous post My Erlang binary search I’ve implemented binary search in Python and Erlang as small exercise for myself after reading Half-baked Ideas blog post. Good article pointing to specifics of implementation of that algorithm in Erlang was posted on Erlane’s blog which is in a nutshell: binary search in Erlang implemented on list data structure is less efficient than linear search.

So to grasp why linear search which is O(N) is faster in Erlang then binary search which is in theory O(logN) go and read that article.
In Python list data structure (I’m talking here about CPython) is implemented as mutable and extensible vector of references to objects(we might say array of pointers), here is the excerpt from listobject.h:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for ‘allocated’ elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

So Python version works as expected regarding efficiency. While my goal of implementing binary search algorithm in Erlang was learning Erlang and not particulary developing optimized version of that algorithm or using another one it’s always good to pick new tricks of the trade along the way and for me the issue with my implementation of binary search in Erlang just boils down to: your experience and know your tools (language, os, editor(emacs :), etc )

As Aldous Huxly said: “Experience is not what happens to you; it’s what you do with what happens to you.”. So make errors (not many :) in your programs, fix them and gain new experience with your new language.

Another post by Erlane team is good reading describing paradigm shifts when you are newbie and are on your own way to Erlang/OTP wizardry.

I was lurking and watching Erlang quite some time during this year and finally decided give it a shot after Programming Erlang was released. I ordered book in pdf format to rest assured i’ll get it in fastest possible way. After i read book a bit i was hooked

Today i came across binary search in Erlang blog post and decided to implement quickly binary search myself. My first attempt was to do it in python as it’s my daily job’s programming language and it turned this way (no check for edge cases like empty sequence):

def binsearch(seq, key, start, end):
    if end < start:
        return -1
    mid = (start + end) / 2
    if key == seq[mid]:
        return mid
    if key < seq[mid]:
        return binsearch(seq, key, start, mid-1)
    if key > seq[mid]:
        return binsearch(seq, key, start+1, end)

After i looked at code a bit i was surprised i wrote it recursively, earlier i would do it like:

def binsearch(seq, key):
    start = 0
    end = len(seq) - 1

    while True:
        if end < start:
            return -1
        mid = (start + end) / 2
        if key == seq[mid]:
            return mid
        if key < seq[mid]:
            end = mid - 1
        else:
            start = mid + 1

Erlang obviously bends my mind :)

And my version in Erlang which was just exercise for myself and mainly looks like in original blog post:

-module(search).
-export([binsearch/2]).
-import(lists, [nth/2]).
-include_lib(“eunit/include/eunit.hrl”).

binsearch(List, Key) ->
    binsearch(List, Key, 1, length(List)).

binsearch(List, Key, LowerBound, UpperBound) ->
    if
        UpperBound < LowerBound -> -1;
        true ->
            Mid = (LowerBound + UpperBound) div 2,
            Item = nth(Mid, List),
            if
                Key < Item ->
                    binsearch(List, Key, LowerBound, Mid-1);
                Key > Item ->
                    binsearch(List, Key, Mid+1, UpperBound);
                true ->
                    Mid
            end
    end.

setup_test_() ->
    {setup,
     fun() -> [7, 11, 14, 40, 50] end,
     fun(L) ->
             [?_assertMatch(3, binsearch(L, 14)),
              ?_assertMatch(-1, binsearch(L, 70))]
     end
    }.

Running unit tests:

(em@localhost)1> search:test().
  All 2 tests successful.
ok