Map (hogere-ordefunctie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In veel programmeertalen is map een hogere-ordefunctie die een functie toepast op elk element van een lijst. 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.

Definitie[bewerken]

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

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

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

Voorbeelden[bewerken]

Het is bijvoorbeeld mogelijk een functie f te definiëren en deze toe te passen op elk element in een lijst:

f x = x + 3
map f [1,2,3] (dit geeft [4,5,6])

Andere voorbeelden:

map head [[1, 2], [3, 4], [5, 6]] (dit geeft [1, 3, 5])

Typesysteem[bewerken]

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. Uiteindelijk wordt een lijst van b-elementen opgeleverd. 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.

Map in bepaalde programmeertalen[bewerken]

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 type klasse. Voor elke instantie van de Functor type klasse moet de fmap functie voldoen aan de volgende voorwaarden:

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

Onder andere Python, PHP en Perl bevatten een ingebouwde functie map.

Optimalisatie[bewerken]

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 functiecompositie staat, 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.