Examples: mapping a list
Suppose we have a list of integers , 2, 3, 4, 5/code> 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
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
):
square x = x * x
Afterwards we may call
>>> map square , 2, 3, 4, 5
which yields , 4, 9, 16, 25/code>, 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 = , 5, 8, 3, 2, 1/code> that we want to map into a new list X'
according to the function :
The map
is provided as part of the Haskell's base prelude (i.e. "standard library") and is implemented as:
map :: (a -> b) -> -> map _ [] = []
map f (x : xs) = f x : map f xs
Generalization
In Haskell, the polymorphic function map :: (a -> b) -> -> /code> 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
In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and ...
.
The type constructor
In the area of mathematical logic and computer science known as type theory, a type constructor is a feature of a typed formal language that builds new types from old ones. Basic types are considered to be built using nullary type constructors. S ...
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 mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
in Haskell.
Among other uses, this allows defining element-wise operations for various kinds of collections
Collection or Collections may refer to:
* Cash collection, the function of an accounts receivable department
* Collection (church), money donated by the congregation during a church service
* Collection agency, agency to collect cash
* Collection ...
.
Moreover, if and are two functors, a natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
is a function of polymorphic type which respects :
: for any function .
If the function is defined by parametric polymorphism
In programming languages and type theory, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed. Parametrically polymorph ...
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, . 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
Functional may refer to:
* Movements in architecture:
** Functionalism (architecture)
** Form follows function
* Functional group, combination of atoms within molecules
* Medical conditions without currently visible organic basis:
** Functional sy ...
analog of loop fusion In computer science, loop fission (or loop distribution) is a compiler optimization in which a loop is broken into multiple loops over the same index range with each taking only a part of the original loop's body. The goal is to break down a large l ...
.
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
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
languages.
The language Lisp
A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech.
Types
* A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
introduced a map function called maplist
in 1959, with slightly different versions already appearing in 1958. This is the original definition for maplist
, mapping a function over successive rest lists:
maplist ;f= ull[x->_NIL;T_->_cons[f[x.html"_;"title=".html"_;"title="ull[x">ull[x->_NIL;T_->_cons[f[x">.html"_;"title="ull[x">ull[x->_NIL;T_->_cons[f[xmaplist[cdr[x.html" ;"title="">ull[x->_NIL;T_->_cons[f[x.html" ;"title=".html" ;"title="ull[x">ull[x-> NIL;T -> cons[f[x">.html" ;"title="ull[x">ull[x-> NIL;T -> cons[f[xmaplist[cdr[x">">ull[x->_NIL;T_->_cons[f[x.html" ;"title=".html" ;"title="ull[x">ull[x-> NIL;T -> cons[f[x">.html" ;"title="ull[x">ull[x-> NIL;T -> cons[f[xmaplist[cdr[xf]
The function maplist
is still available in newer Lisps like Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fro ...
,Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp
/ref> 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
In computer programming, an S-expression (or symbolic expression, abbreviated as sexpr or sexp) is an expression in a like-named notation for nested list (tree-structured) data. S-expressions were invented for and popularized by the programming la ...
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
Object-oriented programming (OOP) is a programming paradigm based on the concept of "objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of pro ...
, and multi-paradigm
Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms.
Some paradigms are concerned mainly with implications for the execution model of the language, suc ...
languages as well: In C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
's Standard Library
In computer programming, a standard library is the library made available across implementations of a programming language. These libraries are conventionally described in programming language specifications; however, contents of a language's as ...
, 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
ColdFusion Markup Language, more commonly known as CFML, is a scripting language for web development that runs on the JVM, the .NET framework, and Google App Engine. Multiple commercial and open source implementations of CFML engines are availab ...
(CFML), Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
, Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
, and Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
; the operation is called map
in all four of these languages. A collect
alias for map
is also provided in Ruby (from Smalltalk
Smalltalk is an object-oriented, dynamically typed reflective programming language. It was designed and created in part for educational use, specifically for constructionist learning, at the Learning Research Group (LRG) of Xerox PARC by Alan Ka ...
). Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fro ...
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 function
In mathematics and in computer programming, a variadic function is a function of indefinite arity, i.e., one which accepts a variable number of arguments. Support for variadic functions differs widely among programming languages.
The term ''varia ...
s may have versions of map with variable arity
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
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
In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...
s and currying
In mathematics and computer science, currying is the technique of translating the evaluation of a function that takes multiple arguments into evaluating a sequence of functions, each with a single argument. For example, currying a function f that ...
, 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.
See also
* Functor (functional programming)
* Zipping (computer science) or zip, mapping 'list' over multiple lists
* Filter (higher-order function)
In functional programming, filter is a higher-order function that processes a data structure (usually a list) in some order to produce a new data structure containing exactly those elements of the original data structure for which a given predicat ...
* Fold (higher-order function) In functional programming, fold (also termed reduce, accumulate, aggregate, compress, or inject) refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the res ...
* foreach
In computer programming, foreach loop (or for each loop) is a control flow statement for traversing items in a collection. is usually used in place of a standard loop statement. Unlike other loop constructs, however, loops usually maintai ...
* Free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
* Functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declar ...
* Higher-order function
* List comprehension
A list comprehension is a Syntax of programming languages, syntactic construct available in some programming languages for creating a list based on existing list (computing), lists. It follows the form of the mathematical ''set-builder notation'' ( ...
* Map (parallel pattern) Map is an idiom in parallel computing where a simple operation is applied to all elements of a sequence, potentially in parallel. It is used to solve embarrassingly parallel problems: those problems that can be decomposed into independent subtask ...
References
{{Reflist
Higher-order functions
Programming language comparisons
Articles with example Haskell code
Iteration in programming