Map (高階函數)

在很多編程語言中，映射（map）是一個高階函數的名字，它將一個給定函數（英語：procedural parameter）應用到一個函子比如列表的每個元素，返回按相同次序的一個列表。映射的概念不受限於列表：它可工作在順序的容器，類似樹的容器，甚至是抽象容器比如future與promise。

關於同名的由鍵值對構成的抽象數據類型，請見「關聯數組」。

映射在作為泛函形式考慮時，經常叫做「應用於全部」。在支持頭等函數和柯里化的語言中，map可以部份應用（英語：partial application）在一個函數上，將這個只工作在一個值之上函數，提升為工作在整個容器上的逐個元素上的函數。

定義

map作為Haskell的基本前序（prelude：就是標準庫）的一部份提供並被實現為：

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

在這個定義之中，涉及到四種不同的模式：

• f是匹配「無論任何事物」的模式，並綁定f變量至所匹配的任何事物。
• (x : xs)是匹配「非空列表」的模式，它是通過將要被綁定到x變量某個事物，cons（這裡是(:)函數）到要被綁定到xs變量的某個其他事物之上而形成的。
• []是匹配「空列表」的模式，它不綁定任何變量。
• _是匹配不被綁定的任何事物的模式（通配符即「不在意」模式）。

Lisp語言在1959年介入了叫做maplist的映射函數^[1]，與1958年出現的版本稍有不同^[2]。這是maplist的最初定義，將一個函數連續的映射到整個列表和去除第一個元素餘下列表之上：

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

函數maplist在更新近的Lisp比如Common Lisp中仍可獲得到^[3]。Common Lisp提供映射函數家族，如mapcar和更一般性的map等，其中對應這裡所描述行為的那叫做mapcar，這裡的後綴car指示取列表第一個元素的CAR運算（英語：CAR and CDR）。

例子：映射一個列表

假定我們有一個整數的列表[1, 2, 3, 4, 5]，並想要計算每個整數的平方。要完成這個任務，首先要定義一個函數square來做單一數值的平方，下面用Haskell演示：

square x = x * x

然後就可以調用：

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

它產生[1, 4, 9, 16, 25]，展示了map遍歷了整個列表並應用函數square於每個元素。在ML、Haskell和F#中，函數是缺省以柯里化形式定義的，從而map square是對列表的每個元素做平方的Haskell函數。

在Lisp中，使用mapcar對列表的元素做平方，使用S-表達式表示法寫為：

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

使用函數maplist，上例將寫為：

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

可視的例子

下面將看到一個映射過程的每一步驟的可視演示，它依據函數${\displaystyle f(x)=x+1}$將整數列表X = [0, 5, 8, 3, 2, 1]映射成新的列表X'：

在應用一個函數於一個列表時的處理步驟的演示

推廣

主條目：函子 (函數式編程)

在Haskell中，多態函數map :: (a -> b) -> [a] -> [b]，被推廣成多類型函數fmap :: Functor f => (a -> b) -> f a -> f b，它應用於屬於函子Functor類型類的任何類型上。

列表的類型構造子[]可以定義為Functor類型類的實例，使用上例中的map函數：

instance Functor [] where
  fmap = map

其他Functor實例的例子包括樹：

-- 一个简单的二叉树
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)

在一個樹之上的映射產生：

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

對於Functor類型類的所有實例，fmap都在契約義務上要滿足函子定律：

fmap id      ≡ id              -- 同一律
fmap (f . g) ≡ fmap f . fmap g -- 复合律

這裡的.在Haskell中指示函數複合（英語：Function composition (computer science)）。

尤其是，它允許為各種搜集定義逐個元素的運算。

此外，如果F和G是兩個函子，自然變換是多態類型${\displaystyle h:\forall T.F(T)\to G(T)}$的函數，它遵守${\displaystyle fmap}$：

${\displaystyle h_{Y}\circ \operatorname {fmap} (f)=\operatorname {fmap} (f)\circ h_{X}}$，對於任何函數${\displaystyle f:X\to Y}$。

如果${\displaystyle h}$函數是按上述類型定義那樣用參數多態定義的，這個規定總是滿足的。

優化

映射的數學基礎允許很多優化（英語：Program optimization）。複合定律確保了如下二者：

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

導致相同的結果；就是說${\displaystyle \operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)}$。但是第二種形式比第一種形式在計算上更加有效率，因為每個map要求從頭重建整個列表。因此，編譯器將嘗試將第一種形式變換第二種形式；這種類型的優化叫做「映射融合」，是循環融合（英語：Loop fission and fusion）的函數式類似者^[4]。

映射函數可以並經常依據fold比如foldr來定義，這意味着可以做「map-fold融合」：foldr f z . map g等價於foldr (f . g) z。

在一個單鍊表上的map實現不是尾遞歸的，所以它在調用於大型列表的時候，可能在棧上建造大量的幀。很多語言作為替代的提供「逆向map」函數，它等價於逆轉一個映射後的列表，但它是尾遞歸的。下面是利用了左fold函數的一個實現：

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

因為逆轉單鍊表也是尾遞歸的，reverse和reverse-map可以複合起來以尾遞歸方式進行正常的map，儘管這需要在這個列表上進行兩趟。

語言比較

映射函數出現在函數式編程語言之中。現在映射函數在很多過程式、面向對象和多范型語言中也能獲得到（或能夠定義）：在C++的標準模板庫中，它叫做std::transform，在C#（3.0）的LINQ庫中，它被作為叫做Select的擴展方法。映射也經常在高級語言中的計算，比如ColdFusion標記語言（英語：ColdFusion Markup Language）（CFML）、Perl、Python和Ruby；在這四種語言中這個運算都叫做map 。在Ruby中還提供collect作為map的別名（來自Smalltalk）。有些語言通過語法構造提供與映射函數相同的功能。

映射有時被推廣為接收二元的（2個參數）函數，它可以把用戶提供的函數應用到來自兩個列表的對應元素上。有些語言對它使用特殊名字，比如「map2」或「zipWith」。使用顯式的可變元數函數的語言擁有可變元數版本的映射來支持可變元數函數。有2個或更多列表在這些列表有不同長度的時候遇到需要處理的問題。各種語言在這個問題上是不同的。有些引起異常。有些在達到最短列表長度之後停止並忽略在其他列表上的額外項目。有些繼續直到最長列表長度，並對已經結束的列表，向函數傳遞某個占位符的值來指示沒有值。

各種語言中的Map

語言	Map	Map 2個列表	Map n個列表	注釋	處理不同長度的列表
APL	func list	list1 func list2	func/ list1 list2 list3 list4	APL的數組處理能力使得map這樣的運算隱式進行	如果列表窗度不相等或者是1則長度錯誤
Common Lisp	(mapcar func list)	(mapcar func list1 list2)	(mapcar func list1 list2 ...)		在達到最短列表長度後停止
C++	std::transform(begin, end, result, func)	std::transform(begin1, end1, begin2, result, func)		在頭文件<algorithm>中 begin、end和result是迭代器 書寫結果起始於result
C#	ienum.Select(func) 或 select子句[5]	ienum1.Zip(ienum2, func)		Select是擴展方法 ienum是個IEnumerable Zip介入於.NET 4.0 在所有.NET語言中都類似	在最短列表結束後停止
CFML（英語：ColdFusion Markup Language）	obj.map(func)			這裡的obj是一個數組或結構。func接受作為參數的是每個項目的值，它的索引或鍵，和到最初對象的引用。
Clojure	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		在最短列表結束後停止
D	list.map!func	zip(list1, list2).map!func	zip(list1, list2, ...).map!func		給定給zip可通過StoppingPolicy: 最短、最長或requireSameLength
Erlang	lists:map(Fun, List)	lists:zipwith(Fun, List1, List2)	zipwith3也能得到		列表必須等長
Elixir	Enum.map(list, fun)	Enum.zip(list1, list2) |> Enum.map(fun)	List.zip([list1, list2, ...]) |> Enum.map(fun)		在最短列表結束後停止
F#	List.map func list	List.map2 func list1 list2		函數對其他類型存在（Seq和Array）	拋出異常
Groovy	list.collect(func)	[list1 list2].transpose().collect(func)	[list1 list2 ...].transpose().collect(func)
Haskell	map func list	zipWith func list1 list2	zipWithn func list1 list2 ...	n對應於列表的數目，預先定義直到zipWith7	在最短列表結束後停止
Haxe	array.map(func) list.map(func) Lambda.map(iterable, func)
J	func list	list1 func list2	func/ list1, list2, list3 ,: list4	J的數組處理能力使得map這樣的運算隱式進行	如果列表長度不等則長度錯誤
Java 8+	stream.map(func)
JavaScript 1.6 ECMAScript 5	array#map(func) （頁面存檔備份，存於網際網路檔案館）	List1.map(function (elem1, i) { return func(elem1, List2[i]); })	List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })	Array#map 傳遞3個實際參數到func: 元素、元素的索引和這個數組。不用的實際參數可以忽略。	在List1結束時停止，用undefined項目擴展較短的數組，如果需要的話。
Julia	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ..., listN)		ERROR: DimensionMismatch
Logtalk（英語：Logtalk）	map(Closure, List)	map(Closure, List1, List2)	map(Closure, List1, List2, List3, ...) (直到7个列表)	只有Closure參數必須被實例化。	失敗
Mathematica	func /@ list Map[func, list]	MapThread[func, {list1, list2}]	MapThread[func, {list1, list2, ...}]		列表必須等長
Maxima	map(f, expr1, ..., exprn) maplist(f, expr1, ..., exprn)			map返回一個表達式，其前導算子同於這個表達式的算子； maplist返回一個列表
OCaml	List.map func list Array.map func array	List.map2 func list1 list2			發起Invalid_argument異常
PARI/GP（英語：PARI/GP）	apply(func, list)				不適用
Perl	map block list map expr, list			在block或expr中特殊變量$_持有依次來自這個列表的值。	Helper List::MoreUtils::each_array組合多於一個列表直到最長的那個被耗盡，用undef.填入其他的。
PHP	array_map(callable, array)	array_map(callable, array1,array2)	array_map(callable, array1,array2, ...)	callable的形式參數的數目 應當匹配數組的數目。	用NULL項目擴展較短的列表
Prolog	maplist(Cont, List1, List2).	maplist(Cont, List1, List2, List3).	maplist(Cont, List1, ...).	列表實際參數是輸入、輸出或二者。也包括zipWith, unzip, all	靜默失敗（不是錯誤）
Python	map(func, list)	map(func, list1, list2)	map(func, list1, list2, ...)	在Python 2中返回一個列表，在Python 3中返回一個迭代器。	zip()和map() (3.x)在最短列表結束後停止，而map()(2.x)和itertools.zip_longest()(3.x)用None項目擴展較短的列表
Ruby	enum.collect {block} enum.map {block}	enum1.zip(enum2).map {block}	enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}	enum is an Enumeration	在它調用在其上的對象（第一個列表）結束時停止；如果任何其他列表更短，用nil項目擴展它
Rust	list1.into_iter().map(func)	list1.into_iter().zip(list2).map(func)		Iterator::map和Iterator::zip方法二者接受最初迭代器的所屬關係並返回一個新的；Iterator::zip方法內部的調用IntoIterator::into_iter方法在list2之上	在較短列表結束後停止
S-R	lapply(list, func)	mapply(func, list1, list2)	mapply(func, list1, list2, ...)		較短列表被循環
Scala	list.map(func)	(list1, list2).zipped.map(func)	(list1, list2, list3).zipped.map(func)	注意：多於3不可能。	在較短列表結束後停止
Scheme（包括Guile和Racket）	(map func list)	(map func list1 list2)	(map func list1 list2 ...)		列表必須都有相同長度（SRFI-1擴展接受不同長度的列表）
Smalltalk	aCollection collect: aBlock	aCollection1 with: aCollection2 collect: aBlock			失敗
Standard ML	map func list	ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)		對於2實際參數map，func接受在一個元組中的實際參數	ListPair.map在最短列表結束後停止，而ListPair.mapEq引起UnequalLengths異常
Swift	sequence.map(func)	zip(sequence1, sequence2).map(func)			在最短列表結束後停止
XPath 3 XQuery（英語：XQuery） 3	list ! block for-each(list, func)	for-each-pair(list1, list2, func)		在block上下文中項目.持有當前值	在最短列表結束後停止

參見

• 函子 (函數式編程)
• 卷繞 (計算機科學)（英語：Convolution (computer science)），也叫做「conv」或「zip」
• Filter (高階函數)
• Fold (高階函數)
• foreach循環
• 自由幺半群
• 高階函數
• 列表推導式
• Map (並行模式)（英語：Map (parallel pattern)）