tirsdag 6. november 2012 Design Polyglot Meninger JavaScript
Map, filter og reduce er tre funksjoner jeg er veldig glad i, uansett hvilket språk jeg programmerer. Jeg har snakket om dette mange ganger. Første gang var i artikkelen jeg kalte filtrer, projiser, aggreger. Og sist var i artikkelen Den Lille Erlanger. Og nå gjør jeg det jammen meg igjen.
For hva er poenget?
Hvorfor skal man bruke disse funksjonene?
Den viktigste grunnen er å gjøre koden enklere å lese. "Hæ?" sier du kanskje, for du synes jo det er mye enklere å lese kode med for-løkker – det er jo det du er vandt til.
Løkker har et problem; de er veldig fleksible! En løkke kan brukes på mange forskjellige måter, og til mange forskjellige ting. For å forstå hva en løkke gjør må man ikke bare lese selve løkke-deklarasjonen, men også alt inneholdet i løkken. Parametre som brukes til å avgjøre når løkken skal avsluttes kan endres når som helst i løkke-kroppen. Kodeord som continue og break kan også radikalt endre hvordan løkken oppfører seg. Og hva er resultatet av løkken? For å svare på det må man lete etter alle mutasjoner som har skjedd underveis.
Et alternativ til løkker er rekursjon, men det kan være like vanskelig å forstå rekursiv kode.
Map, filter og reduce representerer derimot tre helt konkret forskjellige måter å iterere på, tre konkrete områder man kunne brukt løkker eller rekursjon. Ved å bruke disse tar man bort litt fleksibilitet. I stedet er man tydeligere på hva hensikten med koden er.
La oss se litt nærmere på hver av funksjonene. Hvilke typer løkker er det de erstatter? Eksempelkoden er i JavaScript, slik at flest mulig kan følge med.
Map (kalt select i C#) er en funksjon som tar inn en liste, og returnerer en ny, like lang liste. Sett at vi har en funksjon "twice" som ganger et tall med 2. Om man skal "mappet" en liste med tall med denne funksjonen i en løkke vil det se slik ut:
var twice = function(x) {
return x * 2;
};
var listDoubler = function(lst) {
var result = [];
for(var i = 0; i < lst.length; i++) {
result[i] = twice(lst[i]);
}
return result;
};
Kode som dette har de fleste av oss skrevet mange ganger. Vi oppretter en liste, looper over en annen liste, og for hvert element gjør vi noe og putter resultatet i den første listen. Til slutt returnerer vi den ferdige listen.
Hver gang du ser kode som det så skal du vite at det kan gjøres mye enklere ved hjelp av map:
var listDoubler2 = function(lst) {
return map(lst, twice);
};
Som du ser er det mye enklere å lese hva som skjer i "listDoubler2". Men jeg har jukset litt, for JavaScript har i utgangspunktet ingen map-funksjon. Den må du lage selv. Men det er jo veldig enkelt, for den er nesten identisk med den første versjonen av "listDoubler":
var map = function(lst, f) {
var result = [];
for(var i = 0; i < lst.length; i++) {
result[i] = f(lst[i]);
}
return result;
};
Filter er en funksjon som tar inn en liste, og returnerer en ny som inneholder noen utvalgte element fra orginallisten. Sett at vi har funksjonen "even" som avgjør om et tall er partall. Da kan vi bruke en løkke til å filtrere ut partallene i en liste:
var even = function(x) {
return x % 2 == 0;
};
var onlyEven = function(lst) {
var result = [];
for(var i = 0; i < lst.length; i++) {
if (even(lst[i]))
result.push(lst[i]);
}
return result;
};
Med en filter-funksjon blir det igjen mye enklere:
var onlyEven2 = function(lst) {
return filter(lst, even);
};
Og som før er det enkelt å implementere en filter-funksjon:
var filter = function(lst, p) {
var result = [];
for(var i = 0; i < lst.length; i++) {
if (p(lst[i]))
result.push(lst[i]);
}
return result;
};
Reduce (også kjent som fold, inject, aggregate m.m.) er litt vanskeligere å få taket på. Den tar på en måte og "slår sammen" en liste til én verdi. Denne verdien kan være en ny liste, men trenger ikke være det. Reduce er ikke så restriktiv som map og filter, og kan dekke veldig mange itereringsbehov. Funksjonen er likevel bedre enn iterative løkker (når man blir vandt til dem), fordi den begrenser hva man kan gjøre, og derfor gir mer kode som er enklere å forstå.
Sett at vi har en fuksjon som slår sammen tekst-representasjonen av to verdier. Vi kan da lage en funksjon vi kaller "stringifyList" som slår sammen alle elementene i en liste ved hjelp av nevnte funksjon:
var stringJoin = function(a, b) {
return a + "" + b;
};
var stringifyList = function(lst) {
var result = "";
for(var i = 0; i < lst.length; i++) {
result = stringJoin(result, lst[i]);
}
return result;
};
Og så kan vi velge å bruke reduce i stedet. Da ser det sånn ut:
var stringifyList2 = function(lst) {
return reduce(lst, "", stringJoin);
};
Hver gang du itererer over en sekvens for å produsere en eller annen verdi så kan du bruke reduce. Begynner du å se etter slike steder så finner du dem over alt.
Og her er selve implementasjonen av reduce:
var reduce = function(lst, acc, f) {
for(var i = 0; i < lst.length; i++) {
acc = f(acc, lst[i]);
}
return acc;
};
"acc" er en vanlig forkortelse for accumulator.
Som antydet er reduce en mer generell funksjon enn map og filter. Og nå som vi har reduce i verktøyskrinet vårt så kan vi faktisk implementere map og filter ved hjelp av denne:
var map2 = function(lst, f) {
return reduce(lst, [], function(acc, n) {
acc.push(f(n));
return acc;
});
};
var filter2 = function(lst, p) {
return reduce(lst, [], function(acc, n) {
if(p(n))
acc.push(n);
return acc;
});
};
Har du sett noe så vakkert?! :)
Hovedpoenget med å bruke disse funksjonene er altså å skrive kode som er enklere å forstå. Den er enklere å forstå fordi man følger visse regler. Man bruke map til å "mappe", man bruker filter til å filtrere, og man bruker reduce til å redusere en liste til én ny verdi.
Men i mange programmeringsspråk kan disse reglene brytes. Man kan ikke nødvendigvis avslutte en iterasjon for tidlig eller hoppe over et element, men man kan gjøre ting som har uventede sideeffekter.
Dette er det viktig at man unngår. Skal man gjøre noe som bryter med konvensjonene så får man bruke et annet verktøy; en løkke eller rekursjon. Hvis ikke kan man ikke lenger gjøre de riktige antagelsene når man leser kode.., og man er like langt!