Hartă (funcție de ordin superior) - Map (higher-order function)

În multe limbaje de programare , harta este numele unei funcții de ordin superior care aplică o funcție dată fiecărui element al unui functor , de exemplu o listă , returnând o listă de rezultate în aceeași ordine. Este adesea numit aplicabil la toate atunci când este considerat sub formă funcțională .

Conceptul de hartă nu se limitează la liste: funcționează pentru containere secvențiale , containere asemănătoare copacilor sau chiar containere abstracte, cum ar fi futures și promisiuni .

Exemple: maparea unei liste

Să presupunem că avem o listă de numere întregi [1, 2, 3, 4, 5]și am dori să calculăm pătratul fiecărui număr întreg. Pentru a face acest lucru, mai întâi definim o funcție într- squareun singur număr (prezentat aici în Haskell ):

square x = x * x

După aceea, putem suna

>>> map square [1, 2, 3, 4, 5]

care cedează [1, 4, 9, 16, 25], demonstrând că mapa trecut prin întreaga listă și a aplicat funcția squarefiecărui element.

Exemplu vizual

Mai jos, puteți vedea o vedere a fiecărui pas al procesului de mapare pentru o listă de numere întregi pe X = [0, 5, 8, 3, 2, 1]care dorim să le mapăm într-o nouă listă în X'funcție de funcție  : ${\ F displaystyle (x) = x + 1}$

Vizualizarea etapelor de procesare la aplicarea funcției de hartă pe o listă

Este mapfurnizat ca parte a preludiului de bază al lui Haskell (adică „biblioteca standard”) și este implementat ca:

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

Generalizare

În Haskell, funcția polimorfă map :: (a -> b) -> [a] -> [b] este generalizată la o funcție politipică fmap :: Functor f => (a -> b) -> f a -> f b , care se aplică oricărui tip care aparține clasei de tip . Functor

Constructorul de tip al listelor []poate fi definit ca o instanță a Functorclasei de tip folosind mapfuncția din exemplul anterior:

instance Functor [] where
  fmap = map

Alte exemple de Functorcazuri includ copaci:

-- a simple binary tree
data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where  
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

Cartarea peste un copac produce:

>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))

Pentru fiecare caz din Functorclasa de tip, fmapeste obligat contractual să respecte legile funcționarului:

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

unde .denotă compoziția funcției în Haskell.

Printre alte utilizări, aceasta permite definirea operațiunilor elementare pentru diferite tipuri de colecții .

Mai mult, dacă F și G sunt doi functori, o transformare naturală este o funcție de tip polimorf care respectă fmap : ${\ displaystyle h: \ forall TF (T) \ to G (T)}$

${\ displaystyle h_ {Y} \ circ \ operatorname {fmap} (f) = \ operatorname {fmap} (f) \ circ h_ {X}}$pentru orice funcție .${\ displaystyle f: X \ to Y}$

Dacă funcția h este definită de polimorfism parametric ca în definiția de tip de mai sus, această specificație este întotdeauna îndeplinită.

Optimizări

Baza matematică a hărților permite o serie de optimizări . Legea compoziției asigură că ambele

• (map f . map g) list și
• map (f . g) list

duce la același rezultat; adică . Cu toate acestea, a doua formă este mai eficientă de calculat decât prima formă, deoarece fiecare necesită reconstruirea unei liste întregi de la zero. Prin urmare, compilatoarele vor încerca să transforme prima formă în a doua; acest tip de optimizare este cunoscut sub numele de fuziune cu hărți și este analogul funcțional al fuziunii în buclă . ${\ displaystyle \ operatorname {map} (f) \ circ \ operatorname {map} (g) = \ operatorname {map} (f \ circ g)}$map

Funcțiile hărții pot fi și sunt adesea definite în termeni de pliere, cum ar fi foldr, ceea ce înseamnă că se poate face o fuziune hartă-pliere : foldr f z . map geste echivalent cu foldr (f . g) z.

Implementarea hărții de mai sus pe listele conectate individual nu este recursivă , așa că poate acumula o mulțime de cadre pe stivă atunci când este apelată cu o listă mare. Multe limbi oferă alternativ o funcție de „hartă inversă”, care este echivalentă cu inversarea unei liste mapate, dar este recursivă. Iată o implementare care utilizează funcția fold- stânga.

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

Deoarece inversarea unei liste legate individual este, de asemenea, recursivă la coadă, inversă și inversă a hărții pot fi compuse pentru a efectua o hartă normală într-un mod recursiv la coadă, deși necesită efectuarea a două treceri peste listă.

Compararea limbajului

Funcția hartă a apărut în limbaje funcționale de programare .

Limbajul Lisp a introdus o funcție de hartă numită maplistîn 1959, cu versiuni ușor diferite care apar deja în 1958. Aceasta este definiția originală pentru maplist, maparea unei funcții peste listele succesive de odihnă:

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

Funcția maplisteste încă disponibilă în Lisps mai noi, cum ar fi Common Lisp , deși funcții precum mapcarsau cele mai generice mapar fi preferate.

Cadrarea elementelor unei liste folosind maplistar fi scrisă în notație S-expression astfel:

(maplist (lambda (l) (sqr (car l))) '(1 2 3 4 5))

Folosind funcția mapcar, exemplul de mai sus ar fi scris astfel:

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

Astăzi funcțiile de cartografiere sunt acceptate (sau poate fi definit) în mai multe procedurale , orientate-obiect , și multi-paradigmă limbi precum: În C ++ 's Library Standard , este numit std::transform, în C # (3.0) biblioteca lui LINQ, este furnizat ca o metodă de extensie numită Select. Harta este, de asemenea, o operație frecvent utilizată în limbaje de nivel înalt, cum ar fi ColdFusion Markup Language (CFML), Perl , Python și Ruby ; operațiunea se numește mapîn toate cele patru dintre aceste limbi. Un collectalias pentru mapeste furnizat și în Ruby (de la Smalltalk ). Comună Lisp oferă o familie de funcții cum ar fi hartă; cel care corespunde comportamentului descris aici se numește mapcar( -carindicând accesul folosind operația CAR ). Există, de asemenea, limbaje cu construcții sintactice care oferă aceeași funcționalitate ca și funcția de hartă.

Harta este uneori generalizată pentru a accepta funcții diadice (cu 2 argumente) care pot aplica o funcție furnizată de utilizator elementelor corespunzătoare din două liste. Unele limbi folosesc nume speciale pentru aceasta, cum ar fi map2 sau zipWith . Limbile care folosesc funcții variadice explicite pot avea versiuni ale hărții cu aritate variabilă pentru a susține funcții de aritate variabilă . Harta cu 2 sau mai multe liste întâmpină problema manipulării atunci când listele au lungimi diferite. Diverse limbi diferă în acest sens. Unii ridică o excepție. Unii se opresc după lungimea celei mai scurte liste și ignoră elementele suplimentare de pe celelalte liste. Unii continuă până la lungimea celei mai lungi liste, iar pentru listele care s-au încheiat deja, transmiteți o anumită valoare de substituent funcției care nu indică nicio valoare.

În limbile care acceptă funcții de primă clasă și currying , mappot fi parțial aplicate pentru a ridica o funcție care funcționează pe o singură valoare la un echivalent elementar care funcționează pe un container întreg; de exemplu, map squareeste o funcție Haskell care pătrează fiecare element al unei liste.

Vezi si

• Functor (programare funcțională)
• Convoluție (informatică) , numită și conv sau zip
• Filtru (funcție de ordin superior)
• Fold (funcție de ordin superior)
• pentru fiecare
• Monoid gratuit
• Programare funcțională
• Funcție de ordin superior
• Înțelegerea listei
• Hartă (model paralel)

Referințe