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