Mønstergjenkjenning i Erlang
- Friday, April 23rd, 2010
- Skriv en kommentar
Pattern matching, eller mønstergjenkjenning, er en svært sentral teknikk i Erlang. I de fleste programmeringsspråk betyr for eksempel “=” tilordning av en verdi til en variabel. Ikke i Erlang. Her er nemlig “=” en pattern matching-operasjon. X = Y betyr: Evaluer høyresiden (Y), og match det så mot venstresiden (X). Om X allerede har en verdi, og den ikke er lik verdien av Y, vil X = Y kaste en exception.
For å illustrere hvordan mønstergjenkjenning kan brukes til å gjøre kode svært lesbar og deklerativ vil jeg vise litt kode jeg skrev da jeg løste oppgave nummer 54 på Project Euler. Her ble jeg bedt om å analysere en rekke poker-hender. Dette er en oppgave hvor jeg vet akkurat hvordan jeg ville løst det i et objektorientert språk, men å løse det i et funksjonsbasert språk var en ny og spennende utfordring.
Sidebar: Project Euler er en webside som inneholder hundrevis av programmeringsoppgaver, med vekt på matematisk forståelse. Man kan registrere seg for å holde track på hvor mange oppgaver man har løst. Jeg synes disse oppgavene er perfekte når man skal trene seg opp i et nytt prorgammeringsspråk, og jeg anbefaler utviklere på alle erfaringsnivå å prøve seg.
Her er funksjonen min for å sjekke om en poker-hånd er et fullt hus:
61 case order(hand_to_values(Hand)) of
62 [X,X,X,Y,Y] -> {yes, [X, Y]};
63 [X,X,Y,Y,Y] -> {yes, [Y, X]};
64 _Other -> no
65 end.
Funksjonen inneholder en case-statement, og i linje 62 ser du det første forsøke på å matche et mønster. Jeg sjekker om hånden er lik mønsteret X,X,X,Y,Y – dvs. først tre like verdier og så to andre, like verdier. Det er jo nettopp dette som er et hus i poker. I linje 63 forsøker jeg å matche den andre muligheten, som er X,X,Y,Y,Y (det finnes ikke flere permutasjoner fordi jeg har sortert kortene i linje 61).
Hvis et av de to mønstrene matcher hånden, returnerer jeg et positivt svar. Hvis ingen matcher (mønsteret _Other matcher hva som helst) returnerer jeg et negativt svar (no).
Jeg skriver altså ingen imperativ kode for å søke/loope gjennom hånden og sjekke hva den inneholder. Jeg deklarerer bare mønsteret for hvordan hånden må “se ut”, og erlang finner ut resten. Her er et eksempel til, hvor jeg sjekker om hånden inneholder tre like:
68 case order(hand_to_values(Hand)) of
69 [X,X,X,_,_] -> {yes, X};
70 [_,X,X,X,_] -> {yes, X};
71 [_,_,X,X,X] -> {yes, X};
72 _Other -> no
73 end.
Mønstergjenkjenning i funksjonskall
Vi bruker også mønstergjenkjenning til å definere ulike “entrypoints” til funksjoner. Et typisk eksempel er fibonacci-funksjonen. Jeg kan definere fibonacci-følgen ved å si at de to første tallene er begge lik 1, og alle etterfølgende tall er lik summen av de to foregående tallene. I deklerative språk er det lett å lage funksjoner som genererer slike matematiske formler:
25 fib(2) -> 1;
26 fib(N) -> fib(N-1) + fib(N-2).
Funksjonen fib tar ett argument. Når metoden kalles vil Erlang bruke pattern matching til å avgjøre hvilken av de tre “versjonene” av fib som skal kalles. Er argumentet for eksempel tallet 2, vil den kalle fib(2) i linje 25, som rett og slett returnerer tallet 1.
Er argumentet i stedet tallet 3, vil linje 26 aktiveres (24 og 25 matcher ikke, men N matcher alle øvrige tall). Resultatet av fib(3) er fib(2) + fib(1). For å løse dette vil Erlang igjen kalle funksjonene i linje 24 og 25. Er utgangspunktet et større tall vil vi få en rekursjon i linje 26 – inntil vi kommer ned til fib(2) og fib(1).
Mønstergjenkjenning i enhetstester
Vi kan også bruke mønstergjenkjenning til å skrive elegante enhetstester i Erlang. Bruk av testdrevet utvikling er absolutt å anbefale når man programmerer i et nytt språk, fordi man lett gjør småfeil som det ellers kan være vanskelig å oppdage. Og sålangt har jeg bare positive erfaringer med å skrive funksjonsbaserte tester.
En enkel enhetstest av Erlangs innebygde metode for å reversere en liste kan for eksempel se slik ut:
5 [4,3,2,1] = lists:reverse([1,2,3,4]).
Her bruker jeg funksjonen lists:reverse() på en liste som består av tallene 1, 2, 3 og 4. Det forventede resultatet er en liste som består av tallene 4, 3, 2 og 1. Likhetstegnet er som jeg nevnte i innledningen ingen tilordning – det er et forsøk på å matche resultatet av høyresiden mot det som står på venstresiden. Hvis høyresiden resulterer i noe annet enn listen 4, 3, 2, 1, vil likhetstegnet kaste en exception, og testen vil dermed feile.
Dette er elegant fordi det ligner mer en spesifikasjon enn en test. Funksjonen beskriver fakta, og hvis den faktiske implementasjoner fraviker denne definisjonen vil spesifikasjonen feile.
Samme teknikk brukte jeg på en funksjon for å vurdere om en poker-hånd er en straight (lagde ganske mange varianter av akkurat den funksjonen). Her plukker jeg først ut kortenes verdi i synkende rekkefølge i variablene A, B, C, D og E. Deretter forsøker jeg å påstå at A=B+1, at B=C+1 osv. Hvis dette går bra for alle kortene så vet jeg at jeg har en straight – fem kort i rekkefølge. Om så ikke er tilfelle vil det kastes en exception, som jeg catcher og returnerer i stedet “no” (“nei, det er ingen straight”).
101 [A, B, C, D, E] = order(hand_to_values(Hand)),
102 try A = B+1, B = C+1, C = D+1, D = E+1,
103 {yes, A}
104 catch
105 _:_ -> no
106 end.
Kategorier: Erlang.
RSS feed for kommentarene.
Tilbaketråkk.
April 24th, 2010 at 12:54 am
Takk for en bra post. Den løsningen på fullt hus var bare utrolig rå.
May 27th, 2010 at 11:25 am
På NNUG Bergen’s sommeravslutning i går fikk jeg et spørsmål om koden i denne blogposten, nærmere bestemt is_straigh funksjonen. @Osenius lurte på om den ikke ville klare å finne straights hvor Ess ble brukt som 1, altså [5,4,3,2,1]. Og han hadde selvfølgelig rett, dette er en bug. Jeg hadde rett og slett ikke tenkt over at dette var en gyldig straight. Min poker-fu er rusten gitt.
May 27th, 2010 at 12:04 pm
Var litt redd for å kommenterte her siden eg er ganske blank på mønstergjenkjenningen, og ikkje var 100% sikker på at det var ein bug :)
Holder på å se litt på funksjonell programmering (F#), lærer mye av å lese Erlang postene dine. Keep em comming :)
May 27th, 2010 at 12:13 pm
Tviler på det kommer så mye mer Erlang før jeg eventuelt tar det i bruk i et orntlig prosjekt. Men det skulle forundre meg mye om det ikke kommer endel F# i løpet av året, så det burde jo hjelpe på.
June 1st, 2010 at 9:34 am
[...] I denne blogposten får du se seks ulike løsninger på den aller enkleste oppgaven på Project Euler (jeg har snakket om hvordan jeg har brukt Euler til å lære meg nye programmeringsspråk her). Underveis vil du lære litt elementær Erlang-kode, se hvordan man kan parallellisere en enkel algoritme, og se hvilke ytelsesforbedringer det kan gi. Som en appetizer, her er ytelsen (forbrukt tid) på de ulike algoritmene relativt til hverandre: [...]
September 1st, 2010 at 2:05 pm
Dette er ikke relatert til verken mønstergjenkjenning eller lisp, men jeg ser at du har skrevet en del interessante ting om det i forhold til C# og tankemønster.
Linq og labmda-uttrykk er noe jeg synes er veldig greit i C# og det har ufattelig mange bruksområder for dette og jeg kom på en artig one-liner for initialisering av array i fibonacci-følgen. Du er kanskje klar over dette fra før, men jeg slenger med koden.
int[] fib = Enumerable.Range( 0, 10 ).Select( i => (i == 0 || i == 1) ? 0 : i-1 + i-2 ).ToArray();
… Som også selvfølgelig kan initialisere arrays uten stygge for-looper. :)
September 1st, 2010 at 2:33 pm
Innså til slutt at å produsere fibonacci-følgen med en slik one-liner ikke var riktig så enkelt. Men poenget mitt består! ;)
September 1st, 2010 at 3:38 pm
Ja, Linq og lambda i C# har mange bruksområder, og gir kompakt og fin kode når du venner deg til det. Men fibonaccirekken er nok ikke så enkel nei. Prøv gjerne igjen :)
September 2nd, 2010 at 1:34 pm
Enumerable.Range(1, 11).Select(i => (Math.Pow(1+Math.Sqrt(5), i) – Math.Pow(1-Math.Sqrt(5), i)) / (Math.Pow(2, i) * Math.Sqrt(5)));
Men noe sier meg at å gjøre det slik ikke var poenget (og jeg kan ikke nok C# til annet (første gang jeg bruker det nå, faktisk)). I Haskell gjøres det uansett slik:
fibs = 1:1:zipWith (+) fibs (tail fibs)
September 2nd, 2010 at 3:45 pm
Kan alltid stole på at Ameth kommer med en fungerende løsning…, som er helt umulig å forstå ;)
For dem som er interessert i å se et hav av ulike implementasjoner av fibonacci i ulike språk: http://en.literateprograms.org/Category:Fibonacci_numbers
September 3rd, 2010 at 3:25 pm
Ja, jeg innså til slutt at jeg ikke kunne bruke den “vanlige” metoden for å hente ut fibonacci-rekken, da den er rekursiv. :)
November 18th, 2011 at 4:58 pm
[...] det kan være fra F# til et språk jeg selv har jobbet endel med, nemlig Erlang. Jeg har blogget om pattern matching i Erlang tidligere, og her kan du se hvordan Christians algoritme ville sett [...]
December 7th, 2011 at 10:08 am
[...] er lazy (for de som vet hva det er), har pattern matching og list comprehensions, og et sterkt, statisk typesystem. Jeg kunne sagt mye mer, men uansett hva [...]
December 18th, 2011 at 11:44 pm
Hei, likte ikke helt din straight løsning.. Det som er kult mer erlang er jo mønster gjenkjenning og liste håndteringen. Kommer derfor med eget forslag:
is_straight_sorted([X,Y|R]) when Y == X + 1 -> is_straight_sorted([Y|R]);
is_straight_sorted([_,_|_]) -> no;
is_straight_sorted([_]) -> yes.
is_straight(Hand) -> is_straight_sorted(order(hand_to_values(Hand))).
Siden du er så flink til å forklare din kode får jeg vel forsøke å gjøre det samme.
1-3 krever en sortert liste, derav linje 4 som sorterer listen før jeg kaller is_straight_sorted.
Det er i linje 1 magien skjer. Argumentet til funksjonen i 1 matcher alle lister som har 2 eller flere elementer. Første element tilordnes i X, andre i Y og resten i R. R kan være tom liste ([]). Så har jeg lagt inn en såkalt guard som gjør at patternet kun matcher dersom Y er X + 1. Dersom dette er sant har vi sjekket første element i listen og kan fortsette å sjekke resten av listen ([Y|R]). Dersom guarden feiler vil vi matche i linje 2 og returnere no. Når vi har sjekke alle elementene og står igjen med siste element i Y og R er tom ([]) matcher hverken 1 eller 2 lenger og vi treffer 3 som da vil si at alle elementer er ok og vi returnerer yes.
Ellers skryt til bloggen din og julekalenderen!
Sjur
December 18th, 2011 at 11:51 pm
Hei Sjur! Jeg skjønner hvorfor du liker din løsning bedre. Rekursjon er gøy! Jeg synes likevel min løsning kommuniserer bittelitt bedre, men takk for eksempelet ditt. Din teknikk er uansett viktig, og hadde egnet seg mye bedre om jeg måtte ha validert en liste som var lengre.