Et godt sted at starte
Hvis man er nybegynder i funktionel programmering kan det måske være en ide at løse nogle af de opgaver, der er inde på http://projecteuler.net. Det er en samling af matematiske problemstillinger, der stiger i sværhedsgrad, og er et glimrende udgangspunkt hvis man savner lidt andre opgaver at træne med.
For eksempel kunne en løsning til opgave 1 (find summen af alle multipla af 3 og 5 under 1000) være:
let rec getSumOfMultiples current max sumSoFar =
match current with
| _ when current=max -> sumSoFar
| _ -> match (current%3=0)||(current%5=0) with
| true -> getSumOfMultiples (current+1) max (sumSoFar+current)
| _ -> getSumOfMultiples (current+1) max sumSoFar
getSumOfMultiples 1 1000 0
En mere quick-and-dirty version:
let rec sum list =
match list with
| [] -> 0;
| head::rest -> head+(sum rest)
[1..999]
|> List.filter (fun n -> n%3=0 || n%5=0)
|> List.map (fun x -> x)
|> sum
Ja, der mangler så indentering i ovenstående kode... hvordan gør man lige det..?
-
0 -
0
eller bare:
let som n =
List.sum (List.filter (fun x -> x % 3 = 0 || x % 5 = 0) [1..n-1])
som 1000
-
0
-
0
Det er rigtigt, Nicolai. Da jeg skrev det indlæg var jeg selv lige begyndt at lære F#, og var ikke dykket så dybt ned i List-modulet. Ud over det er min egen rekursive sum-funktion ikke tail recursive, så det er også et problem.
En løsning med forward-pipe afledt af dit forslag kunne være:
let sum = [1..999] |> List.filter (fun x -> x%3 = 0 || x%5 = 0) |> List.sum
-
0
-
0
Når nu vi kigger på optimeringer af dette eksempel så kan man bare bruge (>>) frem for (|>)
let s1 = List.filter( fun x -> x% 5=0 || x%3=0) >> List.sum;;
Den funktionelle løsning vil være brug af fold, omend jeg synes overstående er mere læselig
let s2 = List.fold_left (fun acc elem -> if elem % 5 = 0 || elem % 3 = 0 then acc + elem else acc) 0;;
-
0
-
0
@Liam
Jeg kunne godt tænke mig at kende din begrundelse for at kalde anvendelse af fold for funktionel, og hvorfor filter f.eks. ikke skulle være det :-)
-
0
-
0
@Frank
Ah, men selvfølgelig er alle højere ordens funktioner 'funktionelle løsninger', jeg betrager det bare lidt mere 'funktionelt' at løse dette problem med en iteration frem for to.
Ser at min formulering henleder til at de andre løsninger ikke er funktionelle, hvilket ikke har noget på sig.
Jeg fik følgende ide til hvad der kunne være en hurtig løsning.
List.sum [3..3..999] + List.sum [5..5..995] - List.sum [15..15..990];;
-
0
-
0
@Liam
Det var ikke fordi jeg troede du anså det for ikke-funktionelt, men nærmere fordi jeg også er interesseret i at høre folks mening om det :-) Så alt forladt.
Din sidste løsning er elegant i sin enkelthed... hvorfor har man ikke selv tænkt på den..? En gang imellem overkomplicerer vi tingene, ikke mindst når det funktionelle ikke er helt inde på rygraden :-)
-
0
-
0
Jeg ser at min seneste løsning bruger sum af følgende form:
(SUM (N=x by x to (999) ) N) hvilket kan omskrives til
x * (SUM (N=1 to (999/x) ) N)
Det er kendt at:
SUM (N=1 to n) N = n*(n+1) / 2
Og hermed får vi følgende løsning:
((999/3) * (999/3 + 1) / 2 * 3) + ((999/5) * (999/5 + 1) / 2 * 5) - ((999/15) * (999/15 + 1) / 2 * 15);;
Jeg udnytter at (/) er heltals division, eller havde Math.floor været nødvendig.
Hermed er problemmet løst optimalt mht. asymptotisk køretid.
@Frank
Jeg synes det vil være passende med en separat tråd omkring hvad man synes er funktionel programmering.
-
0
-
0
