Map (高阶函数)

在很多编程语言中，映射（map）是一个高阶函数的名字，它将一个应用到一个函子比如列表的每个元素，返回按相同次序的一个列表。映射的概念不受限于列表：它可工作在顺序的容器，类似树的容器，甚至是抽象容器比如future与promise。

映射在作为泛函形式考虑时，经常叫做“应用于全部”。在支持头等函数和柯里化的语言中，map可以在一个函数上，将这个只工作在一个值之上函数，提升为工作在整个容器上的逐个元素上的函数。

定义
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的映射函数，与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指示取列表第一个元素的。

例子：映射一个列表

假定我们有一个整数的列表[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))

可视的例子 
下面将看到一个映射过程的每一步骤的可视演示，它依据函数将整数列表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中指示。

尤其是，它允许为各种搜集定义逐个元素的运算。

此外，如果和是两个函子，自然变换是多态类型的函数，它遵守：
 ，对于任何函数。

如果函数是按上述类型定义那样用参数多态定义的，这个规定总是满足的。

优化

映射的数学基础允许很多。复合定律确保了如下二者：
 (map f . map g) list
 map (f . g) list
导致相同的结果；就是说。但是第二种形式比第一种形式在计算上更加有效率，因为每个map要求从头重建整个列表。因此，编译器将尝试将第一种形式变换第二种形式；这种类型的优化叫做“映射融合”，是的函数式类似者。

映射函数可以并经常依据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的扩展方法。映射也经常在高级语言中的计算，比如（CFML）、Perl、Python和Ruby；在这四种语言中这个运算都叫做map 。在Ruby中还提供collect作为map的别名（来自Smalltalk）。有些语言通过语法构造提供与映射函数相同的功能。

映射有时被推广为接收二元的（2个参数）函数，它可以把用户提供的函数应用到来自两个列表的对应元素上。有些语言对它使用特殊名字，比如“map2”或“zipWith”。使用显式的可变元数函数的语言拥有可变元数版本的映射来支持可变元数函数。有2个或更多列表在这些列表有不同长度的时候遇到需要处理的问题。各种语言在这个问题上是不同的。有些引起异常。有些在达到最短列表长度之后停止并忽略在其他列表上的额外项目。有些继续直到最长列表长度，并对已经结束的列表，向函数传递某个占位符的值来指示没有值。

参见
函子 (函数式编程)
 ，也叫做“conv”或“zip”
 Filter (高阶函数)
 Fold (高阶函数)
 foreach循环
 自由幺半群
 高阶函数
 列表推导式

引用

高阶函数
编程语言比较
编程中的迭代