Content deleted Content added
m →Language comparison: {{code}} |
|||
| (288 intermediate revisions by more than 100 users not shown) | |||
Line 1:
<references group="pakistni" />
{{Short description|Computer programming function}}
{{for|the abstract data type of the same name|Map (data structure)}}
{{one source|date=November 2012}}
In many [[programming language]]s, '''map''' is a [[higher-order function]] that applies a [[procedural parameter|given function]] to each element of a [[Collection (abstract data type)|collection]], e.g. a [[list (computing)|list]] or [[set (abstract data type)|set]], returning the results in a collection of the same type. It is often called ''apply-to-all'' when considered in [[functional form]].
The concept of a map is not limited to lists: it works for sequential [[Container (abstract data type)|containers]], tree-like containers, or even abstract containers such as [[futures and promises]].
== Examples: mapping a list ==
Suppose there is list of integers <code>[1, 2, 3, 4, 5]</code> and would like to calculate the [[Square (algebra)|square]] of each integer. To do this, first define a function to <code>square</code> a single number (shown here in [[Haskell (programming language)|Haskell]]):
<syntaxhighlight lang="haskell">
</syntaxhighlight>
Afterwards, call:
<syntaxhighlight lang="haskell">
>>> map square [1, 2, 3, 4, 5]
</syntaxhighlight>
which yields <code>[1, 4, 9, 16, 25]</code>, demonstrating that <code>map</code> has gone through the entire list and applied the function <code>square</code> to each element.
=== Visual example ===
Below, there is view of each step of the mapping process for a list of integers <code>X = [0, 5, 8, 3, 2, 1]</code> mapping into a new list <code>X'</code> according to the function <math>f(x) = x + 1</math> :
[[File:Mapping-steps-loillibe-new.gif|alt=applying map function processing steps|none|thumb|480x480px|View of processing steps when applying map function on a list]]
The <code>map</code> is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:
<syntaxhighlight lang="haskell">
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x : xs) = f x : map f xs
</syntaxhighlight>
== Generalization ==
{{see also|Functor|Category theory}}
In Haskell, the [[polymorphic function]] {{code|2=haskell|1=map :: (a -> b) -> [a] -> [b]}} is generalized to a [[polytypic function]] {{code|2=haskell|1=fmap :: Functor f => (a -> b) -> f a -> f b}}, which applies to any type belonging the [[functor (category theory)|<code>Functor</code>]] [[type class]].
The [[type constructor]] of lists <code>[]</code> can be defined as an instance of the <code>Functor</code> type class using the <code>map</code> function from the previous example:
<syntaxhighlight lang="haskell">
instance Functor [] where
fmap = map
</syntaxhighlight>
Other examples of <code>Functor</code> instances include trees:
<syntaxhighlight lang="haskell">
-- a simple binary tree
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)
</syntaxhighlight>
Mapping over a tree yields:
<syntaxhighlight lang="haskell">
>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))
Fork (Fork (Leaf 1) (Leaf 4)) (Fork (Leaf 9) (Leaf 16))
</syntaxhighlight>
For every instance of the <code>Functor</code> type class, <code>fmap</code> is [[design by contract|contractually obliged]] to obey the functor laws:
<syntaxhighlight lang="haskell">
fmap id ≡ id -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law
</syntaxhighlight>
where <code>.</code> denotes [[function composition (computer science)|function composition]] in Haskell.
Among other uses, this allows defining element-wise operations for various kinds of [[collection (computer science)|collections]].
=== Category-theoretic background ===
In [[category theory]], a [[functor]] <math>F : C \rarr D</math> consists of two maps: one that sends each object {{mvar|A}} of the category to another object {{mvar|F A}}, and one that sends each morphism <math>f : A \rarr B</math> to another morphism <math>Ff : FA \rarr FB</math>, which acts as a [[homomorphism]] on categories (i.e. it respects the category axioms). Interpreting the universe of data types as a category {{mvar|Type}}, with morphisms being functions, then a type constructor <code>F</code> that is a member of the <code>Functor</code> type class is the object part of such a functor, and {{code|2=haskell|1=fmap :: (a -> b) -> F a -> F b}} is the morphism part. The functor laws described above are precisely the category-theoretic functor axioms for this functor.
Functors can also be objects in categories, with "morphisms" called [[natural transformation]]s. Given two functors <math>F, G : C \rarr D</math>, a natural transformation <math>\eta : F \rarr G</math> consists of a collection of morphisms <math>\eta_A : FA \rarr GA</math>, one for each object {{mvar|A}} of the category {{mvar|D}}, which are 'natural' in the sense that they act as a 'conversion' between the two functors, taking no account of the objects that the functors are applied to. Natural transformations correspond to functions of the form {{code|2=haskell|1=eta :: F a -> G a}}, where <code>a</code> is a universally quantified type variable – <code>eta</code> knows nothing about the type which inhabits <code>a</code>. The naturality axiom of such functions is automatically satisfied because it is a so-called free theorem, depending on the fact that it is [[parametric polymorphism|parametrically polymorphic]].<ref>In a [[non-strict language]] that permits general recursion, such as Haskell, this is only true if the first argument to <code>fmap</code> is strict. {{cite conference |title=Theorems for free! |first=Philip |last=Wadler |author-link=Philip Wadler |conference=4th International Symposium on Functional Programming Languages and Computer Architecture |___location=London |date=September 1989 |url=https://people.mpi-sws.org/~dreyer/tor/papers/wadler.pdf |publisher=[[Association for Computing Machinery]]}}</ref> For example, {{code|2=haskell|1=reverse :: List a -> List a}}, which reverses a list, is a natural transformation, as is {{code|2=haskell|1=flattenInorder :: Tree a -> List a}}, which flattens a tree from left to right, and even {{code|2=haskell|1=sortBy :: (a -> a -> Bool) -> List a -> List a}}, which sorts a list based on a provided comparison function.
==Optimizations==
The mathematical basis of maps allow for a number of [[Optimization (computer science)|optimizations]]. The composition law ensures that both
* <code>(map f . map g) list</code> and
* <code>map (f . g) list</code>
lead to the same result; that is, <math>\operatorname{map}(f) \circ \operatorname{map}(g) = \operatorname{map}(f \circ g)</math>. However, the second form is more efficient to compute than the first form, because each <code>map</code> requires rebuilding an entire list from scratch. Therefore, compilers will attempt to transform the first form into the second; this type of optimization is known as ''map fusion'' and is the [[functional programming|functional]] analog of [[loop fusion]].<ref>[http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance "Map fusion: Making Haskell 225% faster"]</ref>
Map functions can be and often are 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>foldr f z . map g</code> is equivalent to <code>foldr (f . g) z</code>.
The implementation of map above on singly linked lists is not [[tail recursion|tail-recursive]], so it 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 (higher-order function)|fold]]-left function.
<syntaxhighlight lang="haskell">
reverseMap f = foldl (\ys x -> f x : ys) []
</syntaxhighlight>
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, though it requires performing two passes over the list.
==Language comparison==
The map function originated in [[functional programming]] languages.
The language [[Lisp (programming language)|Lisp]] introduced a map function called <code>maplist</code><ref>[http://www.softwarepreservation.org/projects/LISP/MIT/LISP_Prog_Man-Mar_1959.pdf/view J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959]</ref> in 1959, with slightly different versions already appearing in 1958.<ref>[http://www.softwarepreservation.org/projects/LISP/MIT/AIM-004.pdf/view J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958]</ref> This is the original definition for <code>maplist</code>, mapping a function over successive rest lists:
<pre>
maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]
</pre>
The function <code>maplist</code> is still available in newer Lisps like [[Common Lisp]],<ref>[http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp]</ref> though functions like <code>mapcar</code> or the more generic <code>map</code> would be preferred.
Squaring the elements of a list using <code>maplist</code> would be written in [[S-expression]] notation like this:
<syntaxhighlight lang="lisp">
(maplist (lambda (l) (sqr (car l))) '(1 2 3 4 5))
</syntaxhighlight>
Using the function <code>mapcar</code>, above example would be written like this:
<syntaxhighlight lang="lisp">
(mapcar (function sqr) '(1 2 3 4 5))
</syntaxhighlight>
Today mapping functions are supported (or may be defined) in many [[procedural programming|procedural]], [[Object-oriented programming|object-oriented]], and [[multi-paradigm]] languages as well: In [[C++]]'s [[C++ Standard Library|Standard Library]], it is called <code>std::transform</code>, in [[C Sharp (programming language)|C#]] (3.0)'s LINQ library, it is provided as an extension method called <code>Select</code>. Map is also a frequently used operation in high level languages such as [[ColdFusion Markup Language]] (CFML), [[Perl]], [[Python (programming language)|Python]], and [[Ruby (programming language)|Ruby]]; the operation is called <code>map</code> in all four of these languages. A <code>collect</code> alias for <code>map</code> 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 <code>mapcar</code> (<code>-car</code> indicating access using the [[CAR and CDR|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 function]]s 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 function]]s and [[currying]], <code>map</code> may be [[partial application|partially applied]] to ''lift'' a function that works on only one value to an element-wise equivalent that works on an entire container; for example, <code>map square</code> is a Haskell function which squares each element of a list.
{| class="wikitable" style="font-size: 85%"
|+ Map in various languages
! scope="col" | Language
! scope="col" | Map
! scope="col" | Map 2 lists
! scope="col" | Map n lists
! scope="col" | Notes
! scope="col" | Handling lists of different lengths
|- valign="top"
| [[APL (programming language)|APL]]
| <code>''func'' ''list''</code>
| <code>''list1'' ''func'' ''list2''</code>
| <code>''func''/ ''list1'' ''list2'' ''list3'' ''list4''</code>
| APL's array processing abilities make operations like map implicit
| length error if list lengths not equal or 1
|- valign="top"
| [[Common Lisp]]
| <code>(mapcar ''func'' ''list'')</code>
| <code>(mapcar ''func'' ''list1'' ''list2'')</code>
| <code>(mapcar ''func'' ''list1'' ''list2'' ...)</code>
|
| stops after the length of the shortest list
|- valign="top"
| [[C++]]
| <code>std::transform(<wbr/>''begin'', ''end'', ''result'', ''func'')</code>
| <code>std::transform(<wbr/>''begin1'', ''end1'', ''begin2'', ''result'', ''func'')</code>
|
| in header {{mono|<algorithm>}}<br /> ''begin'', ''end'', and ''result'' are iterators<br /> result is written starting at ''result''
|
|- valign="top"
| [[C Sharp (programming language)|C#]]
| <code>''ienum''.Select(''func'')</code><br />or<br />[https://msdn.microsoft.com/en-us/library/bb384087.aspx The <code>select</code> clause]
| <code>''ienum1''.Zip(''ienum2'', ''func'')</code>
|
| <code>Select</code> is an extension method<br /> ''ienum'' is an IEnumerable<br /><code>Zip</code> is introduced in .NET 4.0<br />Similarly in all .NET languages
| stops after the shortest list ends
|- valign="top"
| [[CFML]]
| <code>obj.map(func)</code>
|
|
| Where <code>obj</code> is an array or a structure. <code>func</code> receives as arguments each item's value, its index or key, and a reference to the original object.
|
|- valign="top"
| [[Clojure]]
| <code>(map ''func'' ''list'')</code>
| <code>(map ''func'' ''list1'' ''list2'')</code>
| <code>(map ''func'' ''list1'' ''list2'' ...)</code>
|
| stops after the shortest list ends
|- valign="top"
| [[D (programming language)|D]]
| <code>''list''.map!''func''</code>
| <code>zip(''list1'', ''list2'').map!''func''</code>
| <code>zip(''list1'', ''list2'', ...).map!''func''</code>
|
| Specified to zip by StoppingPolicy: shortest, longest, or requireSameLength
|- valign="top"
| [[Erlang (programming language)|Erlang]]
| <code>lists:map(''Fun'', ''List'')</code>
| <code>lists:zipwith(''Fun'', ''List1'', ''List2'')</code>
| <code>''zipwith3''</code> also available
|
| Lists must be equal length
|- valign="top"
| [[Elixir (programming language)|Elixir]]
| <code>Enum.map(''list'', ''fun'')</code>
| <code>Enum.zip(''list1'', ''list2'') |> Enum.map(fun)</code>
| <code>List.zip([''list1'', ''list2'', ...]) |> Enum.map(fun)</code>
|
| stops after the shortest list ends
|- valign="top"
| [[F sharp (programming language)|F#]]
| <code>List.map ''func'' ''list''</code>
| <code>List.map2 ''func'' ''list1'' ''list2''</code>
|
| Functions exist for other types (''Seq'' and ''Array'')
| Throws exception
|- valign="top"
| [[Gleam (programming language)|Gleam]]
| <code>list.map(''list'', ''func'')</code><br><code>yielder.map(''yielder'', ''func'')</code>
| <code>list.map2(''list1'', ''list2'', ''func'')</code><br><code>yielder.map2(''yielder1'', ''yielder2'', ''func'')</code>
|
|
| drops the extra elements of the longer list
|- valign="top"
| [[Groovy (programming language)|Groovy]]
| {{code|list.collect(func)|groovy}}
| {{code|[list1 list2].transpose().collect(func)|groovy}}
| {{code|[list1 list2 ...].transpose().collect(func)|groovy}}
|
|
|- valign="top"
| [[Haskell (programming language)|Haskell]]
| <code>map ''func'' ''list''</code>
| <code>zipWith ''func'' ''list1'' ''list2''</code>
| <code>zipWith''n'' ''func'' ''list1'' ''list2'' ...</code>
| <code>''n''</code> corresponds to the number of lists; predefined up to <code>''zipWith7''</code>
| stops after the shortest list ends
|- valign="top"
| [[Haxe]]
| <code>''array''.map(''func'')<br />''list''.map(''func'')<br />Lambda.map(''iterable'', ''func'')</code>
|
|
|
|
|- valign="top"
| [[J (programming language)|J]]
| <code>''func'' ''list''</code>
| <code>''list1'' ''func'' ''list2''</code>
| <code>''func''/ ''list1'', ''list2'', ''list3'' ,: ''list4''</code>
| J's array processing abilities make operations like map implicit
| length error if list lengths not equal
|- valign="top"
| [[Java (programming language)|Java]] 8+
| <code>''stream''.map(''func'')</code>
|
|
|
|
|- valign="top"
| [[JavaScript]] 1.6<br />[[ECMAScript]] 5
| [https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/map <code>''array''#map(''func'')</code>]
| <code>''List1''.map(function (elem1, i) { <br />return ''func''(elem1, ''List2''[i]); })</code>
| <code>''List1''.map(function (elem1, i) { <br />return ''func''(elem1, ''List2''[i], ''List3''[i], ...); })</code>
| Array#map passes 3 arguments to ''func'': the element, the index of the element, and the array. Unused arguments can be omitted.
| Stops at the end of ''List1'', extending the shorter arrays with ''undefined'' items if needed.
|- valign="top"
| [[Julia (programming language)|Julia]]
| <code>map(''func'', ''list'')</code>
| <code>map(''func'', ''list1, list2'')</code>
| <code>map(''func'', ''list1, list2, ..., listN'')</code>
|
| ERROR: DimensionMismatch
|- valign="top"
| [[Logtalk]]
| <code>map(''Closure'', ''List'')</code>
| <code>map(''Closure'', ''List1'', ''List2'')</code>
| <code>map(''Closure'', ''List1'', ''List2'', ''List3'', ...) (up to seven lists)</code>
| Only the ''Closure'' argument must be instantiated.
| Failure
|- valign="top"
| [[Mathematica]]
| <code>''func'' /@ ''list'' <br /> Map[''func'', ''list'']</code>
| <code>MapThread[''func'', {''list1'', ''list2''}]</code>
| <code>MapThread[''func'', {''list1'', ''list2'', ...}]</code>
|
| Lists must be same length
|- valign="top"
| [[Maxima (software)|Maxima]]
| <code>map(''f'', ''expr<sub>1</sub>'', ..., ''expr<sub>n</sub>'')<br />maplist(''f'', ''expr<sub>1</sub>'', ..., ''expr<sub>n</sub>'')</code>
|
|
| map returns an expression which leading operator is the same as that of the expressions;<br />maplist returns a list
|
|- valign="top"
| [[OCaml]]
| <code>List.map ''func'' ''list''<br /> Array.map ''func'' ''array''</code>
| <code>List.map2 ''func'' ''list1'' ''list2''</code>
|
|
| raises Invalid_argument exception
|- valign="top"
| [[PARI/GP]]
| <code>apply(''func'', ''list'')</code>
|
|
|
| {{n/a}}
|- valign="top"
| [[Perl]]
| <code>map ''block'' ''list''<br /> map ''expr'', ''list''</code>
|
|
| In ''block'' or ''expr'' special variable ''$_'' holds each value from list in turn.
| Helper <code>''List::MoreUtils::each_array''</code> combines more than one list until the longest one is exhausted, filling the others with <code>''undef''.</code>
|- valign="top"
| [[PHP]]
| <code>array_map(''callable'', ''array'')</code>
| <code>array_map(''callable'', ''array1'',''array2'')</code>
| <code>array_map(''callable'', ''array1'',''array2'', ...)</code>
| The number of parameters for ''callable''<br />should match the number of arrays.
| extends the shorter lists with ''NULL'' items
|- valign="top"
| [[Prolog]]
| <code>maplist(''Cont'', ''List1'', ''List2'').</code>
| <code>maplist(''Cont'', ''List1'', ''List2'', ''List3'').</code>
| <code>maplist(''Cont'', ''List1'', ''...'').</code>
| List arguments are input, output or both. Subsumes also zipWith, unzip, all
| Silent failure (not an error)
|- valign="top"
| [[Python (programming language)|Python]]
| <code>map(''func'', ''list'')</code>
| <code>map(''func'', ''list1'', ''list2'')</code>
| <code>map(''func'', ''list1'', ''list2'', ...)</code>
| Returns a list in Python 2 and an [[iterator]] in Python 3.
| <code>''zip()''</code> and <code>''map()''</code> (3.x) stops after the shortest list ends, whereas <code>''map()''</code> (2.x) and <code>''itertools.zip_longest()''</code> (3.x) extends the shorter lists with <code>''None''</code> items
|- valign="top"
| [[Ruby (programming language)|Ruby]]
| <code>''enum''.collect {''block''}<br /> ''enum''.map {''block''}</code>
| <code>''enum1''.zip(''enum2'')<wbr/>.map {''block''}</code>
| <code>''enum1''.zip(''enum2'', ...)<wbr/>.map {''block''} <br /> [''enum1'', ''enum2'', ...]<wbr/>.transpose.map {''block''}</code>
| <code>''enum'' is an Enumeration</code>
| 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
|-
|[[Rust (programming language)|Rust]]
| <code>''list1''.into_iter().map(''func'')</code>
| <code>''list1''.into_iter().zip(''list2'').map(''func'')</code>
|
| the <code>Iterator::map</code> and <code>Iterator::zip</code> methods both take ownership of the original iterator and return a new one; the <code>Iterator::zip</code> method internally calls the <code>IntoIterator::into_iter</code> method on <code>''list2''</code>
| stops after the shorter list ends
|- valign="top"
| [[S (programming language)|S]]-[[R (programming language)|R]]
| <code>lapply(''list'', ''func'')</code>
| <code>mapply(''func'', ''list1'', ''list2'')</code>
| <code>mapply(''func'', ''list1'', ''list2'', ...)</code>
|
| Shorter lists are cycled
|- valign="top"
| [[Scala (programming language)|Scala]]
| <code>''list''.map(''func'')</code>
| <code>(''list1'', ''list2'')<wbr/>.zipped.map(''func'')</code>
| <code>(''list1'', ''list2'', ''list3'')<wbr/>.zipped.map(''func'')</code>
| note: more than 3 not possible.
| stops after the shorter list ends
|- valign="top"
| [[Scheme (programming language)|Scheme]] (including [[Guile (programming language)|Guile]] and [[Racket (programming language)|Racket]])
| <code>(map ''func'' ''list'')</code>
| <code>(map ''func'' ''list1'' ''list2'')</code>
| <code>(map ''func'' ''list1'' ''list2'' ...)</code>
|
| lists must all have same length (SRFI-1 extends to take lists of different length)
|- valign="top"
| [[Smalltalk]]
| <code>''aCollection'' collect: ''aBlock''</code>
| <code>''aCollection1'' with: ''aCollection2'' collect: ''aBlock''</code>
|
|
| Fails
|- valign="top"
| [[Standard ML]]
| <code>map ''func'' ''list''</code>
| <code>ListPair.map ''func'' (''list1'', ''list2'') <br /> ListPair.mapEq ''func'' (''list1'', ''list2'')</code>
|
| For 2-argument map, ''func'' takes its arguments in a tuple
| <code>''ListPair.map''</code> stops after the shortest list ends, whereas <code>''ListPair.mapEq''</code> raises <code>UnequalLengths</code> exception
|- valign="top"
| [[Swift (programming language)|Swift]]
| <code>''sequence''.map(''func'')</code>
| <code>zip(''sequence1'', ''sequence2'').map(''func'')</code>
|
|
| stops after the shortest list ends
|- valign="top"
| [[XPath 3]]<br />[[XQuery]] 3
| {{code|list ! block|xquery}}<br /> {{code|for-each(list, func)|xquery}}
| {{code|for-each-pair(list1, list2, func)|xquery}}
|
| In <code>block</code> the context item <code>.</code> holds the current value
| stops after the shortest list ends
|}
==See also==
* [[Functor (functional programming)]]
* [[Zipping (computer science)]] or zip, mapping 'list' over multiple lists
* [[Filter (higher-order function)]]
* [[Fold (higher-order function)]]
* [[foreach loop]]
* [[Free monoid]]
* [[Functional programming]]
* [[Higher-order function]]
* [[List comprehension]]
* [[Map (parallel pattern)]]
==References==
{{Reflist}}
[[Category:Higher-order functions]]
[[Category:Programming language comparisons]]
[[Category:Articles with example Haskell code]]
[[Category:Iteration in programming]]
| |||