Map (higher-order function): Difference between revisions

Revision as of 06:36, 5 August 2020

Latest revision as of 06:20, 8 August 2025

(25 intermediate revisions by 21 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 (disambiguationabstract data 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 121 ⟶ 124:

</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 TemplateLibrary|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.

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

* [[Convolution (computer science)]], also termed ''conv'' or ''zip''

* [[Zipping (computer science)]] or zip, mapping 'list' over multiple lists

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

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

* [[foreach loop]]

* [[Free monoid]]

* [[Functional programming]]