diff options
Diffstat (limited to 'system/doc/programming_examples/funs.xmlsrc')
| -rw-r--r-- | system/doc/programming_examples/funs.xmlsrc | 515 |
1 files changed, 515 insertions, 0 deletions
diff --git a/system/doc/programming_examples/funs.xmlsrc b/system/doc/programming_examples/funs.xmlsrc new file mode 100644 index 0000000000..92f99cf6d3 --- /dev/null +++ b/system/doc/programming_examples/funs.xmlsrc @@ -0,0 +1,515 @@ +<?xml version="1.0" encoding="latin1" ?> +<!DOCTYPE chapter SYSTEM "chapter.dtd"> + +<chapter> + <header> + <copyright> + <year>2003</year><year>2009</year> + <holder>Ericsson AB. All Rights Reserved.</holder> + </copyright> + <legalnotice> + The contents of this file are subject to the Erlang Public License, + Version 1.1, (the "License"); you may not use this file except in + compliance with the License. You should have received a copy of the + Erlang Public License along with this software. If not, it can be + retrieved online at http://www.erlang.org/. + + Software distributed under the License is distributed on an "AS IS" + basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See + the License for the specific language governing rights and limitations + under the License. + + </legalnotice> + + <title>Funs</title> + <prepared></prepared> + <docno></docno> + <date></date> + <rev></rev> + <file>funs.xml</file> + </header> + + <section> + <title>Example 1 - map</title> + <p>If we want to double every element in a list, we could write a + function named <c>double</c>:</p> + <code type="none"> +double([H|T]) -> [2*H|double(T)]; +double([]) -> [].</code> + <p>This function obviously doubles the argument entered as input + as follows:</p> + <pre> +> <input>double([1,2,3,4]).</input> +[2,4,6,8]</pre> + <p>We now add the function <c>add_one</c>, which adds one to every + element in a list:</p> + <code type="none"> +add_one([H|T]) -> [H+1|add_one(T)]; +add_one([]) -> [].</code> + <p>These functions, <c>double</c> and <c>add_one</c>, have a very + similar structure. We can exploit this fact and write a function + <c>map</c> which expresses this similarity:</p> + <codeinclude file="funs1.erl" tag="%1" type="erl"></codeinclude> + <p>We can now express the functions <c>double</c> and + <c>add_one</c> in terms of <c>map</c> as follows:</p> + <code type="none"> +double(L) -> map(fun(X) -> 2*X end, L). +add_one(L) -> map(fun(X) -> 1 + X end, L).</code> + <p><c>map(F, List)</c> is a function which takes a function + <c>F</c> and a list <c>L</c> as arguments and returns the new + list which is obtained by applying <c>F</c> to each of + the elements in <c>L</c>.</p> + <p>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:</p> + <list type="ordered"> + <item>write one function which represents the common features of + these functions</item> + <item>parameterize the difference in terms of functions which + are passed as arguments to the common function.</item> + </list> + </section> + + <section> + <title>Example 2 - foreach</title> + <p>This example illustrates procedural abstraction. Initially, we + show the following two examples written as conventional + functions:</p> + <list type="ordered"> + <item>all elements of a list are printed onto a stream</item> + <item>a message is broadcast to a list of processes.</item> + </list> + <code type="none"> +print_list(Stream, [H|T]) -> + io:format(Stream, "~p~n", [H]), + print_list(Stream, T); +print_list(Stream, []) -> + true.</code> + <code type="none"> +broadcast(Msg, [Pid|Pids]) -> + Pid ! Msg, + broadcast(Msg, Pids); +broadcast(_, []) -> + true.</code> + <p>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.</p> + <p>The function <c>foreach</c> expresses this similarity:</p> + <codeinclude file="funs1.erl" tag="%2" type="erl"></codeinclude> + <p>Using <c>foreach</c>, <c>print_list</c> becomes:</p> + <code type="none"> +foreach(fun(H) -> io:format(S, "~p~n",[H]) end, L)</code> + <p><c>broadcast</c> becomes:</p> + <code type="none"> +foreach(fun(Pid) -> Pid ! M end, L)</code> + <p><c>foreach</c> is evaluated for its side-effect and not its + value. <c>foreach(Fun ,L)</c> calls <c>Fun(X)</c> for each + element <c>X</c> in <c>L</c> and the processing occurs in + the order in which the elements were defined in <c>L</c>. + <c>map</c> does not define the order in which its elements are + processed.</p> + </section> + + <section> + <title>The Syntax of Funs</title> + <p>Funs are written with the syntax:</p> + <code type="none"> +F = fun (Arg1, Arg2, ... ArgN) -> + ... + end</code> + <p>This creates an anonymous function of <c>N</c> arguments and + binds it to the variable <c>F</c>.</p> + <p>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:</p> + <code type="none"> +F = fun FunctionName/Arity</code> + <p>With this form of function reference, the function which is + referred to does not need to be exported from the module.</p> + <p>We can also refer to a function defined in a different module + with the following syntax:</p> + <code type="none"> +F = {Module, FunctionName}</code> + <p>In this case, the function must be exported from the module in + question.</p> + <p>The follow program illustrates the different ways of creating + funs:</p> + <codeinclude file="fun_test.erl" tag="%1" type="erl"></codeinclude> + <p>We can evaluate the fun <c>F</c> with the syntax:</p> + <code type="none"> +F(Arg1, Arg2, ..., Argn)</code> + <p>To check whether a term is a fun, use the test + <c>is_function/1</c> in a guard. Example:</p> + <code type="none"> +f(F, Args) when is_function(F) -> + apply(F, Args); +f(N, _) when is_integer(N) -> + N.</code> + <p>Funs are a distinct type. The BIFs erlang:fun_info/1,2 can + be used to retrieve information about a fun, and the BIF + erlang:fun_to_list/1 returns a textual representation of a fun. + The check_process_code/2 BIF returns true if the process + contains funs that depend on the old version of a module.</p> + <note> + <p>In OTP R5 and earlier releases, funs were represented using + tuples.</p> + </note> + </section> + + <section> + <title>Variable Bindings Within a Fun</title> + <p>The scope rules for variables which occur in funs are as + follows:</p> + <list type="bulleted"> + <item>All variables which occur in the head of a fun are assumed + to be "fresh" variables.</item> + <item>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.</item> + <item>No variables may be exported from a fun.</item> + </list> + <p>The following examples illustrate these rules:</p> + <code type="none"> +print_list(File, List) -> + {ok, Stream} = file:open(File, write), + foreach(fun(X) -> io:format(Stream,"~p~n",[X]) end, List), + file:close(Stream).</code> + <p>In the above example, the variable <c>X</c> which is defined in + the head of the fun is a new variable. The value of the variable + <c>Stream</c> which is used within within the fun gets its value + from the <c>file:open</c> line.</p> + <p>Since any variable which occurs in the head of a fun is + considered a new variable it would be equally valid to write:</p> + <code type="none"> +print_list(File, List) -> + {ok, Stream} = file:open(File, write), + foreach(fun(File) -> + io:format(Stream,"~p~n",[File]) + end, List), + file:close(Stream).</code> + <p>In this example, <c>File</c> is used as the new variable + instead of <c>X</c>. This is rather silly since code in the body + of the fun cannot refer to the variable <c>File</c> which is + defined outside the fun. Compiling this example will yield + the diagnostic:</p> + <code type="none"> +./FileName.erl:Line: Warning: variable 'File' + shadowed in 'lambda head'</code> + <p>This reminds us that the variable <c>File</c> which is defined + inside the fun collides with the variable <c>File</c> which is + defined outside the fun.</p> + <p>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 <c>F</c> to be evaluated when the value of + its argument is <c>Y</c>:</p> + <code type="none"> +f(...) -> + Y = ... + map(fun(X) when X == Y -> + ; + (_) -> + ... + end, ...) + ...</code> + <p>instead of</p> + <code type="none"> +f(...) -> + Y = ... + map(fun(Y) -> + ; + (_) -> + ... + end, ...) + ...</code> + </section> + + <section> + <title>Funs and the Module Lists</title> + <p>The following examples show a dialogue with the Erlang shell. + All the higher order functions discussed are exported from + the module <c>lists</c>.</p> + + <section> + <title>map</title> + <codeinclude file="funs1.erl" tag="%1" type="erl"></codeinclude> + <p><c>map</c> 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.</p> + <pre> +> <input>Double = fun(X) -> 2 * X end.</input> +#Fun<erl_eval.6.72228031> +> <input>lists:map(Double, [1,2,3,4,5]).</input> +[2,4,6,8,10]</pre> + <p>When a new fun is defined in the shell, the value of the Fun + is printed as <c><![CDATA[Fun#<erl_eval>]]></c>.</p> + </section> + + <section> + <title>any</title> + <codeinclude file="funs1.erl" tag="%4" type="erl"></codeinclude> + <p><c>any</c> takes a predicate <c>P</c> of one argument and a + list of terms. A predicate is a function which returns + <c>true</c> or <c>false</c>. <c>any</c> is true if there is a + term <c>X</c> in the list such that <c>P(X)</c> is <c>true</c>.</p> + <p>We define a predicate <c>Big(X)</c> which is <c>true</c> if + its argument is greater that 10.</p> + <pre> +> <input>Big = fun(X) -> if X > 10 -> true; true -> false end end.</input> +#Fun<erl_eval.6.72228031> +> <input>lists:any(Big, [1,2,3,4]).</input> +false +> <input>lists:any(Big, [1,2,3,12,5]).</input> +true</pre> + </section> + + <section> + <title>all</title> + <codeinclude file="funs1.erl" tag="%3" type="erl"></codeinclude> + <p><c>all</c> has the same arguments as <c>any</c>. It is true + if the predicate applied to all elements in the list is true.</p> + <pre> +> <input>lists:all(Big, [1,2,3,4,12,6]).</input> +false +> <input>lists:all(Big, [12,13,14,15]).</input> +true</pre> + </section> + + <section> + <title>foreach</title> + <codeinclude file="funs1.erl" tag="%2" type="erl"></codeinclude> + <p><c>foreach</c> takes a function of one argument and a list of + terms. The function is applied to each argument in the list. + <c>foreach</c> returns <c>ok</c>. It is used for its + side-effect only.</p> + <pre> +> <input>lists:foreach(fun(X) -> io:format("~w~n",[X]) end, [1,2,3,4]).</input> +1 +2 +3 +4 +ok</pre> + </section> + + <section> + <title>foldl</title> + <codeinclude file="funs1.erl" tag="%8" type="erl"></codeinclude> + <p><c>foldl</c> 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.</p> + <p>If we have a list of lists <c>L = ["I","like","Erlang"]</c>, + then we can sum the lengths of all the strings in <c>L</c> as + follows:</p> + <pre> +> <input>L = ["I","like","Erlang"].</input> +["I","like","Erlang"] +10> <input>lists:foldl(fun(X, Sum) -> length(X) + Sum end, 0, L).</input> +11</pre> + <p><c>foldl</c> works like a <c>while</c> loop in an imperative + language:</p> + <code type="none"> +L = ["I","like","Erlang"], +Sum = 0, +while( L != []){ + Sum += length(head(L)), + L = tail(L) +end</code> + </section> + + <section> + <title>mapfoldl</title> + <codeinclude file="funs1.erl" tag="%10" type="erl"></codeinclude> + <p><c>mapfoldl</c> simultaneously maps and folds over a list. + The following example shows how to change all letters in + <c>L</c> to upper case and count them.</p> + <p>First upcase:</p> + <pre> +> <input>Upcase = fun(X) when $a =< X, X =< $z -> X + $A - $a;</input> +<input>(X) -> X</input> +<input>end.</input> +#Fun<erl_eval.6.72228031> +> <input>Upcase_word =</input> +<input>fun(X) -></input> +<input>lists:map(Upcase, X)</input> +<input>end.</input> +#Fun<erl_eval.6.72228031> +> <input>Upcase_word("Erlang").</input> +"ERLANG" +> <input>lists:map(Upcase_word, L).</input> +["I","LIKE","ERLANG"]</pre> + <p>Now we can do the fold and the map at the same time:</p> + <pre> +> <input>lists:mapfoldl(fun(Word, Sum) -></input> +<input>{Upcase_word(Word), Sum + length(Word)}</input> +<input>end, 0, L).</input> +{["I","LIKE","ERLANG"],11}</pre> + </section> + + <section> + <title>filter</title> + <codeinclude file="funs1.erl" tag="%9" type="erl"></codeinclude> + <p><c>filter</c> takes a predicate of one argument and a list + and returns all element in the list which satisfy + the predicate.</p> + <pre> +> <input>lists:filter(Big, [500,12,2,45,6,7]).</input> +[500,12,45]</pre> + <p>When we combine maps and filters we can write very succinct + code. For example, suppose we want to define a set difference + function. We want to define <c>diff(L1, L2)</c> to be + the difference between the lists <c>L1</c> and <c>L2</c>. + This is the list of all elements in L1 which are not contained + in L2. This code can be written as follows:</p> + <code type="none"> +diff(L1, L2) -> + filter(fun(X) -> not member(X, L2) end, L1).</code> + <p>The AND intersection of the list <c>L1</c> and <c>L2</c> is + also easily defined:</p> + <code type="none"> +intersection(L1,L2) -> filter(fun(X) -> member(X,L1) end, L2).</code> + </section> + + <section> + <title>takewhile</title> + <codeinclude file="funs1.erl" tag="%5" type="erl"></codeinclude> + <p><c>takewhile(P, L)</c> takes elements <c>X</c> from a list + <c>L</c> as long as the predicate <c>P(X)</c> is true.</p> + <pre> +> <input>lists:takewhile(Big, [200,500,45,5,3,45,6]).</input> +[200,500,45]</pre> + </section> + + <section> + <title>dropwhile</title> + <codeinclude file="funs1.erl" tag="%6" type="erl"></codeinclude> + <p><c>dropwhile</c> is the complement of <c>takewhile</c>.</p> + <pre> +> <input>lists:dropwhile(Big, [200,500,45,5,3,45,6]).</input> +[5,3,45,6]</pre> + </section> + + <section> + <title>splitwith</title> + <codeinclude file="funs1.erl" tag="%7" type="erl"></codeinclude> + <p><c>splitwith(P, L)</c> splits the list <c>L</c> into the two + sub-lists <c>{L1, L2}</c>, where <c>L = takewhile(P, L)</c> + and <c>L2 = dropwhile(P, L)</c>.</p> + <pre> +> <input>lists:splitwith(Big, [200,500,45,5,3,45,6]).</input> +{[200,500,45],[5,3,45,6]}</pre> + </section> + </section> + + <section> + <title>Funs Which Return Funs</title> + <p>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.</p> + + <section> + <title>Simple Higher Order Functions</title> + <p><c>Adder(X)</c> is a function which, given <c>X</c>, returns + a new function <c>G</c> such that <c>G(K)</c> returns + <c>K + X</c>.</p> + <pre> +> <input>Adder = fun(X) -> fun(Y) -> X + Y end end.</input> +#Fun<erl_eval.6.72228031> +> <input>Add6 = Adder(6).</input> +#Fun<erl_eval.6.72228031> +> <input>Add6(10).</input> +16</pre> + </section> + + <section> + <title>Infinite Lists</title> + <p>The idea is to write something like:</p> + <code type="none"> +-module(lazy). +-export([ints_from/1]). +ints_from(N) -> + fun() -> + [N|ints_from(N+1)] + end.</code> + <p>Then we can proceed as follows:</p> + <pre> +> <input>XX = lazy:ints_from(1).</input> +#Fun<lazy.0.29874839> +> <input>XX().</input> +[1|#Fun<lazy.0.29874839>] +> <input>hd(XX()).</input> +1 +> <input>Y = tl(XX()).</input> +#Fun<lazy.0.29874839> +> <input>hd(Y()).</input> +2</pre> + <p>etc. - this is an example of "lazy embedding".</p> + </section> + + <section> + <title>Parsing</title> + <p>The following examples show parsers of the following type:</p> + <pre> +Parser(Toks) -> {ok, Tree, Toks1} | fail</pre> + <p><c>Toks</c> is the list of tokens to be parsed. A successful + parse returns <c>{ok, Tree, Toks1}</c>, where <c>Tree</c> is a + parse tree and <c>Toks1</c> is a tail of <c>Tree</c> which + contains symbols encountered after the structure which was + correctly parsed. Otherwise <c>fail</c> is returned.</p> + <p>The example which follows illustrates a simple, functional + parser which parses the grammar:</p> + <pre> +(a | b) & (c | d)</pre> + <p>The following code defines a function <c>pconst(X)</c> in + the module <c>funparse</c>, which returns a fun which parses a + list of tokens.</p> + <codeinclude file="funparse.erl" tag="%14" type="erl"></codeinclude> + <p>This function can be used as follows:</p> + <pre> +> <input>P1 = funparse:pconst(a).</input> +#Fun<funparse.0.22674075> +> <input>P1([a,b,c]).</input> +{ok,{const,a},[b,c]} +> <input>P1([x,y,z]).</input> +fail</pre> + <p>Next, we define the two higher order functions <c>pand</c> + and <c>por</c> which combine primitive parsers to produce more + complex parsers. Firstly <c>pand</c>:</p> + <codeinclude file="funparse.erl" tag="%16" type="erl"></codeinclude> + <p>Given a parser <c>P1</c> for grammar <c>G1</c>, and a parser + <c>P2</c> for grammar <c>G2</c>, <c>pand(P1, P2)</c> returns a + parser for the grammar which consists of sequences of tokens + which satisfy <c>G1</c> followed by sequences of tokens which + satisfy <c>G2</c>.</p> + <p><c>por(P1, P2)</c> returns a parser for the language + described by the grammar <c>G1</c> or <c>G2</c>.</p> + <codeinclude file="funparse.erl" tag="%15" type="erl"></codeinclude> + <p>The original problem was to parse the grammar + <c><![CDATA[(a | b) & (c | d)]]></c>. The following code addresses this + problem:</p> + <codeinclude file="funparse.erl" tag="%13" type="erl"></codeinclude> + <p>The following code adds a parser interface to the grammar:</p> + <codeinclude file="funparse.erl" tag="%12" type="erl"></codeinclude> + <p>We can test this parser as follows:</p> + <pre> +> <input>funparse:parse([a,c]).</input> +{ok,{'and',{'or',1,{const,a}},{'or',1,{const,c}}}} +> <input>funparse:parse([a,d]).</input> +{ok,{'and',{'or',1,{const,a}},{'or',2,{const,d}}}} +> <input>funparse:parse([b,c]).</input> +{ok,{'and',{'or',2,{const,b}},{'or',1,{const,c}}}} +> <input>funparse:parse([b,d]).</input> +{ok,{'and',{'or',2,{const,b}},{'or',2,{const,d}}}} +> <input>funparse:parse([a,b]).</input> +fail</pre> + </section> + </section> +</chapter> + |