Map (higher-order function): Difference between revisions

Revision as of 19:23, 28 October 2015

Revision as of 00:48, 24 January 2016

Line 1:

{{one source|date=November 2012}}

In many [[programming language]]s, '''map''' is the name of a [[higher-order function]] that applies a given [[Procedural parameter|function]] to each element of a [[list (computing)|list]], returning a list of results. It is often called ''apply-to-all'' when considered in [[functional form]]. <!-- This is an example of [[functor]]iality. ex, map f = foldr ((:) . f) [] -->

In many [[programming language]]s, '''map''' is the name of a [[higher-order function]] that applies a given [[Proceduralprocedural parameter|given function]] to each element of a [[list (computing)|list]], returning a list of results in the same order. It is often called ''apply-to-all'' when considered in [[functional form]]. <!-- This is an example of [[functor]]iality. ex, map f = foldr ((:) . f) [] -->

==Example==

For example, if we define in [[Haskell (programming language)|Haskell]] a function <code>square</code> as follows:

The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as [[futures and promises]].

==Example: mapping a list ==

Suppose we have a list of integers <code>[1, 2, 3, 4, 5]</code> and would like to calculate the 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]]):

<source lang="haskell">

Line 9 ⟶ 13:

</source>

Afterwards we may call

Then calling <code>map square [1,2,3,4,5]</code> will return <code>[1,4,9,16,25]</code>, as <code>map</code> will go through the list and apply the function <code>square</code> to each element.

<source lang="haskell">

>>> map square [1, 2, 3, 4, 5]

</source>

which yields <code>[1, 4, 9, 16, 25]</code>, demonstrating that <code>map</code> has gone through the entire list and applied the function <code>square</code> to each element. The <code>map</code> is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:

<source lang="haskell">

map :: (a -> b) -> [a] -> [b]

map _ [] = []

map f (x : xs) = f x : map f xs

</source>

==Generalization==

{{see also|Functor|Category theory}}

In the [[Haskell (programming language)|Haskell programming language]], the [[Type polymorphism|polymorphic]] function &nbsp;<code>map :: (a -> b) -> [a] -> [b]</code> is generalized to a [[Polytypic function|polytypic]] function called <code>fmap :: Functor f => (a -> b) -> f a -> f b</code>, which applies to any type in the [[functor (category theory)|<code>Functor</code>]] class.

In the [[Haskell (programming language)|Haskell programming language]], the [[Typepolymorphic polymorphism|polymorphicfunction]] function &nbsp;<code>map :: (a -> b) -> [a] -> [b]</code> is generalized to a [[Polytypicpolytypic function|polytypic]] function called <code>fmap :: Functor f => (a -> b) -> f a -> f b</code>, which applies to any type inbelonging the [[functor (category theory)|<code>Functor</code>]] [[type class]].

''map'' is used in Haskell's Prelude to define the list type constructor (<code>[]</code>) an instance of the <code>Functor</code> type class as follows

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:

<source lang="haskell">

instance Functor [] where
fmap = map

</source>

ButOther treesexamples may belong toof <code>Functor</code> too,instances forinclude exampletrees:

<source lang="haskell">

-- a simple binary tree

data Tree a = Leaf a | Fork (Tree a) (Tree a)

instance Functor Tree where

fmap f (Leaf x) = Leaf (f x)

fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

instance Functor Tree where

fmap (1+) (Fork(Fork(Leaf 0)(Leaf 1))(Fork(Leaf 2)(Leaf 3)))

fmap f (Leaf x) = Leaf (f x)

fmap f (Fork l r) = Fork (fmap f l) (fmap f r)

</source>

evaluates to:

Mapping over a tree yields:

<source lang="haskell">

>>> fmap square (Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Leaf 4)))

fmapFork (1+)Fork (Fork(Fork(Leaf 01) (Leaf 14)) (Fork (Leaf 29) (Leaf 3)16))

</source>

For every instance of the <code>Functor</code> [[type class]], <code>fmap</code> is expected[[design toby becontract|contractually definedobliged]] such that itto obeysobey the functor laws:

<source lang="haskell">

fmap id = ≡ id -- identity law

fmap (f . g) =≡ fmap f . fmap g -- composition law

</source>

where <code>.</code> denotes [[function composition (computer science)|function composition]] in Haskell.

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

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

: <math>h_{Y}h_Y \circ (\mathrmoperatorname{fmap} \, k(f) = (\mathrmoperatorname{fmap} \, k(f) \circ h_{X}h_X</math> for any function <math>kf : X \rarrto Y</math>.

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

==Optimizations==

The mathematical basis of maps allow for a number of [[Optimization (computer science)|optimizations]]. If one has <code>(map f . map g) xs</code> ('.' is [[function composition (computer science)|function composition]]) then it is the same as the simpler <code>map (f . g) xs</code>; that is,

<math>\left( \text{map}\,f \right) \circ \left( \text{map}\,g \right) = \text{map}\,\left( f \circ g \right)</math>. This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion".<ref>[http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance "Map fusion: Making Haskell 225% faster"]</ref>

The mathematical basis of maps allow for a number of [[Optimization (computer science)|optimizations]]. If one has <code>(map f . map g) xs</code> ('.' is [[functionThe composition (computer science)|function composition]]) then it is the same as the simpler <code>map (f . g)law xs</code>;ensures that is,both

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

|* <code>(map ''func''f ''list''. map g) list</code> and

* <code>map (f . g) list</code>

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

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.

<source lang="haskell">

rev_mapreverseMap f = foldl (\ys x -> f x : ys) []

</source>

Line 64 ⟶ 90:

==Language comparison==

The map function originated in [[functional programming]] languages but is today supported (or may be defined) in many [[procedural programming|procedural]], [[object oriented]], and [[multi-paradigm]] languages as well: In [[C++]]'s [[Standard Template Library]], it is called <code>std::transform</code>, in 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 [[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.

In languages which support [[first-class function]]s, <code>map</code> may be [[partial application|partially applied]] to "''lift"'' functionsa function that only works on a single value to an element-wise versionsequivalent that works on an entire container; for instance, <code>(map square)</code> is a Haskell function which squares listseach element-wise of a list.

{| class="wikitable"

Line 85 ⟶ 112:

| <code>std::transform(<wbr/>''begin1'', ''end1'', ''begin2'', ''result'', ''func'')</code>

|

| in header <algorithm><br /> ''begin'', ''end'', &and ''result'' are iterators<br /> result is written starting at ''result''

|

|- valign="top"

Line 114 ⟶ 141:

| <code>(map ''func'' ''list1'' ''list2'' ...)</code>

|

| Clojure: stops after the shortest list ends

|- valign="top"

| [[D (programming language)|D]]

Line 145 ⟶ 172:

|- valign="top"

| [[Groovy (programming language)|Groovy]]

| <code>list.collect(func)</code>

| <code>[list1 list2]<wbr>.transpose()<wbr>.collect(func)</code>

| <code>[list1 list2 ...]<wbr>.transpose()<wbr>.collect(func)</code>

|

|

Line 176 ⟶ 203:

|- valign="top"

| [[JavaScript]] 1.6<br>[[ECMAScript]] 5

| [https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/map <code>''array''#map(''func'')</code>]

| <code>''List1''.map(function (elem1, i) { <br />return ''func''(elem1, ''List2''[i]); })</code>

| <code>''List1''.map(function (elem1, i) { <br />return ''func''(elem1, ''List2''[i], ''List3''[i], ...); })</code>

Line 244 ⟶ 271:

| Returns a list in Python 2 and an [[iterator]] in Python 3.

| <code>''zip()''</code> and <code>''map()''</code> (3.x) stops after the shortest list ends, whereas <code>''map()''</code> (2.x) and <code>''itertools.zip_longest()''</code> (3.x) extends the shorter lists with <code>''None''</code> items

|- valign="top"

| [[Racket (programming language)|Racket]]

| <code>(map ''func'' ''list'')</code>

| <code>(map ''func'' ''list1'' ''list2'')</code>

| <code>(map ''func'' ''list1'' ''list2'' ...)</code>

|

| lists must all have the same length

|- valign="top"

| [[Ruby (programming language)|Ruby]]

Line 273 ⟶ 293:

| stops after the shorter list ends

|- valign="top"

| [[Scheme (programming language)|Scheme]], [[Racket (programming language)|Racket]]

| <code>(map ''func'' ''list'')</code>

| <code>(map ''func'' ''list1'' ''list2'')</code>