Map (higher-order function)

Map (higher-order function)

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a list, returning a list 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], as map will go through the list, and apply the function square to each element.

Contents

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 high level languages such as Perl, Python and Ruby; the operation is called map in all three of these languages. A collect alias for map is also provided 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 with 2 or more lists encounters the issue of handling when the lists are of different lengths. Various languages differ on this; some raise an exception, some stop after the length of the shortest list and ignore extra items on the other lists; some continue on to the length of the longest list, and for the lists that have already ended, pass some placeholder value to the function indicating no value.

In languages which support first-class functions, map may be partially applied to "lift" functions to element-wise versions; for instance, map square is a Haskell function which squares lists element-wise.

Map in various languages
Language Map Map 2 lists Map n lists Notes Handling lists of different lengths
Haskell map func list zipWith func list1 list2 zipWithn func list1 list2 ... n corresponds to the number of lists; predefined up to zipWith7 stops after the shortest list ends
haXe Lambda.map(iterable, func)
J func list list func list func/ list1 , list2 , list3 ,: list4 J's array processing capabilities make operations like map implicit length error if lists not equal
OCaml List.map func list
Array.map func array
List.map2 func list1 list2 raises Invalid_argument exception
Standard ML map func list ListPair.map func (list1, list2)
ListPair.mapEq func (list1, list2)
For 2-argument map, func takes its arguments in a tuple ListPair.map stops after the shortest list ends, whereas ListPair.mapEq raises UnequalLengths exception
Python map(func, list) map(func, list1, list2) map(func, list1, list2, ...) zip() and map() (3.x) stops after the shortest list ends, whereas map() (2.x) and itertools.zip_longest() (3.x) extends the shorter lists with None items
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 stops at the end of the object it is called on (the first list); if any other list is shorter, it is extended with nil items
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
In block or expr special variable $_ holds each value from list in turn. N/A
C# 3.0 ienum.Select(func) Select is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
C# 4.0 ienum.Select(func) ienum1.Zip(ienum2, func) Select is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
stops after the shortest list ends
JavaScript 1.6 array.map(func)
Common Lisp (mapcar func list) (mapcar func list1 list2) (mapcar func list1 list2 ...) stops after the length of the shortest list
Scheme, Clojure (map func list) (map func list1 list2) (map func list1 list2 ...) Stops after the shortest list ends
Smalltalk aCollection collect: aBlock aCollection1 with: aCollection2 collect: aBlock Fails
Erlang lists:map(Fun, List) lists:zipwith(Fun, List1, List2) zipwith3 also available Lists must be equal length
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.
extends the shorter lists with NULL items
Prolog maplist(Cont, List1, List2). maplist(Cont, List1, List2, List3). maplist(Cont, List1, ...). List arguments are input, output or both. Subsumes unzip, all Failure
Mathematica func /@ list
Map[func, list]
MapThread[func, {list1, list2}] MapThread[func, {list1, list2, ...}] Lists must be same length
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,...) Shorter lists are cycled
Scala list.map(func) (list1, list2).zipped.map(func) (list1, list2,"list3").zipped.map(func) note: more than 3 not possible. stops after the shorter list ends

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.

Generalization

In the Haskell programming language, the polymorphic map  :: (a -> b) -> ([a] -> [b]) is generalized to a polytypic function called fmap :: Functor f => (a -> b) -> (f a -> f b) which applies to any type in the Functor class.

map is used in Haskell's Prelude to define the list type constructor [] an instance of the Functor class as follows

  instance Functor [] where fmap = map

But trees may belong to Functor too, for example:

 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 (1+) (Fork(Fork(Leaf 0)(Leaf 1))(Fork(Leaf 2)(Leaf 3)))

evaluates to:

 Fork (Fork(Leaf 1)(Leaf 2))(Fork(Leaf 3)(Leaf 4))

For every instance of the Functor type class, fmap must be defined such that it obeys the functor laws:

  • fmap id = id -- identity
  • fmap (f . g) = fmap f . fmap g -- composition

Among other uses, this allows defining element-wise operations for other kind of collections.


Moreover, if F and G are two functors, a natural transformation is a function of polymorphic type h: \, \forall T.\, F \, T \rarr G \, T which respects fmap:

h_{Y} \circ (\mathrm{fmap} \, k) = (\mathrm{fmap} \, k) \circ h_{X} for any function k: X \rarr Y.

If the h function is defined by parametric polymorphism as in the type definition above, this specification is always satisfied.

References

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

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Fold (higher-order function) — In functional programming, fold, also known variously as reduce, accumulate, compress or inject, is a family of higher order functions that process a data structure in some order and build up a return value. Typically, a fold deals with two… …   Wikipedia

  • Filter (higher-order function) — In functional programming, filter is a higher order function that processes a data structure (typically a list) in some order to produce a new data structure containing exactly those elements of the original data structure for which a given… …   Wikipedia

  • Higher-order function — In mathematics and computer science, higher order functions or functionals are functions which do at least one of the following: *take one or more functions as an input *output a function.In mathematics these are also known as operators or… …   Wikipedia

  • map (C++) — Not to be confused with Map (higher order function). C++ Standard Library fstream iomanip ios iostream sstre …   Wikipedia

  • Map (disambiguation) — Contents 1 Mathematics and Programming 2 Science 3 Television, film, and music …   Wikipedia

  • Function composition — For function composition in computer science, see function composition (computer science). g ∘ f, the composition of f and g. For example, (g ∘ f)(c) = #. In mathematics, function composition is the application of one function to the resul …   Wikipedia

  • Function space — In mathematics, a function space is a set of functions of a given kind from a set X to a set Y . It is called a space because in many applications, it is a topological space or a vector space or both. ExamplesFunction spaces appear in various… …   Wikipedia

  • Map — /map/, n. Walter, c1140 1209?, Welsh ecclesiastic, poet, and satirist. Also, Mapes /mayps, may peez/. * * * I Graphic representation, drawn to scale and usually on a flat surface, of features usually geographic, geologic, or geopolitical of an… …   Universalium

  • map — mappable, adj. mapper, n. /map/, n., v., mapped, mapping. n. 1. a representation, usually on a flat surface, as of the features of an area of the earth or a portion of the heavens, showing them in their respective forms, sizes, and relationships… …   Universalium

  • MAP — See modified American plan. * * * I Graphic representation, drawn to scale and usually on a flat surface, of features usually geographic, geologic, or geopolitical of an area of the Earth or of any celestial body. Globes are maps represented on… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”