tirsdag 6. desember 2011 F# Julekalender Polyglot
Har du hørt at programmer som er kodet etter den funksjonelle paradigmen ofte er kortere og er enklere å teste, og gjør det mye enklere å utnytte prosessorkraften på maskinen? Spennende, men hvilket språk skal man bruke da? F# er ett alternativ.
På Universitetet i Edinburg utviklet man tidlig på 70-tallet et programmeringsspråk man kalte ML. Språket støttet både imperativ og funksjonell programmering. F# er en moderne implementasjon av ML, først utviklet av Don Syme ved Microsoft Research for 10 år siden. Nå er språket i versjon 2, mens versjon 3 er i preview. Det er tilgjengelig i Visual Studio, og distribueres som et fullverdig språk på .NET-plattformen.
F# er et sterkt typet språk. Det her såkalte immutable types – data som ikke kan endres – som brukes til funksjonell programmering, men også mutable types som kan brukes til objektorientering. I F# kan man benytte alle biblotekene en som .NET-utvikler er vandt til å ha tilgang til, men måten du koder og tenker på er ganske anderledes.
Funksjonell programmering (FP) er når man lager programmer som er som evaluering av matematiske funksjoner, og man forsøker å unngå tilstand og data som kan endres på underveis i programmet. Man legger altså vekt på å evaluere funksjoner, og mindre vekt på endring av variabler.
FP har sine røtter i lambda calculus, en formell beskrivelse av funksjonsdefinisjoner, evaluering av funksjoner, og rekursjon. Et par relaterte blogposter som utdyper betydningen av FP er programmeringsparadigmer – ulike måter å tenke på og hemmeligheten bak funksjonell programmering avslørt.
Jeg vil nå vise en hel rekke ulike løsninger på Euler problem nummer 1 implementert i F#. Selv om jeg har blogget litt om F# tidligere så er jeg helt nybegynner, og her er den første løsningen jeg kom opp med gjennom å google meg frem til funksjoner jeg kunne bruke:
10 let Euler1a = 11 Seq.unfold (fun x -> Some(x, x+1)) 0 12 |> Seq.takeWhile (fun x -> x < 1000) 13 |> Seq.filter (fun x -> x % 3 = 0 || x % 5 = 0) 14 |> Seq.fold (fun x acc -> x + acc) 0 15 |> System.Console.WriteLine
Seq.unfold genererer en uendelig sekvens med tall. Jeg sender så sekvensen gjennom en rekke funksjoner for å begrense, filtrere, summere, og til slutt skrive ut resultatet.
Jeg fant derimot raskt ut at jeg kunne forenkle løsningen. Sekvenser kan lages enklere, og jeg behøver ikke bruke fold for å summere tall.
17 let Euler1b = 18 seq { 0 .. 999 } 19 |> Seq.filter(fun x -> x % 3 = 0 || x % 5 = 0) 20 |> Seq.sum 21 |> System.Console.WriteLine
Faktisk viste det seg også at Seq-bibloteket inneholdt en funksjon som jeg kunne bruke til å filtrere og summere i én operasjon, og da så det til slutt slik ut:
23 let Euler1c = 24 seq { 0..999 } 25 |> Seq.sumBy (fun x -> if x%3=0 || x%5=0 then x else 0) 26 |> System.Console.WriteLine
Men F# egner seg også til å implementere sett-baserte løsninger som dem jeg beskrev i denne bloggposten. I løsningen nedenfor oppretter jeg to sett med multipler av 3 og multipler av 5. Disse finner jeg unionen av, endrer settet til en sekvens, summerer og skriver ut.
28 let Euler1d = 29 (set {0..3..999}, set {0..5..999}) 30 ||> Set.union 31 |> Set.toSeq 32 |> Seq.sum 33 |> System.Console.WriteLine
Jeg forsøkte også det andre alternativet av sett-løsninger hvor jeg legger sammen summen av alle 3-multipler og 5-multipler, og trekker fra summer av alle 15-multipler:
35 let Euler1e = 36 (seq {0..3..999} |> Seq.sum) + 37 (seq {0..5..999} |> Seq.sum) - 38 (seq {0..3*5..999} |> Seq.sum) 39 |> System.Console.WriteLine
Den neste løsningen er en rekursiv funksjon som bygger opp en sum basert på pattern matching. Løsningen er inspirert av bowlingkata-algoritmen jeg viste i blogposten Likheter mellom F# og Erlang. Jeg bruker et såkalt match expression med tre ulike muligheter: Hvis n er 1000 skal sum inneholdet svaret, og det returneres. Hvis ikke sjekker jeg om n er delelig på 3 eller 5, og hvis så er tilfelle så legger jeg n til sum, øker n med 1, og kaller funksjonen rekursivt. Hvis tallet ikke er delelig på 3 eller 5 skal det ikke inkluderes, og jeg kjører videre uten å endre sum.
43 let rec Euler1f n sum = 44 match n with 45 | 1000 -> sum 46 | _ when n % 3 = 0 || n % 5 = 0 -> Euler1f (n+1) (sum+n) 47 | _ -> Euler1f (n+1) sum 48 49 System.Console.WriteLine (Euler1f 0 0)
Til slutt har jeg laget en forbedret pattern matching ved å bruke et såkalt active pattern. Denne teknikken brukes for å partisjonere data – i dette tilfelle splitte alle tenkelige tall i to grupper basert på om de er multipler av 3 eller 5 eller om de ikke er det. Selve match-uttrykket blir dermed renere.
56 let (|Multiple|NotMultiple|) n = 57 if n % 3 = 0 || n % 5 = 0 then Multiple else NotMultiple 58 59 let rec Euler1g n sum = 60 match n with 61 | 1000 -> sum 62 | Multiple -> Euler1g (n+1) (sum+n) 63 | NotMultiple -> Euler1g (n+1) sum 64 65 System.Console.WriteLine (Euler1g 0 0)
Jeg vil ikke at du absolutt skal lære deg F#, men jeg mener det er viktig at du lærer deg minst ett språk med fokus på funksjonell programmering. Og om du allerede har .NET-erfaring er F# da et naturlig valg. Er du Java-utvikler er det kanskje mer sansynlig at du vil gå for å lære deg Scala eller Clojure (som forresten begge finnes for .NET også).
Men nå snakker vi altså om F#, som er et modent språk, supportert av Microsoft, og som egner seg godt til praktisk utvikling av forretningsprogramvare. Visual Studio-støtten, og F#-støtten man finner i andre verktøy som f.eks. LinqPad, er også et stort pluss for dem som allerede bruker disse.
Jeg har derimot ikke inntrykk av at F# har fått den utbredelsen man kunne forvente. Det kan være flere grunner til dette, men ett av dem er nok at C# og VB.NET – de mest utbredte språkene på .NET – også har fått brukbar støtte for funksjonell programmering vha. Linq og lambda-uttrykk. F# har derimot endel egenskaper man ikke finner i disse andre språkene, og det er absolutt verdifullt å studere disse.
Har du Visual Studio 2010 har du allerede F# på maskinen, og det er bare å sette igang. På MSDN finner du all informasjon du behøver om språket og API'ene, samt flere guider, tutorials og videoer. På Visual F# Developer Center finner du siste nytt og community-relatert informasjon. Lykke til!