Fibonacci in Erlang

We’ve seen the fibonacci example in multiple languages, but none of them purely functional. Erlang is a functional language that is growing in popularity due to the ease in which you can create concurrent programs. It has a number of paradigms that may be foreign to developers that are used to working in scripting or object oriented languages, but rather than a hindrance, things like immutable variables and the lack of loop constructs encourage an elegance in implementation that becomes second nature once you change your mindset.

In this example, we’re using three of these features together to create a very simple version of our fibonacci function.

  • Multiple function clauses – In erlang, you can define a function multiple times – and depending on the arguments passed to the function the correct version of that function is executed.
  • Pattern matching – To determine which function clause is executed, variables declared in the head can be matched against a pattern. In this example, we’re using the same variable name in the first clause for the third and fourth variables. Because variables are immutable, they can only ever equal one value when they are set. That means that when we are looking for “Count” twice in the function head – we are really looking for those variables to contain the same value.
  • Tail recursion – Instead of for or while loops, erlang uses a mechanism called tail recursion. By calling itself multiple times with incremented values, our fibonacci function is in effect executing a loop; and because we have multiple function clauses, we can end the loop when a certain condition is met.
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -smp enable -sname fibonacci debug verbose

%% I've written this as an escript rather than something that we need to compile
%% This means it will compile on the fly and execute the function named main
main([]) ->
        %% Getting the input here is simple a single call to an io function
        Num = io:get_line("\nHow many numbers of the sequence would you like?\n"),
        %% Erlang does have types - we need to remove the newline and convert the
        %% input to an integer here before passing it to the fibonacci function
        fibonacci(0, 1, list_to_integer(string:strip(Num, both, $\n)), 0);
main([Num]) ->
        fibonacci(0, 1, list_to_integer(string:strip(Num, both, $\n)), 0).

%% Here we see the elegance of erlang's tail recursion and multiple function
%% definitions. Rather than changing variables (which we can't do anyway - 
%% they are immutable!), we call the function again with new values. When
%% the end is reached ( Num == Count ), we exit with ok. Notice that the end
%% clause is first so it is exectued when the 3rd and 4th arguments match.
fibonacci( _, _, Count, Count ) ->
fibonacci( A, B, Num, Count ) ->
        io:format("~w~n", [A]),
        fibonacci( B, A + B, Num, Count + 1).

HTML code generated by vim-color-improved v.0.4.0.Download this code: fibonacci.erl

Leave a Reply