Map (hogere-ordefunctie)

Voor de gelijknamige datastructuur, zie associatieve array.

In veel programmeertalen is map een hogere-ordefunctie die een gegeven functie toepast op elk element van een collectie, bijvoorbeeld op een lijst, waarbij het resultaat dan een even grote lijst van resultaten is. Deze functie komt met name voor in functionele programmeertalen maar ook andere talen (zoals high-level procedurele talen) kennen deze functie of maken het mogelijk deze te definiëren.

Voorbeeld

Stel dat we een lijst van getallen hebben: $[1,2,3,4]$. Als we elk element van deze lijst willen verdubbelen, definiëren we eerst een functie $f$ die een getal verdubbelt: $f(x)=x*2$. Vervolgens kunnen we map oproepen met onze lijst en onze functie: ${\text{map}}(f,[1,2,3,4])$. Dit geeft het gewenste resultaat: $[2,4,6,8]$. De map-functie heeft dus onze functie $f$ toegepast op elk element van onze lijst $a$.

Visueel voorbeeld

Hieronder staat een voorbeeld voor het optellen van 1 bij elk getal in een lijst:

Definitie

De map-functie kan als volgt gedefinieerd worden (in Haskell):

map :: (a -> b) -> [a] -> [b]
map f []      = []
map f (x:xs)  = f x : map f xs

Deze definitie werkt als volgt:

1. Definieert het type van de map-functie (zie hieronder)
2. Behandelt het basisgeval: het toepassen van de functie f op een lege lijst geeft als resultaat een lege lijst.
3. Werkt als volgt: het tweede argument, de lijst, wordt gesplitst in het eerste element x en de rest xs. Als resultaat wordt een nieuwe lijst gegeven, met als eerste element f toegepast op x en als rest het resultaat van een recursieve oproep, d.w.z. het toepassen van f op de rest van de lijst xs.

De map-functie kan ook geschreven worden met behulp van de hogere-ordefuncties fold en functiecompositie:

map f = foldr ((:).f) []

Typesysteem

Het type van map is (a -> b) -> [a] -> [b] (in de notatie van de programmeertaal Haskell). Dit wordt als volgt gelezen: het eerste argument van de functie map is een functie van een a naar een b, het tweede argument is een lijst van a-elementen. Het uiteindelijke resultaat is een lijst van b-elementen. Stel dat we een lijst van getallen hebben en de functie g verandert elk getal in een string, dan geldt dat de functie het type Int -> String heeft. Het type van de expressie map g wordt dan [Int] -> [String] want map g kan toegepast worden op een lijst van getallen om een lijst van strings op te leveren.

Generalisatie

Het gebruik van map beperkt zich niet tot lijsten; het kan worden toegepast op alle functors. Als voorbeeld kunnen we map ook definiëren zodat het werkt op een boom (opnieuw in Haskell):

data Boom a = Blad a | Top (Boom a) (Boom a)

Deze definieert de datastructuur van een eenvoudige binaire boom: een boom is ofwel een blad, ofwel een top met twee kinderen, die op hun beurt een boom zijn. Vervolgens kunnen we map definiëren:

map f (Blad x)    = Blad (f x)
map f (Top l r)   = Top (map f l) (map f r)

Toegepast op een voorbeeld wordt dit (met de functie f van hierboven):

>>> map f (Top (Top (Blad 1) (Blad 2)) (Top (Blad 3) (Blad 4)))
Top (Top (Blad 2) (Blad 4)) (Top (Blad 6) (Blad 8))

(Merk op dat in Haskell zelf niet op deze manier geschiedt. Men gebruikt het concept van de Functor-typeklasse, zie hieronder.)

Optimalisatie

Voor de functie map geldt dat $\left({\text{map}}\,f\right)\circ \left({\text{map}}\,g\right)={\text{map}}\,\left(f\circ g\right)$, waarbij $\circ$ voor de functiecompositie staat (gelezen als $f$ na $g$), voor alle functies $f$ en $g$. Het mappen van een functie $g$ en daarna het mappen van een functie $f$ is gelijk aan het mappen van de samengestelde functie $f\circ g$. In beide gevallen wordt op elk element van de lijst eerst de functie $g$ toegepast en daarna de functie $f$.

Stel bijvoorbeeld $f(x)=x*2$ en $g(x)=x/2$ en we willen $\left({\text{map}}\,f\right)\circ \left({\text{map}}\,g\right)$ uitvoeren. Doordat we kunnen steunen op de eigenschappen van de functiecompositie, kunnen we ook niets doen, aangezien de samengestelde functie $(f\circ g)(x)=(x/2)*2=x$ de identiteitsfunctie is.

Map in programmeertalen

Common Lisp bevat een redelijk aantal functies vergelijkbaar met map; de functie die overeenkomt met de hier beschreven functie is mapcar.

In de Standard Template Library van C++ heet het transform.

In Haskell is map gegeneraliseerd naar een polymorfe functie fmap die een onderdeel is van de Functor-typeklasse. Voor elke instantie van de Functor type klasse moet de fmap functie voldoen aan de volgende voorwaarden (de identiteit en de compositie):

fmap id = id
fmap (f . g) = fmap f . fmap g

Onder andere Python, PHP en Perl bevatten een ingebouwde functie map; daarnaast hebben nog heel wat andere talen ook gelijkaardige functies.

Zie ook

• Filter
• Fold
• Functor
• Lijstcomprehensie
• Hogere-ordefunctie
• Functioneel programmeren