Map (higher-order function)

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a functor, e.g. a list, returning a list of results in the same order. 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 containers, tree-like containers, or even abstract containers such as futures and promises.

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

square x = x * x

Afterwards we may call

>>> map square [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

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 _ []       = []
map f (x : xs) = f x : map f xs

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:

instance Functor [] where
  fmap = map

Other examples of Functor instances include trees:

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

Mapping over a tree yields:

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

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

fmap id      ≡ id              -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law

where . denotes function composition in Haskell.

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

Moreover, if $F$ and $G$ are two functors, a natural transformation is a function of polymorphic type $h:\forall T.F(T)\to G(T)$ which respects $fmap$ :

h_{Y}\circ \operatorname {fmap} (f)=\operatorname {fmap} (f)\circ h_{X}

for any function

f:X\to Y

.

If the $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 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.[1]

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.

reverseMap f = foldl (\ys x -> f x : 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[2] in 1959, with slightly different versions already appearing in 1958.[3] 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,[4] 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 (car l))) '(1 2 3 4 5))

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

(mapcar (function sqr) '(1 2 3 4 5))

Today mapping functions are supported (or may be defined) in many procedural, object-oriented, and multi-paradigm languages as well: In C++'s Standard Template 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	`func list`	`list1 func list2`	`func/ list1 list2 list3 list4`	APL's array processing abilities make operations like map implicit	length error if list lengths not equal or 1
Common Lisp	`(mapcar func list)`	`(mapcar func list1 list2)`	`(mapcar func list1 list2 ...)`		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 func list)`	`(map func list1 list2)`	`(map func list1 list2 ...)`		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 func list`	`List.map2 func list1 list2`		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 func list`	`zipWith func list1 list2`	`zipWithn func list1 list2 ...`	`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	`func list`	`list1 func list2`	`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 func list Array.map func array`	`List.map2 func list1 list2`			raises Invalid_argument exception
PARI/GP	`apply(func, list)`				N/A
Perl	`map block list 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 func list)`	`(map func list1 list2)`	`(map func list1 list2 ...)`		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 func list`	`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

gollark: Can your "computer" achieve amazing 1.2GHz clock rates?

gollark: A GPU isn't the same as an ISP, bee.

gollark: Does it have a dedicated image signal processor for cameras?

gollark: Does it run entirely on one micro-USB power connection?

gollark: Hmm. I assumed it predated USB 2. Worrying.

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

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

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

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