Map (higher-order function)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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


[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.

Map in various languages
Language Map Map 2 lists Map n lists Notes
Haskell map func list
[func x | x <- list]
zipWith func list1 list2
OCaml func list func array
List.map2 func list1 list2
Standard ML map func list 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} {block} {block}, ...).map {block}
[enum1, enum2, ...] {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
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, \left( \text{map}\,f \right) \circ \left( \text{map}\,g \right) = \text{map}\,\left( f \circ g \right). 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 -- identity
  • fmap (f . g) = fmap f . fmap g -- composition

[edit] References

  1. ^ "Map fusion: Making Haskell 225% faster"

[edit] See also

Personal tools