Map (hogere-ordefunctie)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/1rightarrow_blue.svg/15px-1rightarrow_blue.svg.png)
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
bewerkenStel dat we een lijst van getallen hebben: . Als we elk element van deze lijst willen verdubbelen, definiëren we eerst een functie die een getal verdubbelt: . Vervolgens kunnen we map oproepen met onze lijst en onze functie: . Dit geeft het gewenste resultaat: . De map-functie heeft dus onze functie toegepast op elk element van onze lijst .
Visueel voorbeeld
bewerkenHieronder staat een voorbeeld voor het optellen van 1 bij elk getal in een lijst:
Definitie
bewerkenDe 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:
- Definieert het type van de map-functie (zie hieronder)
- Behandelt het basisgeval: het toepassen van de functie
f
op een lege lijst geeft als resultaat een lege lijst. - Werkt als volgt: het tweede argument, de lijst, wordt gesplitst in het eerste element
x
en de restxs
. Als resultaat wordt een nieuwe lijst gegeven, met als eerste elementf
toegepast opx
en als rest het resultaat van een recursieve oproep, d.w.z. het toepassen vanf
op de rest van de lijstxs
.
De map-functie kan ook geschreven worden met behulp van de hogere-ordefuncties fold
en functiecompositie:
map f = foldr ((:).f) []
Typesysteem
bewerkenHet 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
bewerkenHet 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
bewerkenVoor de functie map geldt dat , waarbij voor de functiecompositie staat (gelezen als na ), voor alle functies en . Het mappen van een functie en daarna het mappen van een functie is gelijk aan het mappen van de samengestelde functie . In beide gevallen wordt op elk element van de lijst eerst de functie toegepast en daarna de functie .
Stel bijvoorbeeld en en we willen uitvoeren. Doordat we kunnen steunen op de eigenschappen van de functiecompositie, kunnen we ook niets doen, aangezien de samengestelde functie de identiteitsfunctie is.
Map in programmeertalen
bewerkenCommon 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.