I am a programmer and architect (the kind that writes code) with a focus on testing and open source; I maintain the PHPUnit_Selenium project. I believe programming is one of the hardest and most beautiful jobs in the world. Giorgio is a DZone MVB and is not an employee of DZone and has posted 638 posts at DZone. You can read more from them at their website. View Full User Profile

Erlang: functions (part 1)

09.26.2012
| 2651 views |
  • submit to reddit

Everyone knows how to write a function that calculates the factorial of a number, since is one of the basic examples of recursion usage.

Erlang is no different from other programming languages in its recursion support, but its pattern matching capabilities provide a shortcut for listing the base case of the recursion along with the generic one:

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

Here is a little test for this function:

simple_test() ->
    ?assertEqual(6, recursive_factorial(3)),
    ?assertEqual(2, recursive_factorial(2)),
    ?assertEqual(1, recursive_factorial(1)),
    ?assertEqual(1, recursive_factorial(1)).

As in all function definitions, clauses and their bodies are separated by semicolons; statements belonging to the same function are instead separated by commas. The last statement of each function is returned.

Clauses are matched in the order they are defined, so the base case where the argument is equal to 0 will stop the recursion for this function; it's no different than an if() containing an early return. However, not only in the long run you would get tired of writing this kind of conditionals, but pattern matching is also more powerful and concise:

print_name({person, Name, _Surname}) -> io:format("~s~n", Name).

In this function definition, we are extracting the second element of a tuple of cardinality 3, but only if its first element is the atom person. The second element is bound to the variable Name, while we signal that we want to ignore the third one by prefixing the variable name Surname with _ (we could also just write _).

When matching isn't enough, we have also the possibility of adding guard clauses. Reimplementing factorial in this way:

guard_factorial(N) when N < 2 -> 1;
guard_factorial(N) -> guard_factorial(N - 1) * N.

lets us specify clauses programmatically, instead of relying on the structure of the arguments.

We can do the same job inside Erlang code, if we don't want to extract it into a separate function:

case_factorial(N) ->
    case N of
        0 -> 1;
        _ -> case_factorial(N - 1) * N
    end.


The end is part of the case statement, while the dot marks the end of the function. Note that _ is Erlang placeholder for anything and will in fact always match any value.

Anonymous functions

In every functional language, you can define anonymous functions, that can be stored in variables and passed to other functions (that are said to be of an higher-order, recalling the mathematical concept of higher-order logic.)

In Erlang, it's easy to define such a function:

Function = fun(Argument) -> dosomething() end.

This time the end is part of the function definition.

These functions can be called directly in many cases:

Function(ActualArgument).

Or with apply/2:

apply(Function, [ActualArgument]).

The second argument of apply/2 is always a list. There is also an apply/3 version, where the first two arguments are atoms describing the module and the function name:

    ?assertEqual(6, apply(factorial_04, guard_factorial, [3])),

What about recursion in anonymous functions?

This where it gets complicated. When implementing recursion with named functions, you can refer to the function by name to call it inside itself. Take a look again at our recursive_factorial/1:

But when the function is defined anonymously, it can't refer to itself that easily. To recur on itself, a function must be passed to itself as an argument:

    Factorial = fun(N, F) ->
        case N of
            0 -> 1;
            _ -> apply(F, [N-1, F]) * N
        end
    end,
    ?assertEqual(6, apply(Factorial, [3, Factorial])),

It turns out this pattern is common, and can be generalized to applied to any function with the famous Y combinator.

The Y combinator is an higher-order function that takes a function F as input. This function is designed in such a way to have two curried arguments:

    FactorialY =
        fun(F) ->
            fun (N) ->
                case N of
                    0 -> 1;
                    _ -> F(N-1) * N
                end
            end
        end,
    ?assertEqual(6, apply(y(FactorialY), [3])).

What comes out of the Y combinator is just a fun(N). If you're curious, here's the combinator defined in Erlang:

y(M) ->
    G = fun (F) ->
        M(fun(A) -> (F(F))(A) end)
    end,
    G(G).

but just as you, I'm still trying to wrap my head around it. :) This is probably a sign of why object-oriented programming is more diffused than functional programming: it's a bit more closer to the way ordinary people think, while functional programming is closer to the mathematical and theoretical aspects of computer science. And theory isn't the simplest thing to grasp...

Conclusion

We have no space (and air) left, so we will talk about tail recursion in the next article. We will also expand a bit the discussion of anonymous functions and of their usefulness. Remember that all the code discussed in this article is available on the Github repository of this series.

Published at DZone with permission of Giorgio Sironi, author and DZone MVB.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Tags: