Map (高階函數)

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

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

## 定義

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

```haskell
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`的映射函數，與1958年出現的版本稍有不同。這是`maplist`的最初定義，將一個函數連續的映射到整個列表和去除第一個元素餘下列表之上：

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

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

## 例子：映射一個列表

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

```haskell
square x = x * x
```

然後就可以調用：

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

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

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

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

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

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

### 可視的例子

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

<image>

## 推廣

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

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

```haskell
instance Functor [] where
  fmap = map
```

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

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

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

```haskell
>>> 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`都在契約義務上要滿足函子定律：

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

這裡的`.`在Haskell中指示函數複合 (電腦科學)。

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

此外，如果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$函數是按上述類型定義那樣用參數多態定義的，這個規定總是滿足的。

## 優化

映射的數學基礎允許很多程序優化。複合定律確保了如下二者：

- `(map f . map g) list`
- `map (f . g) list`

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

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

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

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

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

## 語言比較

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

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

語言｜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(<wbr/>''begin'', ''end'', ''result'', ''func'')`｜`std::transform(<wbr/>''begin1'', ''end1'', ''begin2'', ''result'', ''func'')`｜在頭文件中begin、end和result是迭代器書寫結果起始於result

C#｜`''ienum''.Select(''func'')`或`select`子句｜`''ienum1''.Zip(''ienum2'', ''func'')`｜`Select`是擴展方法 ienum是個IEnumerable`Zip`介入於.NET 4.0在所有.NET語言中都類似｜在最短列表結束後停止

ColdFusion標記語言｜`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'') &#124;> Enum.map(fun)`｜`List.zip([''list1'', ''list2'', ...]) &#124;> Enum.map(fun)`｜在最短列表結束後停止

F#｜`List.map ''func'' ''list''`｜`List.map2 ''func'' ''list1'' ''list2''`｜函數對其他類型存在（Seq和Array）｜拋出異常

Groovy｜`list.collect(func)`｜`[list1 list2]<wbr>.transpose()<wbr>.collect(func)`｜`[list1 list2 ...]<wbr>.transpose()<wbr>.collect(func)`

Haskell｜`map ''func'' ''list''`｜`zipWith ''func'' ''list1'' ''list2''`｜`zipWith''n'' ''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.6ECMAScript 5｜ `''array''#map(''func'')`｜`''List1''.map(function (elem1, i) { <br />return ''func''(elem1, ''List2''[i]); })`｜`''List1''.map(function (elem1, i) { <br />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｜`map(''Closure'', ''List'')`｜`map(''Closure'', ''List1'', ''List2'')`｜`map(''Closure'', ''List1'', ''List2'', ''List3'', ...) (直到7个列表)`｜只有Closure參數必須被實例化。｜失敗

Mathematica｜`''func'' /@ ''list'' <br /> Map[''func'', ''list'']`｜`MapThread[''func'', {''list1'', ''list2''}]`｜`MapThread[''func'', {''list1'', ''list2'', ...}]`｜列表必須等長

Maxima｜`map(''f'', ''expr<sub>1</sub>'', ..., ''expr<sub>n</sub>'')<br />maplist(''f'', ''expr<sub>1</sub>'', ..., ''expr<sub>n</sub>'')`｜map返回一個表達式，其前導算子同於這個表達式的算子；maplist返回一個列表

OCaml｜`List.map ''func'' ''list''<br /> Array.map ''func'' ''array''`｜`List.map2 ''func'' ''list1'' ''list2''`｜發起Invalid_argument異常

PARI/GP｜`apply(''func'', ''list'')`｜不適用

Perl｜`map ''block'' ''list''<br /> 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''}<br /> ''enum''.map {''block''}`｜`''enum1''.zip(''enum2'')<wbr/>.map {''block''}`｜`''enum1''.zip(''enum2'', ...)<wbr/>.map {''block''} <br /> [''enum1'', ''enum2'', ...]<wbr/>.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'')<wbr/>.zipped.map(''func'')`｜`(''list1'', ''list2'', ''list3'')<wbr/>.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'') <br /> ListPair.mapEq ''func'' (''list1'', ''list2'')`｜對於2實際參數map，func接受在一個元組中的實際參數｜`''ListPair.map''`在最短列表結束後停止，而`''ListPair.mapEq''`引起`UnequalLengths`異常

Swift｜`''sequence''.map(''func'')`｜`zip(''sequence1'', ''sequence2'').map(''func'')`｜在最短列表結束後停止

XPath 3XQuery 3｜`list ! block` `for-each(list, func)`｜`for-each-pair(list1, list2, func)`｜在`block`上下文中項目`.`持有當前值｜在最短列表結束後停止