Map (higher-order function): Difference between revisions

Revision as of 11:09, 9 June 2024

Latest revision as of 06:20, 8 August 2025

(5 intermediate revisions by 5 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)}}

Line 7 ⟶ 8:

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 15 ⟶ 16:

</syntaxhighlight>

Afterwards we may, call:

Afterwards we may call

<syntaxhighlight lang="haskell">

Line 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 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 79:

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

Line 90:

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

Map functions can be and often

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

Line 158 ⟶ 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 209 ⟶ 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 381 ⟶ 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