Map, filter, reduce

En av de viktige tingene jeg har lært meg om programmering i de siste par årene, er at for-løkker er utdaterte og stygge. I dag er høyere ordens funksjoner og lambda-funksjoner greia. Dette er eksempler på begreper som gjennomsyrer funksjonell programmering. Her skal jeg forklare de tre viktigste funksjonelle funksjonene.

La oss starte med et enkelt problem og løse det på den "gammeldagse" måten. Oppgaven er å summere alle de odde tallene fra 1 og opp til et tall n. I Javascript kan dette gjøres slik:

const sumNumbers = function(upperLimit) {
  sum = 0;
  for (let i = 0; i <= upperLimit; i++) {
    if (i % 2 == 1) {
      sum += i;
    }
  }
  return sum;
}

Det første vi legger merke til er at det er ganske mye kode. For det andre er ikke koden veldig selvforklarende. Vi har en midlertidlig variabel i, og vi setter sum lik 0 i begynnelsen, noe som ikke er sant. Ved hjelp av map, filter og reduce kan denne funksjonen gjøres mye mer lesbar og semantisk korrekt.

Vi starte med å forklare map. Kort sagt: gitt en liste med elementer av en viss type og en funksjon f:A \to B (fra type A til type B), kan funksjonen f anvendes på hvert element i listen:
(x_1,\ldots,x_n) \mapsto (f(x_1), \ldots,f(x_n)).

Vi tar et eksempel (i Clojure, for å være morsomme). Vi starter med listen over tallene 1 til 5, og ønsker å gange alle med to:

(map (fn [x] (* x 2))
     (list 1 2 3 4 5)
)

Notasjonen er enkel. Først definerer vi "gang med to"-funksjonen, deretter definerer vi listen vi starter med. Resultatet er listen [2,4,6,8,10]. Vi kan gjøre det samme i Javascript:

[1,2,3,4,5].map( (x) => 2*x)
// [ 2, 4, 6, 8, 10 ]

I begge eksemplene over matet vi map med anonyme funksjoner. Det er fullt mulig å gi dem mer kompliserte funksjoner. Anta vi for eksempel har lyst å sjekke om tall er primtall. Da kan vi gjøre følgende (Javascript):

const isPrime = function(n) {
  if (n == 1) return false;
  if (n == 2) return true;

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
};

[1,2,3,4,5,6,7,8,9,10].map(isPrime)
// [ false, true, true, false, true, false, true, false, false, false ]

(her startet vi med en funksjon \mathrm{isPrime}:\mathbb N_+ \to \mathrm{Bool}, og brukte funktoren map, og fikk en funksjon \mathrm{isPrime}:\mathbb N_+^{10} \to \mathrm{Bool}^{10})

Okay, det får være nok om map. La oss forklare filter. Filter gjør det det høres ut som: den filtrerer en liste, gitt en boolsk funksjon. Vi tar et eksempel i Javascript og et i Clojure:

[1,2,3,4,5,6,7,8,9,10].filter( (x) => x % 2 == 0)
// [ 2, 4, 6, 8, 10 ]
(filter
  (fn [x] (= (mod x 2) 0))
  (list 1 2 3 4 5 6 7 8 9 10)
)
;; (2 4 6 8 10)

I begge eksemplene starter vi med listen over tallene 1 til og med 10, og så tar vi kun vare på partallene.

Vi kan dra primtalleksemplet litt lenger:

[1,2,3,4,5,6,7,8,9,10].filter(isPrime)
//  [ 2, 3, 5, 7 ]

På dette tidspunktet ville det vært kjekt med en funksjon tilsvarende Pythons range, som gitt start- og slutt-verdier gir en liste over alle tallene i dette intervallet. Dessverre har ikke Javascript noen innebygd funksjon som gjør dette, men vi kan lage en (litt hacky):

const range = function(start, end) {
  return (new Array(end-start+1))
      .fill(null)
      .map((_,idx) => idx+start)
}

Eksempel:

range(1,10)
// [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Nå er det på tide å introdusere reduce. Den er hakket mer abstrakt enn de to andre. For å bruke reduce, trenger vi en startverdi, og en akkumulatorfunksjon. Det klassiske eksemplet er å summere elementene i en liste: anta du har lyst å summere tallene 1 til 10. Måten du gjør det på er å starte med 0 (acc = 0). Så legger du til første elementet i lista (acc += 1), så legger du til andre elementet i lista (acc+= 2), og så videre. Når du er ferdig med å akkumulere, har du svaret.

I Javascript skrives dette slik:

range(1,10).reduce( (x,y) => x + y, 0)
// 55

I Clojure:

(reduce + (range 1 11))
;; 55

Reduce er et veldig kraftig verktøy når man gjenkjenner når det kan brukes. Anta for eksempel at du har flere lister som du har lyst å lime sammen til én lang liste. Da kan vi skrive slik:

[[1,2],[4,5],[6,7]].reduce( (a1,a2) =>  a1.concat(a2), [])
// [ 1, 2, 4, 5, 6, 7 ]

Eller anta at du vil finne maks-verdien i en liste:

[1,2,3,4,2.5,0,-5].reduce( (x,y) => Math.max(x,y))
// 4

(om man ikke oppgir en initialverdi i Javascript, vil det første elementet i listen brukes som initialverdi)

Vi er nå klare til å summere alle de odde tallene:

const sumNumbers = function(upperLimit) {
  return range(1,upperLimit)
    .filter( (x) => x % 2 == 1)
    .reduce( (x,y) => x + y, 0)
}

Se der! Funksjonen er flere linjer kortere, og det er ingen variabler som endrer verdi underveis. Vi starter med listen over alle tall fra 1 til den øvre grensen, så fjerner vi alle partall, og så summerer vi alle tallene. Svaret returnerer vi.

Og i Clojure:

(defn sumNumbers [n]
  (reduce +
        (filter
          (fn [x] (= (mod x 2) 1 ))
          (range 1 (+ n 1))
        )
  )
)

Til slutt: som en bonus kan vi skrive om isPrime-funksjonen i litt mer funksjonell stil:

const isPrime = function(n) {
  if (n == 1) return false;
  if (n == 2) return true;
  return range(2,Math.floor(Math.sqrt(n))+1)
    .every( divisor => n % divisor != 0)
}

Ingen for-løkker!

Legg igjen en kommentar