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的映射函数^[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))

下面将看到一个映射过程的每一步骤的可视演示，它依据函数${\displaystyle f(x)=x+1}$ 将整数列表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中指示函数复合（英语：Function composition (computer science)）。

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

此外，如果F和G是两个函子，自然变换是多态类型${\displaystyle h:\forall T.F(T)\to G(T)}$ 的函数，它遵守${\displaystyle fmap}$ ：

${\displaystyle h_{Y}\circ \operatorname {fmap} (f)=\operatorname {fmap} (f)\circ h_{X}}$ ，对于任何函数${\displaystyle f:X\to Y}$ 。

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

映射的数学基础允许很多优化（英语：Program optimization）。复合定律确保了如下二者：

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

导致相同的结果；就是说${\displaystyle \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个或更多列表在这些列表有不同长度的时候遇到需要处理的问题。各种语言在这个问题上是不同的。有些引起异常。有些在达到最短列表长度之后停止并忽略在其他列表上的额外项目。有些继续直到最长列表长度，并对已经结束的列表，向函数传递某个占位符的值来指示没有值。

• 函子 (函数式编程)
• 卷绕 (计算机科学)（英语：Convolution (computer science)），也叫做“conv”或“zip”
• Filter (高阶函数)
• Fold (高阶函数)
• foreach循环
• 自由幺半群
• 高阶函数
• 列表推导式
• Map (并行模式)（英语：Map (parallel pattern)）