Carte (fonction d'ordre supérieur)

carré x = x * x

Ensuite, appelez :

>>> carte carré [ 1 , 2 , 3 , 4 , 5 ]

ce qui donne [1, 4, 9, 16, 25], démontrant que mapa parcouru toute la liste et a appliqué la fonction squareà chaque élément.

Exemple visuel

Ci-dessous, vous trouverez le détail de chaque étape du processus de conversion d'une liste d'entiers X = [0, 5, 8, 3, 2, 1]en une nouvelle liste X'selon la fonction. ${\displaystyle f(x)=x+1 <semantics><mrow><mstyle><mi>f</mi><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><mi>x</mi><mo>+</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle f(x)=x+1}</annotation></semantics></math><img src=$

application des étapes de traitement de la fonction de carte — Vue des étapes de traitement lors de l'application de la fonction map à une liste

Elle mapest fournie dans le cadre du prélude de base de Haskell (c'est-à-dire la « bibliothèque standard ») et est implémentée comme suit :

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

Généralisation

::(a->b)->[a]->[b]fmap::Functorf=>(a->b)->fa->fbFunctor

Le constructeur de type des listes []peut être défini comme une instance de la Functorclasse de type en utilisant la mapfonction de l'exemple précédent :

instance de Functor [] où fmap = map

Parmi les autres exemples, Functoron peut citer les arbres :

-- données d'un arbre binaire simple Arbre a = Feuille a | Fourche ( Arbre a ) ( Arbre a )instance Arbre de foncteurs où fmap f ( Feuille x ) = Feuille ( f x ) fmap f ( Fourche l r ) = Fourche ( fmap f l ) ( fmap f r )

La cartographie d'un arbre donne :

>>> fmap carré ( Fourchette ( Fourchette ( Feuille 1 ) ( Feuille 2 )) ( Fourchette ( Feuille 3 ) ( Feuille 4 ))) Fourchette ( Fourchette ( Feuille 1 ) ( Feuille 4 )) ( Fourchette ( Feuille 9 ) ( Feuille 16 ))

Pour chaque instance de la Functorclasse de types, fmapest contractuellement tenu de respecter les lois des foncteurs :

fmap id ≡ id -- loi d'identité fmap ( f . g ) ≡ fmap f . fmap g -- loi de composition

où .désigne la composition de fonctions en Haskell.

Cela permet notamment de définir des opérations élément par élément pour différents types de collections .

Fondements de la théorie des catégories

En théorie des catégories , un foncteur ${\displaystyle F:C ightarrow D <semantics><mrow><mstyle><mi>F</mi><mo>:</mo><mi>C</mi><mo>→</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle F:C ightarrow D}</annotation></semantics></math><img src=$ ${\displaystyle f:A ightarrow B <semantics><mrow><mstyle><mi>f</mi><mo>:</mo><mi>UN</mi><mo>→</mo><mi>B</mi></mstyle></mrow><annotation>{\displaystyle f:A ightarrow B}</annotation></semantics></math><img src=$ ${\displaystyle Ff:FA ightarrow FB <semantics><mrow><mstyle><mi>F</mi><mi>f</mi><mo>:</mo><mi>F</mi><mi>UN</mi><mo>→</mo><mi>F</mi><mi>B</mi></mstyle></mrow><annotation>{\displaystyle Ff:FA ightarrow FB}</annotation></semantics></math><img src=$ ::(a->b)->Fa->Fb

Les foncteurs peuvent également être des objets de catégories, les « morphismes » étant appelés transformations naturelles . Étant donné deux foncteurs ${\displaystyle F,G:C ightarrow D <semantics><mrow><mstyle><mi>F</mi><mo>,</mo><mi>G</mi><mo>:</mo><mi>C</mi><mo>→</mo><mi>D</mi></mstyle></mrow><annotation>{\displaystyle F,G:C ightarrow D}</annotation></semantics></math><img src=$ ${\displaystyle \eta :F ightarrow G <semantics><mrow><mstyle><mi>η</mi><mo>:</mo><mi>F</mi><mo>→</mo><mi>G</mi></mstyle></mrow><annotation>{\displaystyle \eta :F ightarrow G}</annotation></semantics></math><img src=$ ${\displaystyle \eta _{A}:FA ightarrow GA <semantics><mrow><mstyle><msub><mi>η</mi><mrow><mi>UN</mi></mrow></msub><mo>:</mo><mi>F</mi><mi>UN</mi><mo>→</mo><mi>G</mi><mi>UN</mi></mstyle></mrow><annotation>{\displaystyle \eta _{A}:FA ightarrow GA}</annotation></semantics></math><img src=$ eta::Fa->Gaaetaareverse::Lista->ListaflattenInorder::Treea->ListasortBy::(a->a->Bool)->Lista->Lista

Optimisations

Les fondements mathématiques des cartes permettent un certain nombre d' optimisations . La loi de composition garantit que les deux

(map f . map g) listet
map (f . g) list

aboutissent au même résultat ; c'est-à-dire, ${\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g) <semantics><mrow><mstyle><mi>carte</mi><mo>⁡</mo><mo>(</mo><mi>f</mi><mo>)</mo><mo>∘</mo><mi>carte</mi><mo>⁡</mo><mo>(</mo><mi>g</mi><mo>)</mo><mo>=</mo><mi>carte</mi><mo>⁡</mo><mo>(</mo><mi>f</mi><mo>∘</mo><mi>g</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)}</annotation></semantics></math><img src=$ mapnécessite de reconstruire une liste entière à partir de zéro. Par conséquent, les compilateurs tenteront de transformer la première forme en la seconde ; ce type d’optimisation est connu sous le nom de fusion de mappage et est l’ analogue fonctionnel de la fusion de boucles .

Les fonctions de mappage peuvent être et sont souvent définies en termes de pliage tel que foldr, ce qui signifie que l'on peut effectuer une fusion map-pli : foldr f z . map gest équivalent à foldr (f . g) z.

L'implémentation de `map` ci-dessus sur les listes simplement chaînées n'est pas récursive terminale ; par conséquent, elle peut accumuler de nombreux cadres sur la pile lorsqu'elle est appelée avec une grande liste. De nombreux langages proposent une fonction alternative de « map inverse », équivalente à l'inversion d'une liste mappée, mais récursive terminale. Voici une implémentation qui utilise la fonction `fold -left`.

reverseMap f = foldl ( \ ys x -> f x : ys ) []

Étant donné que l'inversion d'une liste simplement chaînée est également récursive terminale, reverse et reverse-map peuvent être composés pour effectuer une map normale de manière récursive terminale, bien que cela nécessite d'effectuer deux passages sur la liste.

Comparaison linguistique

La fonction map trouve son origine dans les langages de programmation fonctionnelle .

Le langage Lisp a introduit une fonction map appelée maplist en 1959, avec des versions légèrement différentes déjà apparues en 1958. Voici la définition originale de maplist, qui applique une fonction sur des listes de restes successives :

La fonction maplistest toujours disponible dans les Lisp plus récents comme Common Lisp , bien que des fonctions comme mapcarou les plus génériques mapseraient préférées.
L'élévation au carré des éléments d'une liste maplists'écrirait en notation S-expression comme ceci :
( maplist ( lambda ( l ) ( sqr ( voiture l ))) ' ( 1 2 3 4 5 ))

En utilisant cette fonction mapcar, l'exemple ci-dessus s'écrirait comme ceci :

( mapcar ( fonction sqr ) ' ( 1 2 3 4 5 ))

Aujourd'hui, les fonctions de mappage sont prises en charge (ou peuvent être définies) dans de nombreux langages procéduraux , orientés objet et multi-paradigmes : dans la bibliothèque standard de C++ , elles sont appelées ` map` ou ` map` , et dans la bibliothèque LINQ de C# (3.0), elles sont fournies comme méthode d'extension appelée ` map`. L'opération `map` est également fréquemment utilisée dans les langages de haut niveau tels que CFML , Perl , Python et Ruby ; elle est appelée `map` dans ces quatre langages. Un alias pour `map` est également fourni en Ruby (via Smalltalk ). Common Lisp propose une famille de fonctions similaires à `map` ; celle correspondant au comportement décrit ici est appelée `map` ( indiquant un accès via l' opération CAR ). Il existe également des langages avec des constructions syntaxiques offrant la même fonctionnalité que la fonction `map`.std::transformstd::ranges::transformSelectmapcollectmapmapcar-car

La fonction `map` est parfois généralisée pour accepter des fonctions dyadiques (à deux arguments) qui appliquent une fonction fournie par l'utilisateur aux éléments correspondants de deux listes. Certains langages utilisent des noms spécifiques pour cela, tels que `map2` ou `zipWith` . Les langages utilisant des fonctions variadiques explicites peuvent proposer des versions de `map` à arité variable pour prendre en charge ce type de fonctions. L'utilisation de `map` avec deux listes ou plus pose le problème de la gestion des listes de longueurs différentes. Les langages adoptent des comportements variés à ce sujet. Certains lèvent une exception. D'autres s'arrêtent à la longueur de la liste la plus courte et ignorent les éléments supplémentaires des autres listes. D'autres encore continuent jusqu'à la longueur de la liste la plus longue et, pour les listes déjà traitées, passent une valeur d'espace réservé à la fonction pour indiquer qu'aucune valeur n'est attendue.

Dans les langages qui prennent en charge les fonctions de première classe et la curryfication , mapon peut partiellement appliquer cette méthode pour transformer une fonction qui ne fonctionne que sur une seule valeur en un équivalent élément par élément qui fonctionne sur un conteneur entier ; par exemple, ` map squareis` est une fonction Haskell qui met au carré chaque élément d'une liste.