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`上下文中项目`.`持有当前值｜在最短列表结束后停止