Indeni map() bor en reduce()

Mest af alt er jeg oprørt over de historier, som udspringer i begivenheder omkring Nets, der florerer i øjeblikket. De får lov at ligge et øjeblik, men jeg skal nok vende tilbage til dem, når der er afdækket mere. Her vil jeg koncentrere mig om noget så virkelighedsfjernt som funktionerne map og reduce. Årsagen til dette er, at jeg har haft nogle stumper til et indlæg liggende i et stykke tid og hellere må få skrevet, inden det kommer alt for langt væk.

Tidligere skrev jeg noget om lambda’er og fik en enkelt kommentar angående min brug af reduce. Jeg fik svaret lidt kortfattet på kommentaren, men i bund og grund handler det om, at reduce er en sweitzerkniv, som også kan bruges til at implementere funktionerne map, filter og remove. Hvis der ikke er en indbygget funktion, kan problemet som regel løses med reduce. Det vil jeg gerne eksemplificere ved at implementere funktionerne map, filter og remove ved at bruge reduce.

I det følgende anvender jeg groovy, da ingen af funktionerne findes i sproget (groovy har dog nogle objektorienterede ækvivalenter, som jeg også benytter som reference). Det er en fordel at læse det tidligere indlæg om lambda’er, da der i dette indlæg bruges lambda’er hele tiden. Funktionen add() defineret med en lambda, ser i groovy således ud:

add = {a, b -> a +b }

I krølleparanteser skrives først en liste af argumenter som funktionen tager, så ‘->’ efterfulgt af funktionens implementation.

Først reduce.
I mit indlæg om lamda’er, foreslog jeg en implementation af reduce, som jeg genbruger. Reduce er en funktion som tager 3 argumenter: en funktion, en samling data og en initiel værdi for resultatet. For hvert element i samlingen af data, kaldes denne funktion med elementet og resultatet af det foregående kald.

Hvis add(a,b) returnerer summen af a og b, vil

reduce(add, [1, 2, 3], 0) 

svarer til

add(add(add(0, 1), 2), 3)

Havde vi i stedet for add() haft muligheden for at bruge infix-operatoren ‘+’, ville det have set mere læseligt ud, og derved havde det nok været letter forståeligt:

0 + 1 + 2 + 3

I groovy hedder den ækvivalente metode inject(), og da groovy er objektorienteret, findes den selvfølgelig som en metode på en liste. Lad os bruge reduce til at summere tallene fra 1 til 10, begge inklusive.

#!/usr/bin/env groovy

def reduce(f, l, s) {
    for (i in l) s=f(s, i); 
    return s;
}

print("Reduce: ")
println(reduce({a,b -> a + b}, (0..10), 0))

print("Inject: ")
println((0..10).inject{a,b -> a+b})
Reduce: 55
Inject: 55

Map
Map er blot en variant af reduce. Den tager en funktion og en samling af data, men returværdien er en liste af resultater, et for hvert element i inddata. Map påtrykker altså en funktion på hvert element i samlingen af data og lægger resultaterne i en liste. Dette kan gøres ved hjælp af reduce. Den ækvivalente metode i groovy hedder collect() og er, som inject, en metode på dataobjektet. Map kan implementeres med reduce som følger:

#!/usr/bin/env groovy

def reduce(f, l, s) {
    for (i in l) s=f(s, i); 
    return s;
}

def map(f, l) {
    return reduce({a,b -> a.add(f(b)); return a} ,l , []);
}

print("Map:    ")
println(map({a -> a*a}, (0..10)))
print("Collect:")
println((0..10).collect{it*it})
Map:    [0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
Collect:[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Filter
Funktionen filter minder om map, men i stedet for at tilføje resultatet af et funktionskald, tilføjes elementet, hvis funktionen returnerer true på elementet. Funktionen skal altså teste om elementet overholder en given betingelse. Den kan f.eks. bruges til at udvælge alle lige tal i en liste. Den ækvivalente funktion i groovy hedder findAll().

#!/usr/bin/env groovy

def reduce(f, l, s) {
    for (i in l) s=f(s, i); 
    return s;
}

def filter(f, l) {
    return reduce({a,b -> if (f(b)) a.add(b); return a} ,l , []);
}

print("Filter: ")
println(filter({a-> 0==a%2}, (0..10)))
print("FindAll:")
println((0..10).findAll{0==it%2})
Filter: [0, 2, 4, 6, 8, 10]
FindAll:[0, 2, 4, 6, 8, 10]

Remove
Funktionen remove gør det modsatte af filter. Den bruges til at udvælge alle elementer der ikke oveholder en given betingelse, f.eks. alle tal, der ikke er delelig med 3. Den har ikke rigtig nogen ækvivalent i groovy, så her genbruges findAll(), men med en negeret betingelse.

#!/usr/bin/env groovy

def reduce(f, l, s) {
    for (i in l) s=f(s, i); 
    return s;
}

def remove(f, l) {
    return reduce({a,b -> if (!f(b)) a.add(b); return a} ,l , []);
}

print("Remove: ")
println(remove({a-> 0==a%3}, (0..10)))
print("FindAll:")
println((0..10).findAll{0!=it%3})
Remove: [1, 2, 4, 5, 7, 8, 10]
FindAll:[1, 2, 4, 5, 7, 8, 10]

Simple eksempler siger selvfølgelig ikke meget om styrken i reduce(), men jeg har i de sidste 2,5 år kodet clojure på fuldt tid og reduce() er blevet min bedste ven. Jeg håber at eksemplerne har givet lidt større forståelse af reduce.

Share Button
The following two tabs change content below.
Profile photo of Andreas Ryge
Med en baggrund i datalogi og psykologi, er jeg humanisten i datalogi. Arbejdsmæssigt har jeg været lidt omkring. Har været selvstændig, lavet systemer til skattemyndigheder i det meste af verden, arbejdet med musikbranchen, lavet systemer til telebranchen og er idag endt i AudienceProject. Gennem tiden har jeg prøvet en del roller, blandt andet projektleder, scrum master, afdelingsleder og arbejder i øjeblikket som Data Scientist - en lidt anden rolle, end den typiske udvikler-rolle. Har også været en del omkring i sprog og teknologier, bla C/C++, Tcl, Prolog, Java, Perl, Python, Ruby, Clojure og arbejder idag mest med Scala. Mine interesser mange, særligt machine learning, distribuerede systemer og sikkerhed. Og så interesserer jeg mig også lidt for filosofi. Forvent at skriblerierne stritter i alle retninger.

Flattr this!

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *