Erlang: Functions (Part 4).
As we have seen in the previous articles, functions elevate some tiny little things to the new heights. I find it really cool you could create something new in terms of existing things just by combining them in the right way (composition). Functions also allow you to manipulate complex objects if you guarantee you could break them to smaller pieces (recursion). Combined together these two principles create a universe of beautiful solutions. In this article we're going to explore some new forms of composition and recursion.
Sometimes recursion could lead you to unexpected results. We once created a hyper operator by just utilizing the successor and predecessor functions. The predecessor function (just to remind you) is a function that decrements its only parameter by one. If we start applying the predecessor function to any positive integer over and over we would eventually reach zero (which is an even number as you might know). Thinking this way we could try and implement two functions that test positive integers for being even or odd numbers.
-module(lesson4).
-export([is_even/1, is_odd/1]).
is_even(0) -> true;
is_even(N) -> is_odd(N - 1).
is_odd(0) -> false;
is_odd(N) -> is_even(N - 1).
Here we introduce a few new concepts. First of all, functions that return a boolean value are called predicates (yet this is not a complete definition and the term itself has different interpretations, if you need more information please start here). So, is_even and is_odd are both unary predicates. It's also very common to utilize the is prefix for unary predicates when naming your functions.
Secondly, an interesting fact here is that both predicates have mutual base cases. If we're calling is_even and the number is zero, then the answer is true, because zero is even. Otherwise, we're decrementing the argument by 1 and giving the control to the is_odd function. If at this point the argument is zero then the result is false, otherwise the argument is decremented again and is_even is called. And so on and so forth until it reaches zero and stops the recursion.
Functions with mutual base cases represent so called mutual recursion. While in everyday programming you will face such recursion rarely it might be common in such tasks as writing parsers and producing some sequences for analytical purposes.
You might be also wondering why implement such simple thing that way while there are generic and performant alternatives. Let me illustrate them.
is_even2(N) -> N rem 2 =:= 0.
is_even3(N) -> 1 band N =:= 0.
I'm omitting is_odd here; those are just to illustrate the idea after all. You could see that the same function could be implemented in many different ways and it's your responsibility to utilize the version that suits your needs best. However while working with negative integers both the above functions require you to have either rem (integer remainder) or band (bitwise and) operator to be supported.
On the other hand our initial version of the is_even and is_odd functions requires nothing but the predecessor function, which could be easily replaced by an analogue operation over some other non-integer structure (for instance, tuples). This might be confusing for now but this topic will be explained in detail as soon as we discuss functions and their relation to types.
Now, let's see how we could filter out a list of integers so that if you provide a lists of integers it would return you either a list of odd or even numbers depending on which version you're using.
filter_even([]) -> [];
filter_even([H|T]) ->
case is_even(H) of
true -> [H|filter_even(T)];
false -> filter_even(T)
end.
filter_odd([]) -> [];
filter_odd([H|T]) ->
case is_odd(H) of
true -> [H|filter_odd(T)];
false -> filter_odd(T)
end.
You might notice these functions are almost identical. The only difference is the exact function we call to test a single number. If only we had a mechanism to generalize such cases...
Erlang is a functional language. Among other properties Erlang treats functions as first-class citizens. It means we could assign functions to variables, test them for equality, consider functions as arguments of other functions and also return them as a result of evaluation of other functions. In other words functions in Erlang are in fact like all other types we use regularly.
To refer to a function we use the keyword fun followed by either the function's name or a combination of module and function depending on where we refer it from and the function's arity. For instance, if we refer to the is_even function from where it's defined (lesson4), we could just use the short form which is fun is_even/1.
The syntax could be generalized as fun M:F/A, where MFA stands for module, function and arity. You should also keep in mind that any component could be either constant or variable.
1> IsOdd = fun lesson4:is_odd/1.
fun lesson4:is_odd/1
2> IsOdd(42).
false
3> M = lesson4.
lesson4
4> F = is_even.
is_even
5> A = 1.
1
6> IsEven = fun M:F/A.
fun lesson4:is_even/1
7> IsEven(3).
false
8> fun lesson4:is_even/1(0).
true
It's not always necessary to assign a reference to a variable to call it. Instead you could just call it right away by providing its arguments, as you could see in the very last example (step 8). You could also wrap a reference in parentheses before calling it which is a common way to do it. Here is an example.
1> (fun lesson4:is_even/1)(6).
true
The fact we could associate any function with a variable and then call it means we could now implement a generic version of the filter function. Let's do this.
filter(_, []) -> [];
filter(P, [H|T]) ->
case P(H) of
true -> [H|filter(P, T)];
false -> filter(P, T)
end.
Filter is a higher-order function. Higher-order functions (unlike first-order functions) take other functions as arguments or return other functions as a result, elevating our ability to abstract things to a new level.
To call the filter function you should provide a reference to some unary predicate. Let's illustrate it by simplifying the filter_even and filter_odd functions.
filter_even_simple(L) -> filter(fun is_even/1, L).
filter_odd_simple(L) -> filter(fun is_odd/1, L).
One important thing I have to mention is that our generic filter function is already implemented as a part of the lists module. While it's fun to write our own versions of generic and fundamental functions (not just fun but also really useful for educational purposes) it's always a good idea to utilize Erlang's built-in functions (BIFs) when possible due to performance reasons. It's also a good practice to utilize the Standard Library even if you know some functions aren't BIFs because these modules and functions are well tested and documented.
Now let's get back to the predicates. It's sometimes useful to check whether at least one element in the list satisfies some condition or conditions. This task could be generalized as a higher-order function which is a predicate itself called any. This function takes a predicate P (that's intended to test a single element in the list) and the list itself and returns true if at least one element of the list satisfies the predicate. Otherwise it returns false.
any(_, []) -> false;
any(P, [H|T]) -> P(H) orelse any(P, T).
Oh boy, I do love this function! It's quite unique among all the previous functions we have seen so far because it has two base cases one of which is at the same clause that forms the recursion. I mean, look at the second clause, you could see here is the orelse operator! It does work in that way so we call any (which is the second operand) if only the first operand is false. Hence, P(H) is a base case! Let's do some tests first to get a better understanding.
1> false orelse 1.
1
2> true orelse 1.
true
3> true andalso 1.
1
4> false andalso 1.
false
5> 2 < 1 andalso io:fwrite("you won't see this~n").
false
The andalso and orelse operators represent so called Short-Circuit Evaluation, means their second operand won't be evaluated at all if not needed. In the very last example you could see the io:fwrite function is not evaluated because 2 is more than 1 hence the equation is false already and there is no need to evaluate it further.
You could also notice that unlike in and and or the second operand could be evaluated to anything, not just some boolean value. And one last note is that you could use andalso and orelse in guards (we will discuss it one day if there is a luck).
Any has its dual called all. The all function is almost the same but it does return true if all elements in the list satisfy the given predicate.
all(_, []) -> true;
all(P, [H|T]) -> P(H) andalso all(P, T).
As I said both functions are almost the same but you could notice the first clauses return different boolean values. That's because in the case of all if all elements satisfy the given predicate then the recursion terminates when calling the all function against an empty list so that it must return true, otherwise it would produce incorrect results. In the case of any if all elements do not satisfy the given predicate then the very last call would be made against an empty list, hence the result should be false (there are no elements that satisfy P).
Now let me introduce the zip function. This function takes 2 lists and combines them into a single list so that each element of each source list would be combined into a binary tuple. Let me show you how it works.
1> lists:zip([1, 2, 3], [a, b, c]).
[{1,a},{2,b},{3,c}]
Cool, huh? Well, one thing though... I did mention you should always be using the Standard Library whenever possible. But for some weird reason the zip function that's provided by the lists module does only work when there are 2 lists of same size. Giving it lists of different sizes would simply produce an error. So we're going to implement our own version!
% differs from lists:zip!
zip([HX|TX], [HY|TY]) -> [{HX, HY}|zip(TX, TY)];
zip(_, _) -> [].
Let's now try it in erl.
1> lesson4:zip([1, 2, 3], [a, b, c, d]).
[{1,a},{2,b},{3,c}]
Splendid! Now, let me show you something. Consider we have a list of integers. If we try to combine it with its own tail (the list itself minus the head element) we would get each element paired with the element next to it. Let's see.
1> Numbers = [1, 2, 3, 4, 5].
[1,2,3,4,5]
2> lesson4:zip(Numbers, tl(Numbers)).
[{1,2},{2,3},{3,4},{4,5}]
We could now use this property to define a predicate that checks whether a list is sorted or not.
gte({X, Y}) -> X =< Y.
lte({X, Y}) -> X >= Y.
is_sorted([]) -> true;
is_sorted([_|T] = L) ->
Pairs = zip(L, T),
all(fun gte/1, Pairs) orelse
all(fun lte/1, Pairs).
I suppose the gte and lte functions are simple and straightforward. The is_sorted predicate needs some little clarification though. If you take a look in the line number 7 we define a variable called Pairs. That's because the result of calling the zip function is going to be used twice in the worst scenario (when the first all evaluates to false). So, involving a variable here is quite reasonable as we're getting rid of unnecessary computations making the function more efficient. Though, involving variables in functions is an advanced topic (surprise!) as it requires you to understand scoping. I do recommend you to avoid variables in functions during learning Erlang. This would force you to keep your functions short and simple and as a result teaches you good practices. Scoping rules will be discussed in one of the upcoming articles.
Let's see how is_sorted works.
1> lesson4:is_sorted([1, 2, 3, 4, 5, 6]).
true
2> lesson4:is_sorted([1, 2, 3, 5, 4, 6]).
false
3> lesson4:is_sorted([6, 5, 4, 3, 2, 1]).
true
You could see that our predicate does work correctly for both ascending and descending orders, that's why we needed to involve 2 calls of the all function.
That's it for now. Play with the functions from this article, write your own ones and read more about higher-order functions using the links you could find here or over the Internet. In the next article (articles?) I'm going to introduce you Funs and explain why these tiny little things are really a new level to abstract things. Stay tuned!
P.S.: Don't forget to inspect and download the sources.
August 08, 2020