filtrer, projiser, aggreger

Det siste året har jeg knyttet intim bekjentskap til bruk av såkalte higher order functions; først da jeg virkelig tok i bruk LINQ og lambda i C# 3.0, deretter da jeg lærte meg Ruby, og til sist nå når jeg lærer meg å bruke språk som Erlang og F# i den funksjonelle paradigmen. Jeg har lært om Lambda calculus, og hva en closure er for noe – ting jeg nå mener alle utviklere burde ha et forhold til.

For å gi deg, kjære leser, et bedre innblikk i noe av dette, vil jeg snakke litt om noen av disse funksjonene av “høyere orden”. Higher order function betyr i bunn og grunn bare en funksjon som tar som innput en annen funskjon som spesifiserer en del av hva den skal utføre.

Filtrer

Filter er en av de mest vanlige, høyere orden funskjonene som brukes på lister eller andre datastrukturer. Gitt en liste og et predikat så brukes filter-funksjonen til å returnere de elementene i listen som tilfredstiller predikatet. Jeg sier “filter” fordi det er det funksjonen heter i de fleste programmeringsspråkene. I C# heter derimot filter-funksjonen for IEnumerable<T> Where, og den kan for eksempel brukes slik:

var aList = new []{1, 2, 3, 5, 8, 13, 21, 33, 54};
var evenNumbers = aList.Where(n => n % 2 == 0);
// array contains: 2, 8, 54

Filter-funksjonen for Enumerations i Ruby heter select (evt. find_all). Her er samme eksempel i Ruby:

Projiser

Den neste av de mest brukte, høyere orden funksjonene er Map. Denne funksjonen tar en liste eller lignende, samt en funksjon for å omforme (“mappe”) elementene i listen til en ny type elementer. Dette kaller vi også en projisering (projection). C#-varianten av map heter Select (og er altså ikke det samme som select i Ruby). Ønsker jeg for eksempel å konvertere listen med tall om til en liste med strenger kan jeg gjøre det slik:

var evenNumbersAsString = evenNumbers.Select(n => n.ToString());

I de fleste andre språk heter funksjonen map, men i Ruby har man også et alias som heter collect.

Aggreger

Filter og map er fine funksjoner som er anvendelige og lette å forstå og å huske på. En som ikke er fullt så mye brukt, blant utviklere innenfor den imperative paradigmen i alle fall, er Fold. For å forvirre oss fremstår også denne funksjonen med ulike navn i de ulike språkene – som for eksempel Reduce, Accumulate, Compress og Inject. Og i .NET heter den Aggregate:

Console.Write(evenNumbersAsString.Aggregate(
    "", (accumulator, next) => accumulator + next + " "));
// prints "2 8 54 "

Ser du hvordan den virker? I motsetning til de andre funksjonene som returnerer lister, så returnerer Aggregate én verdi. En verdi som er bygget opp ved å kalle det spesifiserte lambda-uttrykket for hvert element i listen. Accumulator er både output og input til lamdaen. For det første elementet vil accumulator ha verdien som ble spesifisert som den første parameteren til Aggregate, altså en tom streng. Når funksjonen kalles igjen for det andre elementet vil accumulator ha verdien som ble returnert fra den første. Og så fortsetter det til listen er tom, og accumulator returneres.

Her er nesten samme eksempel i Ruby, hvor fold heter inject (eller reduce om du ønsker å bruke det):

Har du aldri brukt en slik funksjon ser dette sikkert ganske gresk ut. Den er på kanten til å være uleselig, og hvis du jobber i et team som ikke er så godt kjent med fold/aggregate så bør du kanskje være forsiktig med å bruke den. Men jeg lover deg at om du venner deg til denne funksjonen så vil du i mange tilfeller kunne produsere mere kompakt og elegant kode.

Oppsummering i F#

Her er et oppsummerende eksempel i F#. Jeg oppretter en liste, og bruker pipelining til å sende listen gjennom filter, map (projiser) og fold (aggreger), for til slutt å skrive ut den resulterende strengen.

open System

let aList = [1; 2; 3; 5; 8; 13; 21; 33; 54]

aList |> List.filter (fun n -> n % 2 = 0)
      |> List.map    (fun n -> n.ToString())
      |> List.fold   (fun acc n -> acc + n + " ") String.Empty
      |> Console.WriteLine

Kategorier: F#, Polyglot, Ruby.
RSS feed for kommentarene. Tilbaketråkk.