Map (higher-order function): Difference between revisions

Revision as of 00:12, 28 May 2021

Latest revision as of 06:20, 8 August 2025

(19 intermediate revisions by 16 users not shown)

Line 1:

<references group="pakistni" />

{{for|the similarly-titled abstract data type composed of (key,value) pairs|Associative array}}

{{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 the name of a [[higher-order function]] that applies a [[procedural parameter|given function]] to each element of a [[FunctorCollection (functionalabstract programmingdata type)|functorcollection]], e.g. a [[list (computing)|list]], returningor a[[set list(abstract ofdata type)|set]], returning the results in a collection of the same ordertype. 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 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">

Line 14 ⟶ 16:

</syntaxhighlight>

Afterwards we may, call:

<syntaxhighlight lang="haskell">

Line 23 ⟶ 25:

=== 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]]

Line 35 ⟶ 37:

</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:

Line 75 ⟶ 77:

Among other uses, this allows defining element-wise operations for various kinds of [[collection (computer science)|collections]].

=== Category-theoretic background ===

Moreover, if {{math|''F''}} and {{math|''G''}} are two functors, a [[natural transformation]] is a function of polymorphic type <math>h : \forall T . F(T) \to G(T)</math> which respects {{math|fmap}}:

: <math>h_Y \circ \operatorname{fmap}(f) = \operatorname{fmap}(f) \circ h_X</math> for any function <math>f : X \to Y</math>.

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.

If the {{math|''h''}} function is defined by [[parametric polymorphism]] as in the type definition above, this specification is always satisfied.

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==

Line 129 ⟶ 132:

{| class="wikitable" style="font-size: 85%"

|+ Map in various languages

! scope="col" | Language

! Language !! Map !! Map 2 lists !! Map n lists !! Notes !! Handling lists of different lengths

! 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]]

Line 149 ⟶ 157:

| <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"

Line 200 ⟶ 208:

| 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}}

|

|

Line 216 ⟶ 231:

|- valign="top"

| [[Haxe]]

| <code>''array''.map(''func'')<br />''list''.map(''func'')<br />Lambda.map(''iterable'', ''func'')</code>

''list''.map(''func'')<br />

Lambda.map(''iterable'', ''func'')

</code>

|

|

Line 375 ⟶ 387:

|- 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

Line 383 ⟶ 395:

==See also==

* [[Functor (functional programming)]]

* [[ConvolutionZipping (computer science)]] or zip, alsomapping termed ''conv'list' orover ''zip''multiple lists

* [[Filter (higher-order function)]]

* [[Fold (higher-order function)]]

* [[foreach loop]]

* [[Free monoid]]

* [[Functional programming]]