|
<references group="pakistni" />
{{Short description|Computer programming function}}
{{for|the abstract data type of the same name|Map (data structure)}}
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 wethere have ais 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, we first define a function to <code>square</code> a single number (shown here in [[Haskell (programming language)|Haskell]]):
<syntaxhighlight lang="haskell">
</syntaxhighlight>
Afterwards we may, call:
<syntaxhighlight lang="haskell">
=== Visual example ===
Below, youthere can see ais view of each step of the mapping process for a list of integers <code>X = [0, 5, 8, 3, 2, 1]</code> that we want to mapmapping 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]]
</syntaxhighlight>
== Generalization ==
{{see also|Functor|Category theory}}
In Haskell, the [[polymorphic function]] <{{code>|2=haskell|1=map :: (a -> b) -> [a] -> [b]</code>}} is generalized to a [[polytypic function]] <{{code>|2=haskell|1=fmap :: Functor f => (a -> b) -> f a -> f b</code>}}, 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:
=== Category-theoretic background ===
In [[category theory]], a [[functor]] <math>F : C \rarr D</math> consists of two maps: one that sends each object <math>{{mvar|A</math>}} of the category to another object <math>{{mvar|F A</math>}}, 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 <math>{{mvar|Type</math>}}, 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</code>}} 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 <math>{{mvar|A</math>}} of the category <math>{{mvar|D</math>}}, 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</code>}}, 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</code>}}, which reverses a list, is a natural transformation, as is <{{code>|2=haskell|1=flattenInorder :: Tree a -> List a</code>}}, which flattens a tree from left to right, and even <{{code>|2=haskell|1=sortBy :: (a -> a -> Bool) -> List a -> List a</code>}}, which sorts a list based on a provided comparison function.
==Optimizations==
| <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"
| 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)</code>|groovy}}
| <{{code>|[list1 list2]<wbr>.transpose()<wbr>.collect(func)</code>|groovy}}
| <{{code>|[list1 list2 ...]<wbr>.transpose()<wbr>.collect(func)</code>|groovy}}
|
|
|- valign="top"
| [[XPath 3]]<br />[[XQuery]] 3
| <{{code>|list ! block</code>|xquery}}<br /> <{{code>|for-each(list, func)</code>|xquery}}
| <{{code>|for-each-pair(list1, list2, func)</code>|xquery}}
|
| In <code>block</code> the context item <code>.</code> holds the current value
* [[Filter (higher-order function)]]
* [[Fold (higher-order function)]]
* [[foreach loop]]
* [[Free monoid]]
* [[Functional programming]]
| 