Map (higher-order function)

Last updated December 29, 2023

In many programming languages, map is a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form.

Examples: mapping a list

Suppose we have a list of integers [1, 2, 3, 4, 5] and would like to calculate the square of each integer. To do this, we first define a function to square a single number (shown here in Haskell):

squarex=x*x

Afterwards we may call

>>>mapsquare[1,2,3,4,5]

which yields [1, 4, 9, 16, 25], demonstrating that map has gone through the entire list and applied the function square to each element.

Visual example

Below, you can see a view of each step of the mapping process for a list of integers X = [0, 5, 8, 3, 2, 1] that we want to map into a new list X' according to the function $f(x)=x+1$ :

View of processing steps when applying map function on a list Mapping-steps-loillibe-new.gif — View of processing steps when applying map function on a list

The map is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:

map::(a->b)->[a]->[b]map_[]=[]mapf(x:xs)=fx:mapfxs

Generalization

In Haskell, the polymorphic function map :: (a -> b) -> [a] -> [b] is generalized to a polytypic function fmap :: Functor f => (a -> b) -> f a -> f b, which applies to any type belonging the Functor type class.

The type constructor of lists [] can be defined as an instance of the Functor type class using the map function from the previous example:

instanceFunctor[]wherefmap=map

Other examples of Functor instances include trees:

-- a simple binary treedataTreea=Leafa|Fork(Treea)(Treea)instanceFunctorTreewherefmapf(Leafx)=Leaf(fx)fmapf(Forklr)=Fork(fmapfl)(fmapfr)

Mapping over a tree yields:

>>>fmapsquare(Fork(Fork(Leaf1)(Leaf2))(Fork(Leaf3)(Leaf4)))Fork(Fork(Leaf1)(Leaf4))(Fork(Leaf9)(Leaf16))

For every instance of the Functor type class, fmap is contractually obliged to obey the functor laws:

fmapid≡id-- identity lawfmap(f.g)≡fmapf.fmapg-- composition law

where . denotes function composition in Haskell.

Among other uses, this allows defining element-wise operations for various kinds of collections.

Category-theoretic background

In category theory, a functor $F:C\rightarrow D$ consists of two maps: one that sends each object $A$ of the category to another object $FA$ , and one that sends each morphism $f:A\rightarrow B$ to another morphism $Ff:FA\rightarrow FB$ , which acts as a homomorphism on categories (i.e. it respects the category axioms). Interpreting the universe of data types as a category $Type$ , with morphisms being functions, then a type constructor F that is a member of the Functor type class is the object part of such a functor, and 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.

Functors can also be objects in categories, with "morphisms" called natural transformations. Given two functors $F,G:C\rightarrow D$ , a natural transformation $\eta :F\rightarrow G$ consists of a collection of morphisms $\eta _{A}:FA\rightarrow GA$ , one for each object $A$ of the category $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 eta :: F a -> G a, where a is a universally quantified type variable – eta knows nothing about the type which inhabits a. The naturality axiom of such functions is automatically satisfied because it is a so-called free theorem, depending on the fact that it is parametrically polymorphic.^[1] For example, reverse :: List a -> List a, which reverses a list, is a natural transformation, as is flattenInorder :: Tree a -> List a, which flattens a tree from left to right, and even sortBy :: (a -> a -> Bool) -> List a -> List a, which sorts a list based on a provided comparison function.

Optimizations

The mathematical basis of maps allow for a number of optimizations. The composition law ensures that both

(map f . map g) list and
map (f . g) list

lead to the same result; that is, $\operatorname {map} (f)\circ \operatorname {map} (g)=\operatorname {map} (f\circ g)$ . However, the second form is more efficient to compute than the first form, because each map 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 analog of loop fusion.^[2]

Map functions can be and often are defined in terms of a fold such as foldr, which means one can do a map-fold fusion: foldr f z . map g is equivalent to foldr (f . g) z.

The implementation of map above on singly linked lists is not 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-left function.

reverseMapf=foldl(\ysx->fx:ys)[]

Since reversing a singly linked list is also tail-recursive, reverse and reverse-map can be composed to perform normal map in a tail-recursive way, though it requires performing two passes over the list.

Language comparison

The map function originated in functional programming languages.

The language Lisp introduced a map function called maplist^[3] in 1959, with slightly different versions already appearing in 1958.^[4] This is the original definition for maplist, mapping a function over successive rest lists:

maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]

The function maplist is still available in newer Lisps like Common Lisp,^[5] though functions like mapcar or the more generic map would be preferred.

Squaring the elements of a list using maplist would be written in S-expression notation like this:

(maplist(lambda(l)(sqr(carl)))'(12345))

Using the function mapcar, above example would be written like this:

(mapcar(functionsqr)'(12345))

Today mapping functions are supported (or may be defined) in many procedural, object-oriented, and multi-paradigm languages as well: In C++'s Standard Library, it is called std::transform, in C# (3.0)'s LINQ library, it is provided as an extension method called Select. Map is also a frequently used operation in high level languages such as ColdFusion Markup Language (CFML), Perl, Python, and Ruby; the operation is called map in all four of these languages. A collect alias for map 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 mapcar (-car indicating access using the 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 functions 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 functions and currying, map may be partially applied to lift a function that works on only one value to an element-wise equivalent that works on an entire container; for example, map square is a Haskell function which squares each element of a list.

Map in various languages
Language	Map	Map 2 lists	Map n lists	Notes	Handling lists of different lengths
APL	`funclist`	`list1funclist2`	`func/ list1list2list3list4`	APL's array processing abilities make operations like map implicit	length error if list lengths not equal or 1
Common Lisp	`(mapcar funclist)`	`(mapcar funclist1list2)`	`(mapcar funclist1list2 ...)`		stops after the length of the shortest list
C++	`std::transform(begin, end, result, func)`	`std::transform(begin1, end1, begin2, result, func)`		in header <algorithm> begin, end, and result are iterators result is written starting at result
C#	`ienum.Select(func)` or The `select` clause	`ienum1.Zip(ienum2, func)`		`Select` is an extension method ienum is an IEnumerable `Zip` is introduced in .NET 4.0 Similarly in all .NET languages	stops after the shortest list ends
CFML	`obj.map(func)`			Where `obj` is an array or a structure. `func` receives as arguments each item's value, its index or key, and a reference to the original object.
Clojure	`(map funclist)`	`(map funclist1list2)`	`(map funclist1list2 ...)`		stops after the shortest list ends
D	`list.map!func`	`zip(list1, list2).map!func`	`zip(list1, list2, ...).map!func`		Specified to zip by StoppingPolicy: shortest, longest, or requireSameLength
Erlang	`lists:map(Fun, List)`	`lists:zipwith(Fun, List1, List2)`	`zipwith3` also available		Lists must be equal length
Elixir	`Enum.map(list, fun)`	`Enum.zip(list1, list2) \|> Enum.map(fun)`	`List.zip([list1, list2, ...]) \|> Enum.map(fun)`		stops after the shortest list ends
F#	`List.map funclist`	`List.map2 funclist1list2`		Functions exist for other types (Seq and Array)	Throws exception
Groovy	`list.collect(func)`	`[list1 list2].transpose().collect(func)`	`[list1 list2 ...].transpose().collect(func)`
Haskell	`map funclist`	`zipWith funclist1list2`	`zipWithnfunclist1list2 ...`	`n` corresponds to the number of lists; predefined up to `zipWith7`	stops after the shortest list ends
Haxe	`array.map(func) list.map(func) Lambda.map(iterable, func)`
J	`funclist`	`list1funclist2`	`func/ list1, list2, list3 ,: list4`	J's array processing abilities make operations like map implicit	length error if list lengths not equal
Java 8+	`stream.map(func)`
JavaScript 1.6 ECMAScript 5	`array#map(func)`	`List1.map(function (elem1, i) { return func(elem1, List2[i]); })`	`List1.map(function (elem1, i) { return func(elem1, List2[i], List3[i], ...); })`	Array#map passes 3 arguments to func: the element, the index of the element, and the array. Unused arguments can be omitted.	Stops at the end of List1, extending the shorter arrays with undefined items if needed.
Julia	`map(func, list)`	`map(func, list1, list2)`	`map(func, list1, list2, ..., listN)`		ERROR: DimensionMismatch
Logtalk	`map(Closure, List)`	`map(Closure, List1, List2)`	`map(Closure, List1, List2, List3, ...) (up to seven lists)`	Only the Closure argument must be instantiated.	Failure
Mathematica	`func /@ list Map[func, list]`	`MapThread[func, {list1, list2}]`	`MapThread[func, {list1, list2, ...}]`		Lists must be same length
Maxima	`map(f, expr₁, ..., expr_n) maplist(f, expr₁, ..., expr_n)`			map returns an expression which leading operator is the same as that of the expressions; maplist returns a list
OCaml	`List.map funclist Array.map funcarray`	`List.map2 funclist1list2`			raises Invalid_argument exception
PARI/GP	`apply(func, list)`				—
Perl	`map blocklist map expr, list`			In block or expr special variable $_ holds each value from list in turn.	Helper `List::MoreUtils::each_array` combines more than one list until the longest one is exhausted, filling the others with `undef.`
PHP	`array_map(callable, array)`	`array_map(callable, array1,array2)`	`array_map(callable, array1,array2, ...)`	The number of parameters for callable should match the number of arrays.	extends the shorter lists with NULL items
Prolog	`maplist(Cont, List1, List2).`	`maplist(Cont, List1, List2, List3).`	`maplist(Cont, List1, ...).`	List arguments are input, output or both. Subsumes also zipWith, unzip, all	Silent failure (not an error)
Python	`map(func, list)`	`map(func, list1, list2)`	`map(func, list1, list2, ...)`	Returns a list in Python 2 and an iterator in Python 3.	`zip()` and `map()` (3.x) stops after the shortest list ends, whereas `map()` (2.x) and `itertools.zip_longest()` (3.x) extends the shorter lists with `None` items
Ruby	`enum.collect {block} enum.map {block}`	`enum1.zip(enum2).map {block}`	`enum1.zip(enum2, ...).map {block} [enum1, enum2, ...].transpose.map {block}`	`enum is an Enumeration`	stops at the end of the object it is called on (the first list); if any other list is shorter, it is extended with nil items
Rust	`list1.into_iter().map(func)`	`list1.into_iter().zip(list2).map(func)`		the `Iterator::map` and `Iterator::zip` methods both take ownership of the original iterator and return a new one; the `Iterator::zip` method internally calls the `IntoIterator::into_iter` method on `list2`	stops after the shorter list ends
S-R	`lapply(list, func)`	`mapply(func, list1, list2)`	`mapply(func, list1, list2, ...)`		Shorter lists are cycled
Scala	`list.map(func)`	`(list1, list2).zipped.map(func)`	`(list1, list2, list3).zipped.map(func)`	note: more than 3 not possible.	stops after the shorter list ends
Scheme (including Guile and Racket)	`(map funclist)`	`(map funclist1list2)`	`(map funclist1list2 ...)`		lists must all have same length (SRFI-1 extends to take lists of different length)
Smalltalk	`aCollection collect: aBlock`	`aCollection1 with: aCollection2 collect: aBlock`			Fails
Standard ML	`map funclist`	`ListPair.map func (list1, list2) ListPair.mapEq func (list1, list2)`		For 2-argument map, func takes its arguments in a tuple	`ListPair.map` stops after the shortest list ends, whereas `ListPair.mapEq` raises `UnequalLengths` exception
Swift	`sequence.map(func)`	`zip(sequence1, sequence2).map(func)`			stops after the shortest list ends
XPath 3 XQuery 3	`list ! block` `for-each(list, func)`	`for-each-pair(list1, list2, func)`		In `block` the context item `.` holds the current value	stops after the shortest list ends

Related Research Articles

In mathematics and computer science, currying is the technique of translating a function that takes multiple arguments into a sequence of families of functions, each taking a single argument.

In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects are associated to topological spaces, and maps between these algebraic objects are associated to continuous maps between spaces. Nowadays, functors are used throughout modern mathematics to relate various categories. Thus, functors are important in all areas within mathematics to which category theory is applied.

In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products, pullbacks and inverse limits. The dual notion of a colimit generalizes constructions such as disjoint unions, direct sums, coproducts, pushouts and direct limits.

In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Informally, the notion of a natural transformation states that a particular map between functors can be done consistently over an entire category.

In mathematics, specifically in category theory, a pre-abelian category is an additive category that has all kernels and cokernels.

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them. Examples of combinatorial species are graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.

In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types.

In category theory, a branch of mathematics, a monad is a monoid in the category of endofunctors of some fixed category. An endofunctor is a functor mapping a category to itself, and a monad is an endofunctor together with two natural transformations required to fulfill certain coherence conditions. Monads are used in the theory of pairs of adjoint functors, and they generalize closure operators on partially ordered sets to arbitrary categories. Monads are also useful in the theory of datatypes, the denotational semantics of imperative programming languages, and in functional programming languages, allowing languages with non-mutable states to do things such as simulate for-loops; see Monad.

In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, monads define two operators: one to wrap a value in the monad type, and another to compose together functions that output values of the monad type. General-purpose languages use monads to reduce boilerplate code needed for common operations. Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away control flow, and side-effects.

In mathematics, a comma category is a construction in category theory. It provides another way of looking at morphisms: instead of simply relating objects of a category to one another, morphisms become objects in their own right. This notion was introduced in 1963 by F. W. Lawvere, although the technique did not become generally known until many years later. Several mathematical concepts can be treated as comma categories. Comma categories also guarantee the existence of some limits and colimits. The name comes from the notation originally used by Lawvere, which involved the comma punctuation mark. The name persists even though standard notation has changed, since the use of a comma as an operator is potentially confusing, and even Lawvere dislikes the uninformative term "comma category".

In mathematics, specifically in category theory, F-algebras generalize the notion of algebraic structure. Rewriting the algebraic laws in terms of morphisms eliminates all references to quantified elements from the axioms, and these algebraic laws may then be glued together in terms of a single functor F, the signature.

In mathematics, an initial algebra is an initial object in the category of $F$ -algebras for a given endofunctor $F$ . This initiality provides a general framework for induction and recursion.

In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra.

In category theory, monoidal functors are functors between monoidal categories which preserve the monoidal structure. More specifically, a monoidal functor between two monoidal categories consists of a functor between the categories, along with two coherence maps—a natural transformation and a morphism that preserve monoidal multiplication and unit, respectively. Mathematicians require these coherence maps to satisfy additional properties depending on how strictly they want to preserve the monoidal structure; each of these properties gives rise to a slightly different definition of monoidal functors

In functional programming, fold refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.

In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and so on until some terminating condition is reached. The anamorphism is the function that generates the list of A, B, C, etc. You can think of the anamorphism as unfolding the initial value into a sequence.

In category theory, a span, roof or correspondence is a generalization of the notion of relation between two objects of a category. When the category has all pullbacks, spans can be considered as morphisms in a category of fractions.

In computer science, and in particular functional programming, a hylomorphism is a recursive function, corresponding to the composition of an anamorphism followed by a catamorphism. Fusion of these two recursive computations into a single recursive pattern then avoids building the intermediate data structure. This is an example of deforestation, a program optimization strategy. A related type of function is a metamorphism, which is a catamorphism followed by an anamorphism.

In functional programming, an applicative functor, or an applicative for short, is an intermediate structure between functors and monads. In Category Theory they are called Closed Monoidal Functors. Applicative functors allow for functorial computations to be sequenced, but don't allow using results from prior computations in the definition of subsequent ones. Applicative functors are the programming equivalent of lax monoidal functors with tensorial strength in category theory.

In functional programming, a functor is a design pattern inspired by the definition from category theory that allows one to apply a function to values inside a generic type without changing the structure of the generic type. In Haskell this idea can be captured in a type class:

References

↑ In a non-strict language that permits general recursion, such as Haskell, this is only true if the first argument to fmap is strict. Wadler, Philip (September 1989). Theorems for free! (PDF). 4th International Symposium on Functional Programming Languages and Computer Architecture. London: Association for Computing Machinery.
↑ "Map fusion: Making Haskell 225% faster"
↑ J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959
↑ J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958
↑ Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] In a non-strict language that permits general recursion, such as Haskell, this is only true if the first argument to fmap is strict. Wadler, Philip (September 1989). Theorems for free! (PDF). 4th International Symposium on Functional Programming Languages and Computer Architecture. London: Association for Computing Machinery.

[2] "Map fusion: Making Haskell 225% faster"

[3] J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959

[4] J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958

[5] Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp

[1]

[2]

[3]

[4]

[5]