Map (高阶函数)
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在很多编程语言中,映射(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
的映射函数[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运算。
例子:映射一个列表
假定我们有一个整数的列表[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'
:
![applying map function processing steps](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/0/06/Mapping-steps-loillibe-new.gif/480px-Mapping-steps-loillibe-new.gif)
推广
在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中指示函数复合。
尤其是,它允许为各种搜集定义逐个元素的运算。
此外,如果F和G是两个函子,自然变换是多态类型的函数,它遵守:
- ,对于任何函数。
如果函数是按上述类型定义那样用参数多态定义的,这个规定总是满足的。
优化
映射的数学基础允许很多优化。复合定律确保了如下二者:
(map f . map g) list
map (f . g) list
导致相同的结果;就是说。但是第二种形式比第一种形式在计算上更加有效率,因为每个map
要求从头重建整个列表。因此,编译器将尝试将第一种形式变换第二种形式;这种类型的优化叫做“映射融合”,是循环融合的函数式类似者[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标记语言(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(
|
std::transform(
|
在头文件<algorithm>中 begin、end和result是迭代器 书写结果起始于result |
||
C# | ienum.Select(func) 或 select 子句[5]
|
ienum1.Zip(ienum2, func)
|
Select 是扩展方法ienum是个IEnumerable Zip 介入于.NET 4.0在所有.NET语言中都类似 |
在最短列表结束后停止 | |
CFML | 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]
|
[list1 list2 ...]
|
||
Haskell | map func list
|
zipWith func list1 list2
|
zipWithn func list1 list2 ...
|
n 对应于列表的数目,预先定义直到zipWith7
|
在最短列表结束后停止 |
Haxe | array.map(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) {
|
List1.map(function (elem1, 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
|
MapThread[func, {list1, list2}]
|
MapThread[func, {list1, list2, ...}]
|
列表必须等长 | |
Maxima | map(f, expr1, ..., exprn)
|
map返回一个表达式,其前导算子同于这个表达式的算子; maplist返回一个列表 |
|||
OCaml | List.map func list
|
List.map2 func list1 list2
|
发起Invalid_argument异常 | ||
PARI/GP | apply(func, list)
|
不適用 | |||
Perl | map block 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}
|
enum1.zip(enum2)
|
enum1.zip(enum2, ...)
|
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)
|
(list1, list2, list3)
|
注意:多于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)
|
对于2实际参数map,func接受在一个元组中的实际参数 | ListPair.map 在最短列表结束后停止,而ListPair.mapEq 引起UnequalLengths 异常
| |
Swift | sequence.map(func)
|
zip(sequence1, sequence2).map(func)
|
在最短列表结束后停止 | ||
XPath 3 XQuery 3 |
list ! block for-each(list, func)
|
for-each-pair(list1, list2, func)
|
在block 上下文中项目. 持有当前值
|
在最短列表结束后停止 |
参见
- 函子 (函数式编程)
- 卷绕 (计算机科学),也叫做“conv”或“zip”
- Filter (高阶函数)
- Fold (高阶函数)
- foreach循环
- 自由幺半群
- 高阶函数
- 列表推导式
- Map (并行模式)
引用
- ^ J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959 (PDF). [2021-02-11]. (原始内容 (PDF)存档于2021-04-04).
- ^ J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958 (PDF). [2021-02-11]. (原始内容 (PDF)存档于2021-04-04).
- ^ Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp. [2021-02-11]. (原始内容存档于2020-11-12).
- ^ "Map fusion: Making Haskell 225% faster". [2021-02-11]. (原始内容存档于2013-08-06).
- ^ select clause (C# Reference) (页面存档备份,存于互联网档案馆).