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

V mnoha programovacích jazycích je mapa název funkce vyššího řádu, která aplikuje danou funkci na každý prvek funktoru , např. Seznam , vrací seznam výsledků ve stejném pořadí. Je - li zvažován ve funkční formě, je často nazýván aplikovatelný na všechny .

Koncept mapy není omezen na seznamy: funguje pro sekvenční kontejnery , kontejnery podobné stromům 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ěli bychom vypočítat druhou mocninu každého celého čísla. Za tímto účelem nejprve definujeme funkci pro squarejedno číslo (zde zobrazené v Haskellu ):

square x = x * x

Potom můžeme zavolat

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

což poskytuje [1, 4, 9, 16, 25], což ukazuje, že mapprošel celým seznamem a použil funkci squarena každý prvek.

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}$

Zobrazení kroků zpracování při použití funkce mapy v seznamu

Soubor mapje poskytován jako součást základní předehry společnosti Haskell (tj. „Standardní knihovna“) a je implementován jako:

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

Zobecnění

V Haskellu je polymorfní funkce map :: (a -> b) -> [a] -> [b] zobecněna na polytypovou funkci fmap :: Functor f => (a -> b) -> f a -> f b , která platí pro jakýkoli typ patřící do třídy typů . Functor

Konstruktor typu seznamů []lze definovat jako instanci třídy Functortypu pomocí mapfunkce z předchozího příkladu:

instance Functor [] where
  fmap = map

Mezi další příklady Functorinstancí patří stromy:

-- 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)

Mapování výnosů stromu:

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

Pro každý případ třídy Functortypu fmapje smluvně povinen dodržovat zákony funktorů:

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

kde .označuje funkční složení v Haskellu.

Mimo jiné to umožňuje definovat elementární operace pro různé druhy kolekcí .

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

${\ Displaystyle h_ {Y} \ circ \ operatorname {fmap} (f) = \ operatorname {fmap} (f) \ circ h_ {X}}$pro jakoukoli funkci .${\ Displaystyle f: X \ až Y}$

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

Optimalizace

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

• (map f . map g) list a
• map (f . g) list

vést ke stejnému výsledku; to je , . Druhá forma je však pro výpočet efektivnější než první forma, protože každá vyžaduje přestavbu celého seznamu od začátku. Proto se kompilátoři pokusí transformovat první formu na druhou; tento typ optimalizace je známý jako mapová fúze a je funkčním analogem smyčkové fúze . ${\ displaystyle \ operatorname {map} (f) \ circ \ operatorname {map} (g) = \ operatorname {map} (f \ circ g)}$map

Mapové funkce mohou být a často jsou definovány jako záhyby, jako například foldr, což znamená, že lze provést fúzi skládání mapy : foldr f z . map gje ekvivalentní foldr (f . g) z.

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

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

Protože obrácení jednotlivě propojeného seznamu je také rekurzivní ocas, reverzní a reverzní mapa mohou být složeny tak, aby prováděly normální mapu rekurzivním způsobem, ačkoli to vyžaduje provedení dvou průchodů přes seznam.

Porovnání jazyků

Funkce mapy pochází z funkčních programovacích jazyků.

Jazyk Lisp představil mapovou funkci nazvanou maplistv roce 1959, s mírně odlišnými verzemi se již objevily v roce 1958. Toto je původní definice pro maplistmapování funkce přes po sobě jdoucí odpočinkové seznamy:

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

Funkce maplistje stále k dispozici v novějších lispech, jako je Common Lisp , i když by se upřednostňovaly funkce jako mapcarnebo obecnější map.

Vyrovnávání prvků seznamu pomocí maplistby bylo zapsáno v zápisu výrazu S takto:

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

Pomocí funkce mapcarby výše uvedený příklad byl napsán takto:

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

Dnešní mapování funkce jsou podporovány (nebo může být definováno) v mnoha procesních , objektově orientované , a multi-paradigma jazycích také: V C ++ je standardní knihovny , se nazývá std::transform, v C # (3,0) je knihovna LINQ, že je poskytované jako metoda rozšíření nazvaná Select. Mapa je také často používanou operací v jazycích vysoké úrovně, jako je ColdFusion Markup Language (CFML), Perl , Python a Ruby ; operace se nazývá mapve všech čtyřech těchto jazycích. collectAlias mapje také v Ruby (od Smalltalk ). Common Lisp poskytuje řadu funkcí podobných mapám; nazývá se chování odpovídající zde popsanému chování mapcar( -carindikující přístup pomocí operace CAR ). Existují také jazyky se syntaktickými konstrukty poskytující stejné funkce jako funkce mapy.

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

V jazycích, které podporují prvotřídní funkce a currying , maplze částečně aplikovat na zvednutí funkce, která funguje pouze na jedné hodnotě, na elementární ekvivalent, který funguje na celém kontejneru; například map squareje funkce Haskell, která čtverce každý prvek seznamu.

Viz také

• Funktor (funkční programování)
• 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
• Porozumění seznamu
• Mapa (paralelní vzor)

Reference