Content deleted Content added
«+"They are examples of both catamorphisms and anamorphisms. <!-- ex, map f = foldr ((:) . f) [] -->", "1,2,3,4,5" → "[1,2,3,4,5]", "1,4,9,16,25" → "[1,4,9,16,25]", "behaviour" → "behavior", +"==Optimizations== Becaus", " See also " |
|||
Line 1:
In many [[programming language]]s, '''map''' is the name of a [[higher-order function]] that applies a [[Procedural parameter|given function]] to a sequence of elements (such as a [[linked list|list]]) and returns a sequence of results. They are examples of both [[catamorphism]]s and [[anamorphism]]s. <!-- ex, map f = foldr ((:) . f) [] -->
For example, if we define a function <code>square</code> as follows:
Line 9:
Map itself may be defined recursively as:
map f []
map f (x:xs)
==Language comparison==
The map function is especially common in [[functional programming]] languages, but some [[high-level programming language|high-level]] [[procedural programming|procedural]] languages support it as well, and in others it may be defined. [[Common Lisp]] provides a whole family of map-like functions. The one that corresponds to the
==Optimizations==
The mathematical basis of maps allow for a number of optimizations. If one has <code>map f . map g</code> ('.' is function application; <code>map f (map g xs)</code> is equivalent) then it is the same as the simpler <code>map (f . g)</code>; this particular simplification and optimization is a "map fusion". Maps can be defined in terms of a [[Fold (higher-order function)|fold]] such as <code>foldr</code>, which means one can do a "map-fold fusion": <code>f z . map g</code> is equivalent to <code>foldr (f . g) z</code>.
▲The map function is especially common in [[functional programming]] languages, but some [[high-level programming language|high-level]] [[procedural programming|procedural]] languages support it as well, and in others it may be defined. [[Common Lisp]] provides a whole family of map-like functions. The one that corresponds to the behaviour described here is called <code>mapcar</code>. In [[C++]]'s [[Standard Template Library]], the map function is called <code>transform</code>.
==Haskell's Functor class==
In the [[Haskell (programming language)|Haskell programming language]], map is generalized to a [[Type polymorphism|polymorphic]] function called fmap using the Functor [[type class]]. For every Functor instance, fmap must be defined such that it obeys the Functor laws:
* <code>fmap id = id (identity)
* <code>fmap (f . g) = fmap f . fmap g (composition)</code>
==
* [[List comprehension]]
| |||