Map (higher-order function)

From Wikipedia, the free encyclopedia

In many programming languages, map is the name of a higher-order function that applies a given function to a sequence of elements (such as a list) and returns a sequence of results. They are examples of both catamorphisms and anamorphisms.

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

Map itself may be defined recursively, like this code in Haskell:

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

Contents

[edit] Language comparison

The map function is especially common in functional programming languages, but some high-level procedural languages support it as well, and in others it may be defined. Common Lisp provides a whole family of map-like functions. The one that corresponds to the behavior described here is called mapcar, where the -car designation indicates access using the CAR operation. In C++'s Standard Template Library, the map function is called transform. In C# (3.0), the map function is provided as an extension method called select. It is also frequently used as an array operation in scripting languages such as Perl, Python and Ruby; the operation is called map in Perl and Python and collect in Ruby.

[edit] Optimizations

The mathematical basis of maps allow for a number of optimizations. If one has map f . map g ('.' is function composition) then it is the same as the simpler map (f . g) xs; that is, \left( \text{map}\,f \right) \circ \left( \text{map}\,g \right) = \text{map}\,\left( f \circ g \right). This particular optimization eliminates an expensive second map by fusing it with the first map; thus it is a "map fusion"[1].

Map functions can and often are defined in terms of a fold such as foldr, which means one can do a "map-fold fusion": 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-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.

[edit] Haskell's Functor class

In the Haskell programming language, map is generalized to a polymorphic function called fmap using the Functor type class. For every Functor instance, fmap must be defined such that it obeys the Functor laws:

  • fmap id = id -- identity
  • fmap (f . g) = fmap f . fmap g -- composition

[edit] Mapping in .NET Procedural Languages

The map function in .NET Procedural languages like C# or VB.NET (as of C# 2.0 and VB 8.0[citation needed]) is supported through the select extension method. Here's an example that combines the use of select() with the use of anonymous functions, support for which was added to C# in version 3.0 (November 2007).

var values = new System.Collections.Generic.List<int>() { 7, 13, 4, 9, 3 };
var foo = values.Select(d => d * d);

[edit] References

  1. ^ "Map fusion: Making Haskell 225% faster"

[edit] See also

Languages