Den lille Erlanger

tirsdag 10. juli 2012 Erlang Funksjonell programmering Rekursjon

Dette er en tutorial som lærer deg grunnleggende Erlang og noen grunnleggende teknikker fra funksjonell programmering. Formatet er inspirert av boken The Little Schemer (og de andre bøkene i den serien). Vi begynner helt fra scratch, men bygger raskt opp ganske mye kunnskap om språket. Følg nøye med!

Har du ikke peiling på hva Erlang er for noe kan du leste min lille introduksjon som jeg skrev i 2010.

La oss begynne...

Er du klar for å lære litt Erlang og funksjonell programmering?

 Ja!

Hva er 1?

 Det er et heltall.

Hva er X?

X = 2.
 X er en variabel. X er bundet til verdien 2.
Legg merke til punktumet etter uttrykket. Alle uttrykk avsluttes med et punktum - som om de er normale setninger.

Hvilken verdi er Y bundet til?

X = 3, 
Y = X.
 X er bundet til verdien 3, og Y er bundet til X. Y er derfor også bundet til verdien 3.
Legg merke til at dette uttrykket består av to del-uttrykk, og at de er separert med komma - akkurat som leddsetninger.

Følgende uttrykk vil feile. Hvorfor?

X = 4, 
Y = 5, 
Y = X.
 En variabel i Erlang kan kun bindes til en verdi én gang. Etter at vi har sagt at Y er bundet til 5 kan den ikke bindes på nytt. Hvis X er lik 4 og Y er lik 5, så kan X ikke være lik Y.

Følgende uttrykk feiler ikke. Hvorfor?

X = 6, 
Y = 6, 
Y = X.
 Både X og Y er bundet til verdien 6. X er derfor lik Y, så X = Y feiler ikke.

Hva er X bundet til nå?

X = foo.
 X er bundet til atomet foo. Et atom er en grunnleggende datatype på lik linje med tall. De skiller seg fra variabler ved å begynne med en liten bokstav - variabelnavn begynner alltid med en stor bokstav.

Hva er dette?

{epler, bananer, plummer}
 En datastruktur som kalles en tuple. I dette tilfellet er det en 3-tuple (også kalt triplet) av tre atomer.

Hva er verdien av Person?

GivenName = "Bill", 
SurName = "Gates", 
Person = {person, GivenName, SurName}.
 Person er bundet til en triplet bestående av atomet 'person' og to strenger. Verdien er {person, "Bill", "Gates"}.

Hva er verdien av G og S?

P = {person, "Steve", "Jobs"}, 
{person, G, S} = P.
 G er bundet til strengen "Steve" og S er bundet til strengen "Jobs". Dette kalles pattern matching.

Vil dette fungere?

P = {author, "Joe", "Armstrong"}, 
{person, G, S} = P.
 Nei, atomet person matcher ikke atomet author.

Hva er verdien av dette uttrykket?

P = {man, "Adam"}, 
{_, Name} = P, 
Name.
 Verdien av dette uttrykket er strengen "Adam". Og deluttrykk 2 fungerer fordi vi nå matcher et atom med en underscore, som kan matche hva som helst.

Hva er dette?

[1, 2, 3, 4, 5].
 Dette er en liste. Listen består av fem tall. 

Hva er verdien av X?

[_, X, _] = [1, 2, 3].
 X er bundet til heltallet 2. Dette er også et eksempel på pattern matching.

Hva er verdien av dette uttrykket?

L = [2, 4, 8, 16, 32], 
[Head|Tail] = L, 
Head.
 Vertikal strek (pipe) brukes til å splitte en liste mellom "hodet" og "halen". Dette uttrykket evaluerer til heltallet 2.

Og dette?

L = [2, 4, 8, 16, 32], 
[Head|Tail] = L, 
Tail.
 Verdien av dette uttrykket er listen [4, 8, 16, 32].

Hva er hodet og halen av en liste med ett element?

[Head|Tail] = [a].
 Head = a og Tail = [], den tomme listen.

Kan du plukke ut hode og hale av den tomme listen?

[Head|Tail] = [].
 Nei, dette vil feile.

Hvilken verdi er det vi har trukket ut fra listen nå?

L = [2, 4, 8, 16, 32], 
[_|T] = L, 
[_|T2] = T, 
[H|_] = T2, 
H.
 T er halen av den opprinnelige listen, dvs. en liste som begynner med 4. T2 er halen av denne listen igjen, og begynner på 8. Variabelen H er bundet til hodet på T2, og uttrykket returnerer derfor 8.

Kan det forrige uttrykket skrives mere kompakt?

L = [2, 4, 8, 16, 32], 
[_, _, H | _] = L, 
H.
 Tydeligvis, for dette uttrykket returnerer også 8.

Hva er verdien av double(1)?

double(X) -> X + X.
 double har her blitt definert som en funksjon, og resultatet av å evaluere double(1) er heltallet 2.

Hva er verdien av sum([1, 2, 3]) gitt følgende definisjon?

sum([A, B, C]) -> A + B + C.
 Her har vi laget en sum-funksjon som har en formell parameter som må være en liste med tre element. Igjen bruker vi pattern matching, og svaret er 6.

Hva er verdien av second([1, 2, 3, 4])?

second([_, X | _]) -> X.
 2.

Hva er verdien av S1 og S2?

second([_,X|_]) -> X; 
second(_)       -> no_second_element. 

S1 = second([1]), 
S2 = second([1, 2]).
 S1 er bundet til atomet no_second_element, mens S2 er bundet til tallet 2. Funksjonen second har nå to ulike klauser (clauses), og pattern matching avgjør hvilken av dem som blir brukt.

Nå bruker vi det vi har lært til å telle antall elementer i en liste.

count([ ])   -> 0; 
count([_,T]) -> 1 + count(T).
 Antall elementer i en tom liste er 0. Antall elementer i en liste som ikke er tom er 1 pluss antall elementer i halen av listen. Funksjonen kaller seg selv til den har "spist opp" hele listen. Dette er en rekursjon.

Her er en annen måte vi kan telle elementene i en liste på. Hva er forskjellen?

count(List) -> count(List, 0). 

count([], Acc)    -> Acc; 
count([_|T], Acc) -> count(T, Acc + 1).
Her har vi to ulike funksjoner med samme navn men med ulikt antall parametre. Vi kaller dem count/1 og count/2 fordi de har henholdsvis ett og to formelle parametre. count/2 bygger opp resultatet i variabelen Acc (står for accumulator).

Legg merke til at det rekursive kallet til count er det siste som skjer i count. Dette kalles en halerekursjon, og er mye mere effektivt enn rekursjonen i den forrige implementasjonen av count. Men det kan være mere komplisert å forstå koden.. 

Hva er resultatet av dette uttrykket?

F = fun (X) -> X * 3 end, 
F(3).
 Variabelen F bindes til en anonym funksjon som multipliserer argumentet sitt med 3. Resultatet av uttrykket er 9.

Funksjoner kan være argumenter til andre funksjoner. Hva er verdien av X her?

map(_, [])            -> []; 
map(Fun, [Head|Tail]) -> 
    [Fun(Head) | map(Fun, Tail)]. 

X = map(fun (X) -> X div 2 end, 
        [2, 4, 8, 16]).
 map sier at om det andre argumentet er en tom liste så er resultatet også en tom liste. Om listen ikke er tom er resultatet en ny liste som består av resultatet av å evaluere Fun av det første elementet pluss map av alle de andre elementene. map kaller seg selv rekursivt til den har spist opp hele listen.

X er listen [1, 2, 4, 8].

map er en høyereordens funksjon som utfører en gitt funksjon på elementene i en sekvens. Den er også kjent som apply-to-all, mapcar, select, apply_map og collect.

Hva er X?

filter(_, [])    -> []; 
filter(F, [H|T]) -> 
    case F(H) of 
        true -> [H | filter(F, T)]; 
        false -> filter(F, T) 
    end. 

IsEven = fun (X) -> X rem 2 == 0 end. 
X = filter(IsEven, [1,2,3,4,5,6]).
 X er listen [2, 4, 6].

La oss se på en versjon som bruker halerekursjon. Hva blir X nå?

filter(F, L) -> filter(F, L, []). 

filter(_, [], Acc)    -> Acc; 
filter(F, [H|T], Acc) -> 
    case F(H) of
        true -> filter(F, T, [H|Acc]); 
        false -> filter(F, T, Acc) 
    end. 

IsEven = fun (X) -> X rem 2 == 0 end, 
X = filter(IsEven, [1,2,3,4,5,6]).
 X er listen [6, 4, 2]. Listen er i revers i forhold til den første varianten på grunn av måten vi bygger opp Acc på. Det er mest effektivt å plukke elementer fra og legge elementer til hodet av en liste, og derfor blir det sånn. Men Erlang kan raskt reversere en liste, så dette er egentlig ikke noe problem.

Vi har sett på et par veldig grunnleggende funksjoner i funksjonell programmering - map og filter. Det naturlige neste steget kalles fold (også kjent som reduce, aggregate, accumulate, compress og inject):

fold(Acc, _, [])    -> Acc; 
fold(Acc, F, [H|T]) -> fold(F(H, Acc), F, T).
 Hmm, ok?!

Fold komprimerer en sekvens til én verdi. Hva er verdien av dette uttrykket?

fold(0, 
     fun (X, Acc) -> X + Acc end, 
     [1, 2, 3, 4]).
 Heltallet 10, som er summen av tallene i listen.

Hva er et bedre navn på funksjonen foo?

foo(F, List) -> 
    G = fun (X, Acc) -> 
            case F(X) of 
                true -> [X|Acc]; 
                false -> Acc 
            end 
        end, 
    fold([], G, List).
 Et bedre navn på foo ville vært filter. foo gjør akkurat samme jobben som filter-funksjonen du så tidligere, men denne gangen ved hjelp av fold.

Hva er et bedre navn på funksjonen bar?

bar(F, List) -> 
    G = fun (X, Acc) -> [F(X)|Acc] end, 
    fold([], G, List).
 map.

La oss kombinere filter, map og fold for å analysere et datasett. Hvilken verdi er X bundet til etter å ha evaluert følgende?

is_man({man, _, _}) -> true; 
is_man(_) -> false. 

L = [{man,   "Jan",     23}, 
     {woman, "Kari",    25}, 
     {man,   "Rune",    30}, 
     {man,   "Vidar",   44}, 
     {woman, "Cecilie", 35}], 
L2 = filter(fun is_man/1, L), 
L3 = map(fun ({_, _, Age}) -> Age end, L2), 
X = fold(0, fun (X, Acc) -> X + Acc end, L3).
L er en liste med persondata. L2 er alle mennene. L3 er en liste med aldrene til mennene. Og X er summen av alderen til alle mennene - som er 97.

En aller siste fold: Gitt listen L ovenfor, hva er verdien av dette uttrykket?

fold({men, 0, women, 0}, 
     fun (P, Acc) -> 
         {men, M, women, W} = Acc, 
         case P of 
             {man, _, Age} -> 
                 {men, M + Age, women, W};
             {woman, _, Age} -> 
                 {men, M, women, W + Age} 
         end 
     end, 
     L).
 4-tuplet {men, 97, women, 60},

Lærte du noe?

 Tja, jeg tror jeg begynner å se hvor elegant det er å jobbe med lister med funksjoner som map, filter og fold. Og kanskje jeg skal ta en nærmere titt på Erlang.., pattern matching virker spesielt kult :)
comments powered by Disqus