Mapa (funkce vyššího řádu) - Map (higher-order function)

V mnoha programovací jazyky, mapa je jméno a funkce vyššího řádu to platí a dané funkce ke každému prvku a funktor, např. A seznam, vrací seznam výsledků ve stejném pořadí. Často se tomu říká aplikujte na vše když se uvažuje v funkční forma.

Koncept mapy se neomezuje pouze na seznamy: funguje pro sekvenční kontejnery, kontejnery ve tvaru stromu nebo dokonce abstraktní kontejnery, jako jsou futures a sliby.

Příklady: mapování seznamu

Předpokládejme, že máme seznam celých čísel [1, 2, 3, 4, 5] a chtěl bych vypočítat druhou mocninu každého celého čísla. K tomu nejdříve definujeme funkci náměstí jedno číslo (zobrazené zde v Haskell ):

náměstí X = X * X

Poté můžeme zavolat

>>> mapa náměstí [1, 2, 3, 4, 5]

který přináší [1, 4, 9, 16, 25], což dokazuje mapa prošel celým seznamem a použil funkci náměstí ke každému prvku.

Vizuální příklad

Níže vidíte pohled na každý krok procesu mapování pro seznam celých čísel X = [0, 5, 8, 3, 2, 1] které chceme mapovat do nového seznamu X' podle funkce ${displaystyle f (x) = x + 1}$ :

Pohled na kroky zpracování při aplikaci mapové funkce na seznam

The mapa je poskytována jako součást základní předehry Haskella (tj. „standardní knihovna“) a je implementována jako:

mapa :: (A -> b) -> [A] -> [b]mapa _ []       = []mapa F (X : xs) = F X : mapa F xs

Zobecnění

V Haskellu polymorfní funkce mapa :: (a -> b) -> [a] -> [b] je zobecněn na a polytypická funkce fmap :: Funktor f => (a -> b) -> f a -> f b, který platí pro jakýkoli typ patřící do Funktor typová třída.

The konstruktor typu seznamů [] lze definovat jako instanci Funktor zadejte třídu pomocí mapa funkce z předchozího příkladu:

instance Funktor [] kde  fmap = mapa

Další příklady Funktor instance zahrnují stromy:

- jednoduchý binární stromdata Strom A = List A | Vidlička (Strom A) (Strom A)instance Funktor Strom kde    fmap F (List X) = List (F X)  fmap F (Vidlička l r) = Vidlička (fmap F l) (fmap F r)

Mapování nad stromem přináší:

>>> fmap náměstí (Vidlička (Vidlička (List 1) (List 2)) (Vidlička (List 3) (List 4)))Vidlička (Vidlička (List 1) (List 4)) (Vidlička (List 9) (List 16))

Pro každou instanci Funktor typová třída, fmap je smluvně zavázán řídit se funktorovými zákony:

fmap id      ≡ id              - zákon o totožnostifmap (F . G) ≡ fmap F . fmap G - zákon o složení

kde . označuje složení funkce v Haskellu.

To mimo jiné umožňuje definovat elementární operace pro různé druhy sbírky.

Navíc pokud F a G jsou dva funktory, a přirozená transformace je funkcí polymorfního typu ${displaystyle h: forall T.F (T) o G (T)}$ který respektuje fmap:

${displaystyle h_ {Y} cirkus operatorname {fmap} (f) = operatorname {fmap} (f) cirkus h_ {X}}$ pro jakoukoli funkci ${displaystyle f: X o Y}$.

Pokud h funkce je definována parametrický polymorfismus stejně jako v definici typu výše je tato specifikace vždy splněna.

Optimalizace

Matematický základ map umožňuje řadu optimalizace. Zákon o složení zajišťuje, že obojí

• (mapa f. mapa g) seznam a
• seznam map (např. g)

vést ke stejnému výsledku; to je ${displaystyle operatorname {map} (f) circ operatorname {map} (g) = operatorname {map} (fcirc g)}$. Druhá forma je však efektivnější pro výpočet než první forma, protože každá mapa vyžaduje opětovné sestavení celého seznamu. Proto se kompilátoři pokusí převést první formulář do druhého; tento typ optimalizace je známý jako fúze mapy a je funkční analog smyčková fúze.^[1]

Mapové funkce mohou být a často jsou definovány pomocí a složit jako foldr, což znamená, že je možné udělat a fúze skládání mapy: foldr f z. mapa g je ekvivalentní k foldr (f. g) z.

Implementace mapy výše na jednotlivě propojených seznamech není ocas rekurzivní, takže při volání s velkým seznamem může na zásobníku vzniknout spousta snímků. Mnoho jazyků střídavě poskytuje funkci „reverzní mapy“, která je ekvivalentní obrácení mapovaného seznamu, ale je rekurzivní ocasem. Zde je implementace, která využívá složit -levá funkce.

reverseMap F = složit (ys X -> F X : ys) []

Vzhledem k tomu, že reverzace jednotlivě propojeného seznamu je také rekurzivní ocasem, lze reverzní a reverzní mapu skládat tak, aby prováděla normální mapu ocasně rekurzivním způsobem, i když vyžaduje provedení dvou průchodů seznamem.

Porovnání jazyků

Funkce mapy pochází z Funkcionální programování jazyky.

Jazyk Lisp představil mapovou funkci s názvem seznam map^[2] v roce 1959, přičemž mírně odlišné verze se již objevily v roce 1958.^[3] Toto je původní definice pro seznam map, mapování funkce přes postupné seznamy odpočinku:

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

Funkce seznam map je stále k dispozici v novějších listech jako Společný Lisp,^[4] i když funkce jako mapcar nebo obecnější mapa bylo by upřednostňováno.

Srovnání prvků seznamu pomocí seznam map bude napsáno dovnitř S-výraz zápis takto:

(seznam map (lambda (l) (čtv (auto l))) '(1 2 3 4 5))

Používání funkce mapcar, výše uvedený příklad by byl napsán takto:

(mapcar (funkce čtv) '(1 2 3 4 5))

Dnes jsou mapovací funkce podporovány (nebo mohou být definovány) v mnoha procesní, objektově orientovaný, a multi-paradigma jazyky také: v C ++ je Standardní knihovna šablon, to se nazývá std :: transformace, v C# Knihovna LINQ (3.0) je poskytována jako metoda rozšíření s názvem Vybrat. Mapa je také často používanou operací ve vyšších jazycích, jako je Značkovací jazyk ColdFusion (CFML), Perl, Krajta, a Rubín; operace se volá mapa ve všech čtyřech těchto jazycích. A sbírat alias pro mapa je také poskytována v Ruby (od Pokec ). Společný Lisp poskytuje rodinu mapových funkcí; nazývá se ten, který odpovídá zde popsanému chování mapcar (-auto označující přístup pomocí Provoz vozu ). Existují také jazyky se syntaktickými konstrukty, které poskytují stejnou funkcionalitu jako mapová funkce.

Mapa je někdy zobecněna tak, aby přijímala dyadické (2 argumenty) funkce, které mohou použít funkci dodanou uživatelem na odpovídající prvky ze dvou seznamů. Některé jazyky k tomu používají speciální názvy, například mapa2 nebo zipWith. Jazyky používající explicitní variadické funkce může mít verze mapy s proměnnou arity podporovat variabilní arity funkce. Mapa se 2 nebo více seznamy naráží na problém zpracování, když jsou seznamy různé délky. Různé jazyky se v tomto liší. Někteří vznesou výjimku. Některé se zastaví po délce nejkratšího seznamu a ignorují další položky v ostatních seznamech. Některé pokračují v délce nejdelšího seznamu a u seznamů, které již skončily, předejte nějaké zástupné hodnotě funkci označující žádnou hodnotu.

V jazycích, které podporují prvotřídní funkce a kari, mapa možná částečně aplikováno na výtah funkce, která pracuje pouze na jedné hodnotě s ekvivalentním prvkem, který funguje na celém kontejneru; například, čtverec mapy je funkce Haskell, která umocňuje každý prvek seznamu na druhou.

Viz také

• Konvoluce (počítačová věda), také nazývané konv nebo zip
• Filtr (funkce vyššího řádu)
• Fold (funkce vyššího řádu)
• pro každého
• Zdarma monoid
• Funkcionální programování
• Funkce vyššího řádu
• Seznam s porozuměním
• Mapa (paralelní vzor)

Reference