2 Programming with Funs
This section introduces functional objects (Funs), which are a new data type introduced in Erlang 4.4. Functions which takes Funs as arguments, or which return Funs are called higher order functions.
- Funs can be passed as arguments to other functions, just like lists or tuples
- functions can be written which return Funs, just like any other data object.
2.1 Higher Order Functions
Funs encourages us to encapsulate common patterns of design into functional forms called higher order functions. These functions not only shortens programs, but also produce clearer programs because the intended meaning of the program is explicitly rather than implicitly stated.
The concepts of higher order functions and procedural abstraction are introduced with two brief examples.
2.1.1 Example 1 - map
If we want to double every element in a list, we could write a function named
double
:double([H|T]) -> [2*H|double(T)]; double([]) -> []This function obviously doubles the argument entered as input as follows:
> double([1,2,3,4]). [2,4,6,8]We now add the function
add_one
, which adds one to every element in a list:add_one([H|T]) -> [H+1|add_one(T)]; add_one([]) -> [].These functions,
double
andadd_one
, have a very similar structure. We can exploit this fact and write a functionmap
which expresses this similarity:map(F, [H|T]) -> [F(H)|map(F, T)]; map(F, []) -> [].We can now express the functions
double
andadd_one
in terms ofmap
as follows:double(L) -> map(fun(X) -> 2*X end, L). add_one(L) -> map(fun(X) -> 1 + X end, L).
map(F, List)
is a function which takes a functionF
and a listL
as arguments and returns the new list which is obtained by applyingF
to each of the elements inL
.The process of abstracting out the common features of a number of different programs is called procedural abstraction. Procedural abstraction can be used in order to write several different functions which have a similar structure, but differ only in some minor detail. This is done as follows:
- write one function which represents the common features of these functions
- parameterize the difference in terms of functions which are passed as arguments to the common function.
2.1.2 Example 2 - foreach
This example illustrates procedural abstraction. Initially, we show the following two examples written as conventional functions:
- all elements of a list are printed onto a stream
- a message is broadcast to a list of processes.
print_list(Stream, [H|T]) -> io:format(Stream, "~p~n", [H]), print_list(Stream, T); print_on_list(Stream, []) -> true.broadcast(Msg, [Pid|Pids]) -> Pid ! Msg, broadcast(Msg, Pids); broadcast(_, []) -> true.Both these functions have a very similar structure. They both iterate over a list doing something to each element in the list. The "something" has to be carried round as an extra argument to the function which does this.
The function
foreach
expresses this similarity:foreach(F, [H|T]) -> F(H), foreach(F, T); foreach(F, []) -> ok.Using
foreach
,print_on_list
becomes:foreach(fun(H) -> io:format(S, "~p~n~,[H]) end, L)
broadcast
becomes:foreach(fun(Pid) -> Pid ! M end, L)
foreach
is evaluated for its side-effect and not its value.foreach(Fun ,L)
callsFun(X)
for each elementX
inL
and the processing occurs in the order in which the elements were defined inL
.map
does not define the order in which its elements are processed.2.2 Advantages of Higher Order Functions
Programming with higher order functions, such as
map
andforeach
, has a number of advantages:
- It is much easier to understand the program and the intention of the programmer is clearly expressed in the code. The statement
foreach(fun(X) ->
clearly indicates that the intention of this program is to do something to each element in the listL
. We also know that the function which is passed as the first argument offoreach
takes one argumentX
, which will be successively bound to each of the elements inL
.
- Functions which take Funs as arguments are much easier to re-use than other functions.
2.3 The Syntax of Funs
Funs are written with the syntax:
F = fun (Arg1, Arg2, ... ArgN) -> ... endThis creates an anonymous function of
N
arguments and binds it to the variableF
.If we have already written a function in the same module and wish to pass this function as an argument, we can use the following syntax:
F = fun FunctionName/ArityWith this form of function reference, the function which is referred to does not need to be exported from the module.
We can also refer to a function defined in a different module with the following syntax:
F = {Module, FunctionName}In this case, the function must be exported from the module in question.
The follow program illustrates the different ways of creating Funs:
-module(fun_test). -export([t1/0, t2/0, t3/0, t4/0, double/1]). -import(lists, [map/2]). t1() -> map(fun(X) -> 2 * X end, [1,2,3,4,5]). t2() -> map(fun double/1, [1,2,3,4,5]). t3() -> map({?MODULE, double}, [1,2,3,4,5]). double(X) -> X * 2.We can evaluate the fun
F
with the syntax:F(Arg1, Arg2, ..., Argn)To check whether a term is a Fun, use the test
function/1
in a guard. Example:f(F, Args) when function(F) -> apply(F, Args); f(N, _) when integer(N) -> N.Note that Funs are currently represented internally using tuples, and therefore any code that needs to handle both tuples and Funs must use the
function/1
test before using thetuple/1
test.2.4 Variable Bindings within a Fun
The scope rules for variables which occur in Funs are as follows:
- All variables which occur in the head of a Fun are assumed to be "fresh" variables.
- Variables which are defined before the Fun, and which occur in function calls or guard tests within the Fun, have the values they had outside the Fun.
- No variables may be exported from a Fun.
The following examples illustrate these rules:
print_list(File, List) -> {ok, Stream} = file:open(File, write), foreach(fun(X) -> io:format(Stream,"~p~n",[X]) end, List), file:close(Stream).In the above example, the variable
X
which is defined in the head of the Fun is a new variable. The value of the variableStream
which is used within within the Fun gets its value from thefile:open
line.Since any variable which occurs in the head of a Fun is considered a new variable it would be equally valid to write:
print_list(File, List) -> {ok, Stream} = file:open(File, write), foreach(fun(File) -> io:format(Stream,"~p~n",[File]) end, List), file:close(Stream).In this example,
File
is used as the new variable instead ofX
. This is rather silly since code in the body of the Fun cannot refer to the variableFile
which is defined outside the Fun. Compiling this example will yield the diagnostic:./FileName.erl:Line: Warning: variable 'File' shadowed in 'lambda head'This reminds us that the variable
File
which is defined inside the Fun collides with the variableFile
which is defined outside the Fun.The rules for importing variables into a Fun has the consequence that certain pattern matching operations have to be moved into guard expressions and cannot be written in the head of the Fun. For example, we might write the following code if we intend the first clause of
F
to be evaluated when the value of its argument isY
:f(...) -> Y = ... map(fun(X) when X == Y -> ; (_) -> ... end, ...) ...instead of
f(...) -> Y = ... map(fun(Y) -> ; (_) -> ... end, ...) ...2.5 Funs and the Module lists
The following examples show a dialogue with the Erlang shell. All the higher order functions discussed are exported from the module
lists
.2.5.1 map
map(F, [H|T]) -> [F(H)|map(F, T)]; map(F, []) -> [].
map
takes a function of one argument and a list of terms. It returns the list obtained by applying the function to every argument in the list.1> Double = fun(X) -> 2 * X end. #Fun<erl_eval> 2> lists:map(Double, [1,2,3,4,5]). [2,4,6,8,10]When a new Fun is defined in the shell, the value of the Fun is printed as
Fun#<erl_eval>
2.5.2 any
any(Pred, [H|T]) -> case Pred(H) of true -> true; false -> any(Pred, T) end; any(Pred, []) -> false.
any
takes a predicateP
of one argument and a list of terms. A predicate is a function which returnstrue
orfalse
.any
is true if there is a termX
in the list such thatP(X)
istrue
.We define a predicate
Big(X)
which istrue
if its argument is greater that 10.3> Big = fun(X) -> if X > 10 -> true; true -> false end end. #Fun<erl_eval> 4> lists:any(Big, [1,2,3,4]). false. 5> lists:any(Big, [1,2,3,12,5]). true.2.5.3 all
all(Pred, [H|T]) -> case Pred(H) of true -> all(Pred, T); false -> false end; all(Pred, []) -> true.
all
has the same arguments asany
. It is true if the predicate applied to all elements in the list is true.6> lists:all(Big, [1,2,3,4,12,6]). false 7> lists:all(Big, [12,13,14,15]). true2.5.4 foreach
foreach(F, [H|T]) -> F(H), foreach(F, T); foreach(F, []) -> ok.
foreach
takes a function of one argument and a list of terms. The function is applied to each argument in the list.foreach
returnsok
. It is used for its side-effect only.8> lists:foreach(fun(X) -> io:format("~w~n",[X]) end, [1,2,3,4]). 1 2 3 4 true2.5.5 foldl
foldl(F, Accu, [Hd|Tail]) -> foldl(F, F(Hd, Accu), Tail); foldl(F, Accu, []) -> Accu.
foldl
takes a function of two arguments, an accumulator and a list. The function is called with two arguments. The first argument is the successive elements in the list, the second argument is the accumulator. The function must return a new accumulator which is used the next time the function is called.If we have a list of lists
L = ["I","like","Erlang"]
, then we can sum the lengths of all the strings inL
as follows:9> L = ["I","like","Erlang"]. ["I","like","Erlang"] 10> lists:foldl(fun(X, Sum) -> length(X) + Sum end, 0, L). 11
foldl
works like awhile
loop in an imperative language:L = ["I","like","Erlang"], Sum = 0, while( L != []){ Sum += length(head(L)), L = tail(L) end2.5.6 mapfoldl
mapfoldl(F, Accu0, [Hd|Tail]) -> {R,Accu1} = F(Hd, Accu0), {Rs,Accu2} = mapfoldl(F, Accu1, Tail), {[R|Rs], Accu2}; mapfoldl(F, Accu, []) -> {[], Accu}.
mapfoldl
simultaneously maps and folds over a list. The following example shows how to change all letters inL
to upper case and count them.First upcase:
11> Upcase = fun(X) when $a =< X, X =< $z -> X + $A - $a; (X) -> X end. #Fun<erl_eval> 12> Upcase_word = fun(X) -> lists:map(Upcase, X) end. #Fun<erl_eval> 13> Upcase_word("Erlang"). "ERLANG" 14> lists:map(Upcase_word, L). ["I","LIKE","ERLANG"]Now we can do the fold and the map at the same time:
14> lists:mapfoldl(fun(Word, Sum) -> 14> {Upcase_word(Word), Sum + length(Word)} 14> end, 0, L). {["I","LIKE","ERLANG"],11}2.5.7 filter
filter(F, [H|T]) -> case F(H) of true -> [H|filter(F, T)]; false -> filter(F, T) end; filter(F, []) -> [].
filter
takes a predicate of one argument and a list and returns all element in the list which satisfy the predicate.15> lists:filter(Big, [500,12,2,45,6,7]). [500,12,45]When we combine maps and filters we can write very succinct and obviously correct code. For example, suppose we want to define a set difference function. We want to define
diff(L1, L2)
to be the difference between the listsL1
andL2
. This is the list of all elements in L1 which are not contained in L2. This code can be written as follows:diff(L1, L2) -> filter(fun(X) -> not member(X, L2) end, L1).The AND intersection of the list
L1
andL2
is also easily defined:intersection(L1,L2) -> filter(fun(X) -> member(X,L1) end, L2).2.5.8 takewhile
takewhile(Pred, [H|T]) -> case Pred(H) of true -> [H|takewhile(Pred, T)]; false -> [] end; takewhile(Pred, []) -> [].
takewhile(P, L)
takes elementsX
from a listL
as long as the predicateP(X)
is true.16> lists:takewhile(Big, [200,500,45,5,3,45,6]). [200,500,45]2.5.9 dropwhile
dropwhile(Pred, [H|T]) -> case Pred(H) of true -> dropwhile(Pred, T); false -> [H|T] end; dropwhile(Pred, []) -> [].
dropwhile
is the complement oftakewhile
.17> lists:dropwhile(Big, [200,500,45,5,3,45,6]). [5,3,45,6]2.5.10 splitlist
splitlist(Pred, L) -> splitlist(Pred, L, []). splitlist(Pred, [H|T], L) -> case Pred(H) of true -> splitlist(Pred, T, [H|L]); false -> {reverse(L), [H|T]} end; splitlist(Pred, [], L) -> {reverse(L), []}.
splitlist(P, L)
splits the listL
into the two sub-lists{L1, L2}
, whereL = takewhile(P, L)
andL2 = dropwhile(P, L)
.18> lists:splitlist(Big, [200,500,45,5,3,45,6]). {[200,500,45],[5,3,45,6]}2.5.11 first
first(Pred, [H|T]) -> case Pred(H) of true -> {true, H}; false -> first(Pred, T) end; first(Pred, []) -> false.
first
returns{true, R}
, whereR
is the first element in a list satisfying a predicate orfalse
:19> lists:first(Big, [1,2,45,6,123]). {true,45} 20> lists:first(Big, [1,2,4,5]). false2.6 Funs which Return Funs
So far, this section has only described functions which take Funs as arguments. It is also possible to write more powerful functions which themselves return Funs. The following examples illustrate these type of functions.
2.6.1 Simple Higher Order Functions
Adder(X)
is a function which, givenX
, returns a new functionG
such thatG(K)
returnsK + X
.21> Adder = fun(X) -> fun(Y) -> X + Y end end. #Fun<erl_eval> 22> Add6 = Adder(6). #Fun<erl_eval> 23> Add6(10). 162.6.2 Infinite Lists
The idea is to write something like:
-module(lazy). -export([ints_from/1]). ints_from(N) -> fun() -> [N|ints_from(N+1)] end.Then we can proceed as follows:
24> XX = lazy:ints_from(1). #Fun<lazy> 25> XX(). [1|#Fun<lazy>] 26> hd(XX()). 1 27> Y = tl(XX()). #Fun<lazy> 28> hd(Y()). 2etc. - this is an example of "lazy embedding"
2.6.3 Parsing
The following examples show parsers of the following type:
Parser(Toks) -> {ok, Tree, Toks1} | fail
Toks
is the list of tokens to be parsed. A successful parse returns{ok, Tree, Toks1}
, whereTree
is a parse tree andToks1
is a tail ofTree
which contains symbols encountered after the structure which was correctly parsed. Otherwisefail
is returned.The example which follows illustrates a simple, functional parser which parses the grammar:
(a | b) & (c | d)The following code defines a function
pconst(X)
in the modulefunparse
, which returns a Fun which parses a list of tokens.pconst(X) -> fun (T) -> case T of [X|T1] -> {ok, {const, X}, T1}; _ -> fail end end.This function can be used as follows:
29> P1 = funparse:pconst(a). #Fun<hof> 30> P1([a,b,c]). {ok,{const,a},[b,c]} 31> P1([x,y,z]). failNext, we define the two higher order functions
pand
andpor
which combine primitive parsers to produce more complex parsers. Firstlypand
:pand(P1, P2) -> fun (T) -> case P1(T) of {ok, R1, T1} -> case P2(T1) of {ok, R2, T2} -> {ok, {'and', R1, R2}}; fail -> fail end; fail -> fail end end.Given a parser
P1
for grammarG1
, and a parserP2
for grammarG2
,pand(P1, P2)
returns a parser for the grammar which consists of sequences of tokens which satisfyG1
followed by sequences of tokens which satisfyG2
.
por(P1, P2)
returns a parser for the language described by the grammarG1
orG2
.por(P1, P2) -> fun (T) -> case P1(T) of {ok, R, T1} -> {ok, {'or',1,R}, T1}; fail -> case P2(T) of {ok, R1, T1} -> {ok, {'or',2,R1}, T1}; fail -> fail end end end.The original problem was to parse the grammar
(a | b) & (c | d)
. The following code addresses this problem:grammar() -> pand( por(pconst(a), pconst(b)), por(pconst(c), pconst(d))).The following code adds a parser interface to the grammar:
parse(List) -> (grammar())(List).We can test this parser as follows:
32> funparse:parse([a,c]). {ok,{'and',{'or',1,{const,a}},{'or',1,{const,c}}}} 33> funparse:parse([a,d]). {ok,{'and',{'or',1,{const,a}},{'or',2,{const,d}}}} 34> funparse:parse([b,c]). {ok,{'and',{'or',2,{const,b}},{'or',1,{const,c}}}} 35> funparse:parse([b,d]). {ok,{'and',{'or',2,{const,b}},{'or',2,{const,d}}}} 36> funparse:parse([a,b]). fail