fredag 15. februar 2013 F# Polyglot Trær
I forrige post lekte jeg med med cons-baserte lister. Nå har jeg gått over til tre-strukturer. Som utvikler får man veldig ofte bruk for trær av ett eller annet slag, så dette er noe det kan være greit å øve litt på av og til – og spesielt når man jobber med et nytt programmeringsspråk.
Husker du cons-cellen fra forrige bloggpost? I Lisp bruker man rett som det er cons-celler til å lage trær med også. Det jeg skal gjøre nå ligner litt, men jeg skal gjøre det litt enklere.
Igjen bruker jeg en discriminated union til å definerer en generisk type. Denne gangen kaller jeg den Tree. Tree er en union av to muligheter: Enten er det en Branch (en gren altså), som har en verdi av den generiske typen samt en liste med flere tre-noder. Eller er den et Leaf (et blad), som bare har en verdi.
type Tree<'T> =
| Branch of 'T * Tree<'T> list
| Leaf of 'T
Forresten, når jeg nå snakker om lister så kommer jeg ikke til å bruke min hjemmesnekrede liste fra forrige post. Jeg skal bruke listene som finnes i F#.
En liste kan konstrueres på denne måten:
let aList = 1 :: 2 :: 3 :: 4 :: []
:: er det samme som cons-funksjonen fra sist, men den fungerer som en operator mellom to argumenter (i stedet for at begge argumentene kommer etterpå).
Jeg kan også opprette den samme listen slik som dette:
let aList = [1; 2; 3; 4]
Hadde vi brukt komma i stedet for semikolon hadde det lignet på arrays i de fleste andre språk. Til slutt kan jeg nevne at man også kan droppe semikolon-separatorene om man putter elementene i listen på hver sin linje, slik som dette:
let aList = [ 1
2
3
4 ]
Men tilbake til trær! For å lage et bittelite tre med min nye datatype kan jeg nå gjøre slik som dette:
let smallTree = Branch ("root", [ Leaf "leaf" ])
Dette definerer treet smallTree, som består av en rot-node og en blad-node. Rot-noden holder verdien "root", og bladnoden holder verdien "leaf".
La oss lage et litt større tre:
let root =
Branch
("root",
[Branch ("branch1", [Leaf "A"
Leaf "B"])
Branch ("branch2", [Leaf "C"
Branch ("D", [Leaf "E"])
Leaf "F"])])
En ASCII-representasjon av dette treet har du her:
root
/ \
branch1 branch2
/ | | \ \
A B C D F
|
E
Det jeg nå vil lage er en funksjon som kan brukes til å besøke samtlige noder i treet. Det finnes to hovedstrategier for å besøke alle nodene, og vi kaller dem dybde-først og bredde-først. Bredde-først vil besøke alle nodene på et gitt nivå før det beveger seg videre ned i treet. Dybde-først vil i stedet gå helt til bunns i en gren, for så å snu, gå tilbake, og så helt ned i neste gren. Ta en titt på Wikipedia-artiklene om depth-first search og breadth-first search om du trenger å vite mer.
Jeg velger å bruke en dybde-først strategi, og kaller funksjonen visit:
let rec visit f tree =
match tree with
| Leaf v -> f v
| Branch (v, sub) -> f v
List.iter (visit f) sub
visit er rekursiv, og tar i tillegg til treet inn en funksjon som skal kalles for hver node. Hvis noden som behandles er et Leaf, så vil den bare kalle funksjonen f med verdien av noden som argument. Hvis noden derimot er en Branch vil den først kalle f på verdien, men så iterere over alle subnodene og kalle visit på dem.
Nå kan jeg bruke visit-funksjonen på treet mitt, og sende med en funksjon som rett og slett bare skriver ut verdien i noden samt et mellomrom:
visit (printf "%s ") root
Output:
root branch1 A B branch2 C D E F
Fra dette kan du se at visit har brukt dybde-først strategien.
visit bruker ikke hva vi vil kalle en funksjonell fremgangsmåte. Den baserer seg i stedet på at funksjonen f som sendes inn har sideeffekter – i tilfellet over skrev jeg ut verdier til konsollet.
I stedet ønsker jeg en funksjon som kan traversere treet, kalle en funksjon for hver node, men ta vare på resultatene underveis. Til slutt skal den returnere "summen" fra alle nodene.
Høres dette kjent ut? Det var jo dette fold gjorde for lister! Det jeg ønsker meg er en fold-funksjon for trær. Jeg velger å kalle den treeFold:
let rec treeFold f acc tree =
match tree with
| Leaf v -> f acc v
| Branch (v, sub) -> List.fold (treeFold f) (f acc v) sub
Denne funksjonen har én parameter mer enn visit, nemlig en akkumulatorverdi (acc). Her samles resultatet fra behandlingen av alle nodene. I den siste linjen kaller jeg F# sin fold-funksjon på alle undernodene til noden jeg behandler. Funksjonen som skal kalles på hver av dem er (treeFold f). Akkumulatorverdien er resultatet av å kalle f på denne nodens verdi: (f acc v).
Henger du med?
Nå kan jeg kalle treeFold og sende inn en funksjon som ikke har noen sideeffekter:
let result = treeFold (sprintf "%s %s") "" root
Og resultatet blir at result inneholder den samme strenger som tidligere ble skrevet ut til konsollet.
Nå skal jeg gjøre noe gøy! Jeg skal bruke trestrukturen jeg har laget til å utføre regnestykker. Jeg skal rett og slett laget et såkalt expression tree. Deretter vil jeg lage en funksjon som parser treet – dvs. besøker alle nodene og kalkulerer resultatet av regnestykket det representerer.
Regnestykket jeg vil modellere er 3 * 4 + 5 * 6. Som et tre vil det se slik ut:
Plus
/ \
Multiply Multiply
/ | | \
3 4 5 6
Til dette trenger jeg en ny datatype jeg kaller CalcExpression, som i dette enkle eksempelet kan være en av tre ting: et tall, en multipliseringsoperator, eller en adderingsoperator.
type CalcExpression =
| Number of int
| Multiply
| Plus
Og så kan jeg sette opp regnestykket som et tre:
let expression =
Branch
(Plus, [Branch (Multiply, [Leaf (Number 3)
Leaf (Number 4)])
Branch (Multiply, [Leaf (Number 5)
Leaf (Number 6)])])
Da gjenstår det bare å lage parseren, som jeg har kalt calc. Den må skille mellom de ulike typene av CalcExpression, og vite hvordan den håndterer hver av dem. Finner den en addisjon må den plusse sammen alle subnodene (som kan være trær – derfor inneholder den rekursive kall til calc). Finner den en multiplikasjon må den gjøre det samme, men denne gangen gange sammen subnodene. Finner den et tall så returneres bare tallet.
let rec calc = function
| Branch (Plus, xs) -> List.fold (fun x y -> x + calc y) 0 xs
| Branch (Multiply, xs) -> List.fold (fun x y -> x * calc y) 1 xs
| Leaf (Number n) -> n
| _ -> failwith "Invalid expression tree"
Til slutt kan jeg finne svaret av regnestykket:
let answer = calc expression
.. som selvfølgelig er 42.