Content deleted Content added
→Language comparison: move Groovy up to restore alphabetical order |
m <syntaxhighlight>; <pre> for no lang |
||
Line 9:
Suppose we have a list of integers <code>[1, 2, 3, 4, 5]</code> and would like to calculate the square of each integer. To do this, we first define a function to <code>square</code> a single number (shown here in [[Haskell (programming language)|Haskell]]):
<
square x = x * x
</syntaxhighlight>
Afterwards we may call
<
>>> map square [1, 2, 3, 4, 5]
</syntaxhighlight>
which yields <code>[1, 4, 9, 16, 25]</code>, demonstrating that <code>map</code> has gone through the entire list and applied the function <code>square</code> to each element. The <code>map</code> 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
</syntaxhighlight>
==Generalization==
Line 35:
The [[type constructor]] of lists <code>[]</code> can be defined as an instance of the <code>Functor</code> type class using the <code>map</code> function from the previous example:
<
instance Functor [] where
fmap = map
</syntaxhighlight>
Other examples of <code>Functor</code> instances include trees:
<
-- a simple binary tree
data Tree a = Leaf a | Fork (Tree a) (Tree a)
Line 49:
fmap f (Leaf x) = Leaf (f x)
fmap f (Fork l r) = Fork (fmap f l) (fmap f r)
</syntaxhighlight>
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))
</syntaxhighlight>
For every instance of the <code>Functor</code> type class, <code>fmap</code> is [[design by contract|contractually obliged]] to obey the functor laws:
<
fmap id ≡ id -- identity law
fmap (f . g) ≡ fmap f . fmap g -- composition law
</syntaxhighlight>
where <code>.</code> denotes [[function composition (computer science)|function composition]] in Haskell.
Line 83:
The implementation of map above on singly linked lists is not [[tail recursion|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 (higher-order function)|fold]]-left function.
<
reverseMap f = foldl (\ys x -> f x : ys) []
</syntaxhighlight>
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.
Line 95:
The language [[Lisp (programming language)|Lisp]] introduced a map function called <code>maplist</code><ref>[http://www.softwarepreservation.org/projects/LISP/MIT/LISP_Prog_Man-Mar_1959.pdf/view J. McCarthy, K. Maling, S. Russell, N. Rochester, S. Goldberg, J. Slagle. LISP Programmer's Manual. March-April, 1959]</ref> in 1959, with slightly different versions already appearing in 1958.<ref>[http://www.softwarepreservation.org/projects/LISP/MIT/AIM-004.pdf/view J. McCarthy: Symbol Manipulating Language - Revisions of the Language. AI Memo No. 4, October 1958]</ref> This is the original definition for <code>maplist</code>, mapping a function over successive rest lists:
<
maplist[x;f] = [null[x] -> NIL;T -> cons[f[x];maplist[cdr[x];f]]]
</
The function <code>maplist</code> is still available in newer Lisps like [[Common Lisp]],<ref>[http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm Function MAPC, MAPCAR, MAPCAN, MAPL, MAPLIST, MAPCON in ANSI Common Lisp]</ref> though functions like <code>mapcar</code> or the more generic <code>map</code> would be preferred.
Line 103:
Squaring the elements of a list using <code>maplist</code> would be written in [[S-expression]] notation like this:
<
(maplist (function (lambda (l)
(sqr (car l))))
'(1 2 3 4 5))
</syntaxhighlight>
Using the function <code>mapcar</code>, above example would be written like this:
<
(mapcar (function sqr) '(1 2 3 4 5))
</syntaxhighlight>
Today mapping functions are supported (or may be defined) in many [[procedural programming|procedural]], [[Object-oriented programming|object-oriented]], and [[multi-paradigm]] languages as well: In [[C++]]'s [[Standard Template Library]], it is called <code>std::transform</code>, in [[C Sharp (programming language)|C#]] (3.0)'s LINQ library, it is provided as an extension method called <code>Select</code>. Map is also a frequently used operation in high level languages such as [[ColdFusion Markup Language]] (CFML), [[Perl]], [[Python (programming language)|Python]], and [[Ruby (programming language)|Ruby]]; the operation is called <code>map</code> in all four of these languages. A <code>collect</code> alias for <code>map</code> 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 <code>mapcar</code> (<code>-car</code> indicating access using the [[CAR and CDR|CAR operation]]). There are also languages with syntactic constructs providing the same functionality as the map function.
| |||