Hoofdmenu openen

Map (hogere-ordefunctie)

hogere-ordefunctie
Zie artikel 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 functor, bv. 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.

Inhoud

VoorbeeldBewerken

Stel 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 verdubbeld:  . 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 voorbeeldBewerken

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

 

DefinitieBewerken

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

1 map :: (a -> b) -> [a] -> [b]
2 map f []      = []
3 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) []

TypesysteemBewerken

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.

GeneralisatieBewerken

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 type klasse, zie hieronder.)

OptimalisatieBewerken

Voor 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 programmeertalenBewerken

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 (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 ookBewerken