Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 4183461[1X4 [33X[0;0YFunctions[133X[101X23[33X[0;0YYou have already seen how to use functions in the [5XGAP[105X library, i.e., how to4apply them to arguments.[133X56[33X[0;0YIn this section you will see how to write functions in the [5XGAP[105X language. You7will also see how to use the [9Xif[109X statement and declare local variables with8the [9Xlocal[109X statement in the function definition. Loop constructions via [9Xwhile[109X9and [9Xfor[109X are discussed further, as are recursive functions.[133X101112[1X4.1 [33X[0;0YWriting Functions[133X[101X1314[33X[0;0YWriting a function that prints [10Xhello, world.[110X on the screen is a simple15exercise in [5XGAP[105X.[133X1617[4X[32X Example [32X[104X18[4X[25Xgap>[125X [27Xsayhello:= function()[127X[104X19[4X[25X>[125X [27XPrint("hello, world.\n");[127X[104X20[4X[25X>[125X [27Xend;[127X[104X21[4X[28Xfunction( ) ... end[128X[104X22[4X[32X[104X2324[33X[0;0YThis function when called will only execute the [10XPrint[110X statement in the25second line. This will print the string [10Xhello, world.[110X on the screen followed26by a newline character [10X\n[110X that causes the [5XGAP[105X prompt to appear on the next27line rather than immediately following the printed characters.[133X2829[33X[0;0YThe function definition has the following syntax.[133X3031[33X[0;0Y[9Xfunction[109X[10X( [3Xarguments[103X[10X ) [3Xstatements[103X[10X[110X [9Xend[109X[133X3233[33X[0;0YA function definition starts with the keyword [9Xfunction[109X followed by the34formal parameter list [3Xarguments[103X enclosed in parenthesis [10X( )[110X. The formal35parameter list may be empty as in the example. Several parameters are36separated by commas. Note that there must be [13Xno[113X semicolon behind the closing37parenthesis. The function definition is terminated by the keyword [9Xend[109X.[133X3839[33X[0;0YA [5XGAP[105X function is an expression like an integer, a sum or a list. Therefore40it may be assigned to a variable. The terminating semicolon in the example41does not belong to the function definition but terminates the assignment of42the function to the name [10Xsayhello[110X. Unlike in the case of integers, sums, and43lists the value of the function [10Xsayhello[110X is echoed in the abbreviated44fashion [10Xfunction( ) ... end[110X. This shows the most interesting part of a45function: its formal parameter list (which is empty in this example). The46complete value of [10Xsayhello[110X is returned if you use the function [2XPrint[102X47([14XReference: Print[114X).[133X4849[4X[32X Example [32X[104X50[4X[25Xgap>[125X [27XPrint(sayhello, "\n");[127X[104X51[4X[28Xfunction ( )[128X[104X52[4X[28X Print( "hello, world.\n" );[128X[104X53[4X[28X return;[128X[104X54[4X[28Xend[128X[104X55[4X[32X[104X5657[33X[0;0YNote the additional newline character [10X"\n"[110X in the [2XPrint[102X ([14XReference: Print[114X)58statement. It is printed after the object [10Xsayhello[110X to start a new line. The59extra [9Xreturn[109X statement is inserted by [5XGAP[105X to simplify the process of60executing the function.[133X6162[33X[0;0YThe newly defined function [10Xsayhello[110X is executed by calling [10Xsayhello()[110X with63an empty argument list.[133X6465[4X[32X Example [32X[104X66[4X[25Xgap>[125X [27Xsayhello();[127X[104X67[4X[28Xhello, world.[128X[104X68[4X[32X[104X6970[33X[0;0YHowever, this is not a typical example as no value is returned but only a71string is printed.[133X727374[1X4.2 [33X[0;0YIf Statements[133X[101X7576[33X[0;0YIn the following example we define a function [10Xsign[110X which determines the sign77of an integer.[133X7879[4X[32X Example [32X[104X80[4X[25Xgap>[125X [27Xsign:= function(n)[127X[104X81[4X[25X>[125X [27X if n < 0 then[127X[104X82[4X[25X>[125X [27X return -1;[127X[104X83[4X[25X>[125X [27X elif n = 0 then[127X[104X84[4X[25X>[125X [27X return 0;[127X[104X85[4X[25X>[125X [27X else[127X[104X86[4X[25X>[125X [27X return 1;[127X[104X87[4X[25X>[125X [27X fi;[127X[104X88[4X[25X>[125X [27X end;[127X[104X89[4X[28Xfunction( n ) ... end[128X[104X90[4X[25Xgap>[125X [27Xsign(0); sign(-99); sign(11);[127X[104X91[4X[28X0[128X[104X92[4X[28X-1[128X[104X93[4X[28X1[128X[104X94[4X[32X[104X9596[33X[0;0YThis example also introduces the [9Xif[109X statement which is used to execute97statements depending on a condition. The [9Xif[109X statement has the following98syntax.[133X99100[33X[0;0Y[9Xif[109X [3Xcondition[103X [9Xthen[109X [3Xstatements[103X [9Xelif[109X [3Xcondition[103X [9Xthen[109X [3Xstatements[103X [9Xelse[109X [3Xstatements[103X101[9Xfi[109X[133X102103[33X[0;0YThere may be several [9Xelif[109X parts. The [9Xelif[109X part as well as the [9Xelse[109X part of104the [9Xif[109X statement may be omitted. An [9Xif[109X statement is no expression and can105therefore not be assigned to a variable. Furthermore an [9Xif[109X statement does106not return a value.[133X107108[33X[0;0YFibonacci numbers are defined recursively by [22Xf(1) = f(2) = 1[122X and [22Xf(n) =109f(n-1) + f(n-2)[122X for [22Xn ≥ 3[122X. Since functions in [5XGAP[105X may call themselves, a110function [10Xfib[110X that computes Fibonacci numbers can be implemented basically by111typing the above equations. (Note however that this is a very inefficient112way to compute [22Xf(n)[122X.)[133X113114[4X[32X Example [32X[104X115[4X[25Xgap>[125X [27Xfib:= function(n)[127X[104X116[4X[25X>[125X [27X if n in [1, 2] then[127X[104X117[4X[25X>[125X [27X return 1;[127X[104X118[4X[25X>[125X [27X else[127X[104X119[4X[25X>[125X [27X return fib(n-1) + fib(n-2);[127X[104X120[4X[25X>[125X [27X fi;[127X[104X121[4X[25X>[125X [27X end;[127X[104X122[4X[28Xfunction( n ) ... end[128X[104X123[4X[25Xgap>[125X [27Xfib(15);[127X[104X124[4X[28X610[128X[104X125[4X[32X[104X126127[33X[0;0YThere should be additional tests for the argument [10Xn[110X being a positive128integer. This function [10Xfib[110X might lead to strange results if called with129other arguments. Try inserting the necessary tests into this example.[133X130131132[1X4.3 [33X[0;0YLocal Variables[133X[101X133134[33X[0;0YA function [10Xgcd[110X that computes the greatest common divisor of two integers by135Euclid's algorithm will need a variable in addition to the formal arguments.[133X136137[4X[32X Example [32X[104X138[4X[25Xgap>[125X [27Xgcd:= function(a, b)[127X[104X139[4X[25X>[125X [27X local c;[127X[104X140[4X[25X>[125X [27X while b <> 0 do[127X[104X141[4X[25X>[125X [27X c:= b;[127X[104X142[4X[25X>[125X [27X b:= a mod b;[127X[104X143[4X[25X>[125X [27X a:= c;[127X[104X144[4X[25X>[125X [27X od;[127X[104X145[4X[25X>[125X [27X return c;[127X[104X146[4X[25X>[125X [27X end;[127X[104X147[4X[28Xfunction( a, b ) ... end[128X[104X148[4X[25Xgap>[125X [27Xgcd(30, 63);[127X[104X149[4X[28X3[128X[104X150[4X[32X[104X151152[33X[0;0YThe additional variable [10Xc[110X is declared as a [13Xlocal[113X variable in the [9Xlocal[109X153statement of the function definition. The [9Xlocal[109X statement, if present, must154be the first statement of a function definition. When several local155variables are declared in only one [9Xlocal[109X statement they are separated by156commas.[133X157158[33X[0;0YThe variable [10Xc[110X is indeed a local variable, that is local to the function159[10Xgcd[110X. If you try to use the value of [10Xc[110X in the main loop you will see that [10Xc[110X160has no assigned value unless you have already assigned a value to the161variable [10Xc[110X in the main loop. In this case the local nature of [10Xc[110X in the162function [10Xgcd[110X prevents the value of the [10Xc[110X in the main loop from being163overwritten.[133X164165[4X[32X Example [32X[104X166[4X[25Xgap>[125X [27Xc:= 7;;[127X[104X167[4X[25Xgap>[125X [27Xgcd(30, 63);[127X[104X168[4X[28X3[128X[104X169[4X[25Xgap>[125X [27Xc;[127X[104X170[4X[28X7[128X[104X171[4X[32X[104X172173[33X[0;0YWe say that in a given scope an identifier identifies a unique variable. A174[13Xscope[113X is a lexical part of a program text. There is the global scope that175encloses the entire program text, and there are local scopes that range from176the [9Xfunction[109X keyword, denoting the beginning of a function definition, to177the corresponding [9Xend[109X keyword. A local scope introduces new variables, whose178identifiers are given in the formal argument list and the local declaration179of the function. The usage of an identifier in a program text refers to the180variable in the innermost scope that has this identifier as its name.[133X181182183[1X4.4 [33X[0;0YRecursion[133X[101X184185[33X[0;0YWe have already seen recursion in the function [10Xfib[110X in Section [14X4.2[114X. Here is186another, slightly more complicated example.[133X187188[33X[0;0YWe will now write a function to determine the number of partitions of a189positive integer. A partition of a positive integer is a descending list of190numbers whose sum is the given integer. For example [22X[4,2,1,1][122X is a partition191of 8. Note that there is just one partition of 0, namely [22X[ ][122X. The complete192set of all partitions of an integer [22Xn[122X may be divided into subsets with193respect to the largest element. The number of partitions of [22Xn[122X therefore194equals the sum of the numbers of partitions of [22Xn-i[122X with elements less than195or equal to [22Xi[122X for all possible [22Xi[122X. More generally the number of partitions of196[22Xn[122X with elements less than [22Xm[122X is the sum of the numbers of partitions of [22Xn-i[122X197with elements less than [22Xi[122X for [22Xi[122X less than [22Xm[122X and [22Xn[122X. This description yields198the following function.[133X199200[4X[32X Example [32X[104X201[4X[25Xgap>[125X [27Xnrparts:= function(n)[127X[104X202[4X[25X>[125X [27X local np;[127X[104X203[4X[25X>[125X [27X np:= function(n, m)[127X[104X204[4X[25X>[125X [27X local i, res;[127X[104X205[4X[25X>[125X [27X if n = 0 then[127X[104X206[4X[25X>[125X [27X return 1;[127X[104X207[4X[25X>[125X [27X fi;[127X[104X208[4X[25X>[125X [27X res:= 0;[127X[104X209[4X[25X>[125X [27X for i in [1..Minimum(n,m)] do[127X[104X210[4X[25X>[125X [27X res:= res + np(n-i, i);[127X[104X211[4X[25X>[125X [27X od;[127X[104X212[4X[25X>[125X [27X return res;[127X[104X213[4X[25X>[125X [27X end;[127X[104X214[4X[25X>[125X [27X return np(n,n);[127X[104X215[4X[25X>[125X [27Xend;[127X[104X216[4X[28Xfunction( n ) ... end[128X[104X217[4X[32X[104X218219[33X[0;0YWe wanted to write a function that takes one argument. We solved the problem220of determining the number of partitions in terms of a recursive procedure221with two arguments. So we had to write in fact two functions. The function222[10Xnrparts[110X that can be used to compute the number of partitions indeed takes223only one argument. The function [10Xnp[110X takes two arguments and solves the224problem in the indicated way. The only task of the function [10Xnrparts[110X is to225call [10Xnp[110X with two equal arguments.[133X226227[33X[0;0YWe made [10Xnp[110X local to [10Xnrparts[110X. This illustrates the possibility of having228local functions in [5XGAP[105X. It is however not necessary to put it there. [10Xnp[110X229could as well be defined on the main level, but then the identifier [10Xnp[110X would230be bound and could not be used for other purposes, and if it were used the231essential function [10Xnp[110X would no longer be available for [10Xnrparts[110X.[133X232233[33X[0;0YNow have a look at the function [10Xnp[110X. It has two local variables [10Xres[110X and [10Xi[110X.234The variable [10Xres[110X is used to collect the sum and [10Xi[110X is a loop variable. In the235loop the function [10Xnp[110X calls itself again with other arguments. It would be236very disturbing if this call of [10Xnp[110X was to use the same [10Xi[110X and [10Xres[110X as the237calling [10Xnp[110X. Since the new call of [10Xnp[110X creates a new scope with new variables238this is fortunately not the case.[133X239240[33X[0;0YNote that the formal parameters [3Xn[103X and [3Xm[103X of [10Xnp[110X are treated like local241variables.[133X242243[33X[0;0Y(Regardless of the recursive structure of an algorithm it is often cheaper244(in terms of computing time) to avoid a recursive implementation if possible245(and it is possible in this case), because a function call is not very246cheap.)[133X247248249[1X4.5 [33X[0;0YFurther Information about Functions[133X[101X250251[33X[0;0YThe function syntax is described in Section [14X'Reference: Functions'[114X. The [9Xif[109X252statement is described in more detail in Section [14X'Reference: If'[114X. More about253Fibonacci numbers is found in Section [2XFibonacci[102X ([14XReference: Fibonacci[114X) and254more about partitions in Section [2XPartitions[102X ([14XReference: Partitions[114X).[133X255256257258