Map (higher-order function): Difference between revisions

Revision as of 22:24, 25 February 2025

Latest revision as of 06:20, 8 August 2025

(2 intermediate revisions by 2 users not shown)

Line 41:

{{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 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 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 380 ⟶ 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