Misplaced Pages

This is an old revision of this page, as edited by Jarble (talk | contribs) at 02:54, 6 June 2013 (Actually, this article contains just one inline citation.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Map" higher-order function – news · newspapers · books · scholar · JSTOR (November 2012)

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. It is often called apply-to-all when considered in functional form. This is an example of homomorphism.

For example, if we define a function square as follows:

square y = x * x

Then calling map square will return , as map will go through the list and apply the function square to each element.

Generalization

In the Haskell programming language, the polymorphic map  :: (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 ${\displaystyle F}$ and ${\displaystyle G}$ are two functors, a natural transformation is a function of polymorphic type ${\displaystyle h:\,\forall T.\,F\,T\rightarrow G\,T}$ which respects fmap:

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

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

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, ${\displaystyle \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".

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.

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)'s LINQ library, 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.

See also

• Filter (higher-order function)
• List comprehension
• foreach
• Fold (higher-order function)
• Convolution (computer science), (also known as conv or zip)
• Free monoid
• MapReduce

References

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

• Higher-order functions
• Programming language comparisons