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

可視的例子

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

applying map function processing steps — 在應用一個函數於一個列表時的處理步驟的演示

推廣

在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$ 是兩個函子，自然變換是多型類型 $h:\forall T.F(T)\to G(T)$ 的函數，它遵守 $fmap$ ：

h_{Y}\circ \operatorname {fmap} (f)=\operatorname {fmap} (f)\circ h_{X}

，對於任何函數

f:X\to Y

。

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

最佳化

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

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

導致相同的結果；就是說 $\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, expr₁, ..., expr_n) maplist(f, expr₁, ..., expr_n)`			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)）

參照

^ J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959 (PDF). [2021-02-11]. （原始內容 (PDF)存檔於2021-04-04）.
^ J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958 (PDF). [2021-02-11]. （原始內容 (PDF)存檔於2021-04-04）.
^ Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp. [2021-02-11]. （原始內容存檔於2020-11-12）.
^ "Map fusion: Making Haskell 225% faster". [2021-02-11]. （原始內容存檔於2013-08-06）.
^ select clause (C# Reference) （頁面存檔備份，存於互聯網檔案館）.

[1] J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959 (PDF). [2021-02-11]. （原始內容 (PDF)存檔於2021-04-04）.

[2] J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958 (PDF). [2021-02-11]. （原始內容 (PDF)存檔於2021-04-04）.

[3] Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp. [2021-02-11]. （原始內容存檔於2020-11-12）.

[4] "Map fusion: Making Haskell 225% faster". [2021-02-11]. （原始內容存檔於2013-08-06）.

[5] select clause (C# Reference) （頁面存檔備份，存於互聯網檔案館）.

[1]

[2]

[3]

[4]

[5]