Map (higher-order function)
Encyclopedia
In many programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

s, map is the name of a higher-order function
Higher-order function
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...

 that applies a given function
Procedural parameter
In computing, a procedural parameter is a parameter of a procedure that is itself a procedure.This concept is an extremely powerful and versatile programming tool, because it allows programmers to modify certain steps of a library procedure in arbitrarily complicated ways, without having to...

 to each element of a list, returning a list of results. They are examples of both catamorphism
Catamorphism
In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...

s and anamorphism
Anamorphism
Anamorphosis is a distorted projection or perspective requiring the viewer to use special devices or occupy a specific vantage point to reconstitute the image...

s. This is often called apply-to-all when considered a functional form
Functional form
In programming and mathematics, a functional form is an operator or function that can either be applied to other operators or yield operators as result, or both...

.

For example, if we define a function square as follows:


square x = x * x


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

Language comparison

The map function originated in functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

 languages but is today supported (or may be defined) in many procedural
Procedural programming
Procedural programming can sometimes be used as a synonym for imperative programming , but can also refer to a programming paradigm, derived from structured programming, based upon the concept of the procedure call...

, object oriented, and multi-paradigm languages as well: In C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

's Standard Template Library
Standard Template Library
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...

, it is called 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 Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...

, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 and Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...

; the operation is called map in all three of these languages. A collect alias for map is also provided in Ruby (from Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...

). Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...

 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
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...

). There are also languages with syntactic constructs providing the same functionality as the map function.

Map is sometimes generalized to accept dyadic
Dyadic
Dyadic may refer to:*Adicity of a mathematical relation or function *Dyadic communication* Dyadic counterpoint, the voice-against-voice conception of polyphony...

 (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
Variadic function
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....

s may have versions of map with variable arity
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...

 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
First-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...

s, map may be partially applied
Partial application
In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity...

 to "lift" functions to element-wise versions; for instance, map square is a Haskell function which squares lists element-wise.
Map in various languages
Language Map Map 2 lists Map n lists Notes Handling lists of different lengths
Haskell
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

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
HaXe
haXe is a versatile open-source high-level multiplatform programming language described on its website as a "universal language".It can produce:* Flash applications and games* Multi-platform client-side web applications* Apache CGI web applications...

Lambda.map(iterable, func)
J
J (programming language)
The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....

func list list func list func/ list1 , list2 , list3 ,: list4 J's array processing capabilities make operations like map implicit length error if lists not equal
OCaml List.map func list
Array.map func array
List.map2 func list1 list2 raises Invalid_argument exception
Standard ML
Standard ML
Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the 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
Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

map(func, list) map(func, list1, list2) map(func, list1, list2, ...) 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
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...

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
C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

std::transform(begin, end, result, func) std::transform(begin1, end1, begin2, result, func) in header
begin, end, & result are iterators
result is written starting at result
Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...

map block list
map expr, list
In block or expr special variable $_ holds each value from list in turn. N/A
C# 3.0 ienum.Select(func) Select is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
C# 4.0 ienum.Select(func) ienum1.Zip(ienum2, func) Select is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
stops after the shortest list ends
JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....

 1.6
array.map(func)
Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...

(mapcar func list) (mapcar func list1 list2) (mapcar func list1 list2 ...) stops after the length of the shortest list
Scheme, Clojure
Clojure
Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....

(map func list) (map func list1 list2) (map func list1 list2 ...) Stops after the shortest list ends
Smalltalk
Smalltalk
Smalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...

aCollection collect: aBlock aCollection1 with: aCollection2 collect: aBlock Fails
Erlang
Erlang
Erlang may refer to:* Agner Krarup Erlang , a mathematician and engineer after whom several concepts are named** Erlang , a unit to measure traffic in telecommunications or other domains...

lists:map(Fun, List) lists:zipwith(Fun, List1, List2) zipwith3 also available Lists must be equal length
PHP
PHP
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...

array_map(callback, array) array_map(callback, array1,array2) array_map(callback, array1,array2, ...) The number of parameters for callback
should match the number of arrays.
extends the shorter lists with NULL items
Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...

maplist(Cont, List1, List2). maplist(Cont, List1, List2, List3). maplist(Cont, List1, ...). List arguments are input, output or both. Subsumes unzip, all Failure
Mathematica
Mathematica
Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...

func /@ list
Map[func, list]
MapThread[func, {list1, list2}] MapThread[func, {list1, list2, ...}] Lists must be same length
Maxima map(f, expr1, ..., exprn)
maplist(f, expr1, ..., exprn)
map returns an expression whose leading operator is the same as that of the expressions;
maplist returns a list
S/R
R (programming language)
R is a programming language and software environment for statistical computing and graphics. The R language is widely used among statisticians for developing statistical software, and R is widely used for statistical software development and data analysis....

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

Optimizations

The mathematical basis of maps allow for a number of optimizations
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...

. If one has (map f . map g) xs ('.' is function composition
Function composition (computer science)
In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones...

) then it is the same as the simpler map (f . g) xs; that is,
. This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion".

Map functions can be and often are defined in terms of a fold
Fold (higher-order function)
In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...

 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 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
Fold (higher-order function)
In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...

-left function.


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

Generalization

In the Haskell programming language
Haskell (programming language)
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

, the polymorphic
Type polymorphism
In computer science, polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface. The concept of parametric polymorphism applies to both data types and functions...

 map :: (a -> b) -> ([a] -> [b]) is generalized to a polytypic
Polytypic
In zoology, polytypic refers to a taxonomic unit with more than one subgroup at the next lower level.-See also:*Linnaean taxonomy*monotypic*monotypic habitat...

 function called fmap :: Functor f => (a -> b) -> (f a -> f b) which applies to any type in the Functor class.

map is used in Haskell's Prelude to define the list type constructor [] an instance of the Functor class as follows

instance Functor [] where fmap = map

But trees may belong to Functor too, for example:

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)

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

evaluates to:

Fork (Fork(Leaf 1)(Leaf 2))(Fork(Leaf 3)(Leaf 4))


For every instance of the Functor type class
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...

, fmap must be defined such that it obeys the functor laws:
  • fmap id = id -- identity
  • fmap (f . g) = fmap f . fmap g -- composition


Among other uses, this allows defining element-wise operations for other kind of collections.
Moreover, if and are two functors, a natural transformation
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 of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors". Indeed this intuition...

 is a function of polymorphic type which respects fmap: for any function .

If the h function is defined by parametric polymorphism
Parametric polymorphism
In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without...

 as in the type definition above, this specification is always satisfied.

See also

  • List comprehension
  • foreach
    Foreach
    For each is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set",...

  • Fold (higher-order function)
    Fold (higher-order function)
    In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...

  • Convolution (computer science)
    Convolution (computer science)
    In computer science, specifically formal languages, convolution is a function which maps a tuple of sequences into a sequence of tuples.- Example :The convolution of and, fish, be is...

    , (also known as conv or zip)
  • Free monoid
  • MapReduce
    MapReduce
    MapReduce is a software framework introduced by Google in 2004 to support distributed computing on large data sets on clusters of computers. Parts of the framework are patented in some countries....

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK