Concept

# Map (higher-order function)

Summary
In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. 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. 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. 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 : 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 Functor and Category theory 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 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 .
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related concepts (39)
Function composition (computer science)
In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole. Programmers frequently apply functions to results of other functions, and almost all programming languages allow it. In some cases, the composition of functions is interesting as a function in its own right, to be used later.
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 collection, e.g. a list or set, returning the results in a collection of the same type. 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. Suppose we have a list of integers [1, 2, 3, 4, 5] and would like to calculate the square of each integer.
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 results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions.
Related courses (7)
CS-119(k): Information, Computation, Communication
D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects liés aux systèmes: ordi
MATH-661: Advanced Scientific Programming in Python
This seminar teaches the participants to use advanced Python concepts for writing easier to read, more flexible and faster code. It teaches concepts in a hands-on and tangible fashion, providing examp
CS-628: Interactive Theorem Proving CS
A hands-on introduction to interactive theorem proving, proofs as programs, dependent types, and to the Coq proof assistant. Come learn how to write bug-free code!