Map (higher-order function)
From Wikipedia, the free encyclopedia
In many programming languages, map is the name of a higher-order function that applies a given function to a sequence of elements (such as a list) and returns a sequence of results. They are examples of both catamorphisms and anamorphisms. This is often called apply-to-all when considered a functional form.
For example, if we define a function square as follows:
square x = x * x
Then calling map square [1,2,3,4,5] will return [1,4,9,16,25].
Map itself may be defined recursively, like this Haskell code:
map f [] = [] map f (x:xs) = f x : map f xs
Contents |
[edit] Language comparison
The map function originated in functional programming languages but is today supported (or may be defined) in many procedural, object oriented, and multi-paradigm languages as well: In C++'s Standard Template Library, it is called transform, in C# (3.0), it is provided as an extension method called Select. Map is also a frequently used operation in scripting languages such as Perl, Python and Ruby; the operation is called map in Perl and Python and collect in Ruby (from Smalltalk). Common Lisp provides a family of map-like functions; the one corresponding to the behavior described here is called mapcar (-car indicating access using the CAR operation). There are also languages with syntactic constructs providing the same functionality as the map function.
Map is sometimes generalized to accept dyadic (2-argument) functions that can apply a user-supplied function to corresponding elements from two lists; some languages use special names for this, such as map2 or zipWith. Languages using explicit variadic functions may have versions of map with variable arity to support variable-arity functions.
| Language | Map | Map 2 lists | Map n lists | Notes |
|---|---|---|---|---|
| Haskell | map func list [func x | x <- list] |
zipWith func list1 list2 | ||
| OCaml | List.map func list Array.map func array |
List.map2 func list1 list2 | ||
| Standard ML | map func list | ListPair.map func (list1, list2) | The supplied function takes its arguments in a tuple. | |
| Python | map(func, list) [func(x) for x in list] |
map(func, list1, list2) [func(x, y) for x, y in zip(list1, list2)] |
map(func, list1, list2, ...) [func(*xs) for xs in zip(list1, list2, ...)] |
|
| 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 |
| C++ | std::transform(begin, end, result, func) | std::transform(begin1, end1, begin2, result, func) | in header <algorithm> begin, end, & result are iterators result is written starting at result |
|
| Perl | map block list map expr, list |
|||
| C# 3.0 | ienum.Select(func) | Select is an extension method ienum is an IEnumerable Similarly in all .NET languages |
||
| JavaScript 1.6 | array.map(func) | |||
| Common Lisp | (mapcar func list) | (mapcar func list1 list2) | (mapcar func list1 list2 ...) | |
| Scheme | (map func list) | (map func list1 list2) | (map func list1 list2 ...) | |
| Smalltalk | aCollection collect: aBlock | aCollection1 with: aCollection2 collect: aBlock | ||
| Erlang | lists:map(Fun, List) | lists:zipwith(Fun, List1, List2) | ||
| PHP | array_map(callback, array) | array_map(callback, array1,array2) | array_map(callback, array1,array2, ...) | The number of parameters for callback should match the number of arrays. |
| Mathematica | func /@ list Map[func, list] |
MapThread[func, {list1, list2}] | MapThread[func, {list1, list2, ...}] | |
| Maxima | map(f, expr1, ..., exprn) maplist(f, expr1, ..., exprn) |
map returns an expression whose leading operator is the same as that of the expressions; maplist returns a list |
||
| S/R | lapply(list,func) | mapply(func,list1,list2) | mapply(func,list1,list2,...) |
[edit] Optimizations
The mathematical basis of maps allow for a number of optimizations. If one has (map f . map g) xs ('.' is function composition) then it is the same as the simpler map (f . g) xs; that is, 
. This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion"[1].
Map functions can be and often are defined in terms of a fold such as foldr, which means one can do a "map-fold fusion": foldr f z . map g is equivalent to foldr (f . g) z.
The implementation of map above on singly-linked lists is not tail-recursive, so may build up a lot of frames on the stack when called with a large list. Many languages alternately provide a "reverse map" function, which is equivalent to reversing a mapped list, but is tail-recursive. Here is an implementation which utilizes the fold-left function.
rev_map f = foldl (\ys x -> f x : ys) []
Since reversing a singly-linked list is also tail-recursive, reverse and reverse-map can be composed to perform normal map in a tail-recursive way.
[edit] Haskell's Functor class
In the Haskell programming language, map is generalized to a polymorphic function called fmap using the Functor type class. For every Functor instance, fmap must be defined such that it obeys the Functor laws (see also functor in category theory):
fmap id = id -- identityfmap (f . g) = fmap f . fmap g -- composition
