torsdag 14. februar 2013 F# Polyglot Lister Rekursjon
I kveld har jeg lekt meg litt med F#. Det er ikke et språk jeg kan så veldig godt, så da er det greit å øve på helt basic ting. Noe jeg ofte gjør er å implementere grunnleggende funksjoner som jobber på lister – som map, filter og fold. Du husker kanskje at jeg gjorde det samme i posten Den Lille Erlanger?
Og nå vil jeg dele hva jeg gjorde..
I stedet for å bruke F#'s innebygde liste-type så ville jeg denne gangen lage min egen. Dette er altså ingen instruksjon i hvordan man bør bruke F#, men jeg lærte endel av å gjøre denne øvelsen.
En lenket liste består av det vi kaller for cons-celler. Jeg endte opp med å bruke en såkalt discriminated union til å definere en cons-celle:
type Cell<'T> =
| Cons of 'T * Cell<'T>
| Nil
som jeg så kan bygge lister med:
let aList = Cons("one", Cons("two", Cons("three", Nil)))
En Cell er altså en generisk type som kan bestå av enten en Cons eller Nil. En Cons består av en tuplet av en verdi av den generiske typen pluss en ny Cons (som kan være Nil). Nil er rett og slett en tom liste, og brukes som du ser over til å terminere listen. Dette er Computer Science 101.
Cons-celler er hentet fra programmeringsspråket Lisp, og det slo meg at ved å lage en liten funksjon som jeg kaller cons kan jeg få konstruksjonen av lister til å se ut som om det var Lispkode jeg skrev. Her er funksjonen:
let cons a b = Cons(a, b)
Og når jeg bruker den for å lage en liste med ordene "one", "two" og "three" ser det slik ut:
let aList' = (cons "one" (cons "two" (cons "three" Nil)))
Nå er det på tide å definere funksjonen map for denne listetypen jeg har laget. Den er rekursiv (legg merke til nøkkelordet rec) og den bruker pattern matching til å skille mellom en Cons og Nil. For hvert kall til map blir det laget en ny cons-celle.
let rec map f lst =
match lst with
| Cons(head, tail) -> Cons(f head, map f tail)
| Nil -> Nil
Nå kan jeg for eksempel bruke map til å transformere alle elementene i listen min til store bokstaver:
let aListUppercase = map (fun (s: string) -> s.ToUpper()) aList
PS: Her blir det bonuspoeng til dem som la merke til at map-funksjonen min ikke brukte hale-rekursjon. Mer om det senere...
Ved å lage en funksjon som teller antall elementer i en cons-basert liste får jeg vist frem hvordan man kan lage og bruke indre funksjoner i en funksjon.
let length lst =
let rec length' lst acc =
match lst with
| Cons(head, tail) -> length' tail acc + 1
| Nil -> acc
length' lst 0
For å finne lengden på en liste gjør jeg da slik:
let listLength = length aList
Fold (også kjent som reduce, aggregate, accumulate, inject, compress m.m.) er en grunnleggende liste-funksjon. Den tar som argumenter en funksjon (f), en startverdi (acc) og en liste (lst). f kalles på acc og hvert element fra listen i tur og orden, og resultatet tas hele tiden vare på i en oppdatert versjon av acc.
let rec fold f acc lst =
match lst with
| Cons(head, tail) -> fold f (f acc head) tail
| Nil -> acc
Denne versjonen av fold kalles ofte foldl, eller left fold. Her er en illustrasjon av hva den gjør:
: f
/ \ / \
a : foldl f acc f c
/ \ -------------> / \
b : f b
/ \ / \
c [] acc a
Ett problem med fold er at om den skal brukes til å produsere en ny liste (for eksempel om den brukes som grunnlag for map), så vil listen være reversert i forhold til input-listen.
Det går også an å lage en foldr – right fold – som ikke har dette revers-problemet:
let rec foldr f acc lst =
match lst with
| Cons(head, tail) -> f (foldr f acc tail) head
| Nil -> acc
Den er kanskje litt enklere å forså i forhold til hva den produserer:
: f
/ \ / \
a : foldr f acc a f
/ \ -------------> / \
b : b f
/ \ / \
c [] c acc
Foldr har derimot et annet problem – den bruker ikke hale-rekursjon. Det rekursive kaller er nemlig ikke det siste som skjer i hvert kall, og det gjør at den raskt kan spise opp stacken om man behandler lange lister.
Men uansett, la oss bruke fold til noe fornuftig. Hva med å summere en liste? Her lager jeg først en liste med tall, deretter en sum-funksjon basert på fold, og finner til slutt summen som jeg tar vare på i sumNumbers:
let numbers = (cons 1 (cons 2 (cons 3 Nil))) let sum = fold (fun x y -> x + y) 0 let sumNumbers = sum numbers
For litt siden lagde jeg en funksjon for å telle antall elementer i en liste. Den kan jeg lage på nytt nå som jeg har fold i verktøybeltet mitt:
let length2 = fold (fun acc _ -> acc + 1) 0
Det neste jeg gjorde var å lage en funksjon for å reversere en liste. Det kan være nyttig å ha, spesielt om man skal bruke den halerekursive fold-varianten mye. Som i den første length-funksjonen bruker jeg en indre funksjon, og pattern matchingen har nå blitt bittelitt mere avansert:
let reverse lst =
let rec reverse' lst acc =
match lst with
| Cons(head, Nil) -> cons head acc
| Cons(head, tail) -> reverse' tail <| cons head acc
| Nil -> Nil
reverse' lst Nil
Logikken her kan være litt vrien å skjønne, så forsøk verifiser for deg selv hva som foregår. Jeg plukker ett og ett element fra listen, og bygger opp en ny liste (acc) av disse. Når jeg sier reverse' tail <| cons head acc betyr det at resultatet av cons head acc sendes inn som andre argument til reverse'.
Funksjonen jeg sålangt mangler er den vi som regel kaller filter. Den filtrerer ut elementer fra en liste basert på resultatet av en predikatfunksjon (en funksjon som returnerer true eller false). Jeg kan implementere funksjonen slik som dette:
let filter p lst =
let f acc x =
if p x then cons x acc
else acc
foldr f Nil lst
Men her har jeg brukt foldr, og det er jo ikke bra! La oss bruke fold i stedet, og reversere listen igjen til slutt (slik at den opprinnelige rekkefølgen beholdes):
let filter2 p lst =
let f acc x =
if p x then cons x acc
else acc
fold f Nil lst |> reverse
Nå kan jeg lage et lite predikat som sjekker om et tall er et oddetall, og filtrere numrene mine med den:
let odd x = x % 2 <> 0 let oddNumbers = filter2 odd numbers
Jammen ble det nok en blogpost om grunnleggende, funksjonelle liste-teknikker. Men det er viktige ting å ha kontroll på, og det gir meg alltid noe å bruke disse øvelsene når jeg skal lære meg nye språk – eller bare friske opp igjen gammel kunnskap. Jeg oppfordrer deg derfor til å gjøre det samme.
Og når du har god kontroll på lenkede lister kan du gå videre med trær, og deretter grafer (eller nettverk om du vil kalle dem det). Lister har du nesten alltid god støtte for i språk du bruker, men operasjoner på trær og grafer må man ofte lage på egen hånd. Kanskje jeg gjør det selv i morgen kveld, og at det da kommer en ny post snart om det. Den som følger med får se!