Difference between revisions of "Functor"
(Computer science use of the term. Should there be a disambiguation page?) |
DavidB4-bot (talk | contribs) (clean up) |
||
| (8 intermediate revisions by 7 users not shown) | |||
| Line 2: | Line 2: | ||
==In Pure Mathematics== | ==In Pure Mathematics== | ||
| − | In [[category theory]], a '''functor''' is a map between categories satisfying certain relations. Functors, in a sense, provide for categories what group [[homomorphism | + | In [[category theory]], a '''functor''' is a map between categories satisfying certain relations. Functors can be thought of as expressing relations between categories, and have a wide range of applications. For example, given a problem about topological spaces, one might apply some functor (say, taking the homology groups), and obtain an equivalent problem about vector spaces. Since problems about vector spaces are generally much easier to answer than those about general topological spaces, this may make it easier to understand the original problem. |
| + | |||
| + | Functors, in a sense, provide for categories what group [[homomorphism]]s do for groups. To be precise, a function <math>F : \mathcal C \to \mathcal D</math> between two categories associates to each object <math>X \in \textrm{Ob } \mathcal C</math> an object <math>F(X) \in \textrm{Ob } \mathcal D</math>, and to each morphism <math>f \in \mathcal C(X,Y)</math> a morphism <math>F(f) \in \mathcal D(FX,FY)</math> such that: | ||
:<math>F(\textrm{id}_X) = id_{F(X)}\,</math> | :<math>F(\textrm{id}_X) = id_{F(X)}\,</math> | ||
:<math>F(g \circ f) = F(g) \circ F(f)</math>. | :<math>F(g \circ f) = F(g) \circ F(f)</math>. | ||
Functors are the fundamental objects used to relate structures between different categories. | Functors are the fundamental objects used to relate structures between different categories. | ||
| + | |||
| + | The traditional terminology for the above is a "covariant functor", to distinguish it from "contravariant functors", which reverse the direction of compositions, and instead satisfy | ||
| + | :<math>F(g \circ f) = F(f) \circ F(g)</math>. | ||
| + | We will see an example of this below. | ||
=== Examples === | === Examples === | ||
Algebraic topology was the first field in which the usefulness of the notion of a functor was recognized. A basic example is the [[fundamental group]] functor <math>\pi_1 : \textbf{Top}* \to \textbf{Grp}</math>. The action on objects is defined by sending a topological space to its fundamental group <math>\pi_1(X)</math>. Recall that a map between two topological spaces <math>f : X \to Y</math> induces a map <math>f_* : \pi_1(X) \to \pi(Y)</math> by <math>f_*([\gamma]) = [f \circ \gamma]</math>. Set <math>\pi_1(f) = f_*\,</math> so defined. The functoriality of <math>\pi_1</math> boils down to the fact that <math>F(\textrm{id}_X) = \textrm{id}_{\pi_1(X)}</math>, that is, the identity map on a topological space induces the identity map on its fundamental group, together with the fact that <math>F(g \circ f) = F(g) \circ F(f)</math>, explained at [[fundamental group]]. | Algebraic topology was the first field in which the usefulness of the notion of a functor was recognized. A basic example is the [[fundamental group]] functor <math>\pi_1 : \textbf{Top}* \to \textbf{Grp}</math>. The action on objects is defined by sending a topological space to its fundamental group <math>\pi_1(X)</math>. Recall that a map between two topological spaces <math>f : X \to Y</math> induces a map <math>f_* : \pi_1(X) \to \pi(Y)</math> by <math>f_*([\gamma]) = [f \circ \gamma]</math>. Set <math>\pi_1(f) = f_*\,</math> so defined. The functoriality of <math>\pi_1</math> boils down to the fact that <math>F(\textrm{id}_X) = \textrm{id}_{\pi_1(X)}</math>, that is, the identity map on a topological space induces the identity map on its fundamental group, together with the fact that <math>F(g \circ f) = F(g) \circ F(f)</math>, explained at [[fundamental group]]. | ||
| + | |||
| + | A simple example arises in the category of vector spaces. Fix a vector space <math>V</math>. We can define a functor <math>\textrm{Hom}(V,-) : \textrm{Vect}_k \to \textrm{Vect}_k</math> by | ||
| + | #An object <math>A</math> (that is a vector space) is sent to <math>\textrm{Hom}(V,A)</math>, the vector space of linear maps from <math>V</math> to <math>A</math>. We can think of these linear maps as matrices. | ||
| + | #A linear transformation <math> \phi : A \to B</math> (i.e., an element of <math>\textrm{Hom}_{\textrm{Vect}_k}(A,B)</math> is sent to a linear transformation <math>\textrm{Hom}(V,A) \to \textrm{Hom}(V,B)</math> by setting <math>\textrm{Hom}(V,-)(\phi) = (f \mapsto \phi \circ f)</math>). In other words, the image of <math>\phi</math> is supposed to be a linear transformation from <math>\textrm{Hom}(V,A)</math> to <math>\textrm{Hom}(V,B)</math>: it is defined by sending a linear transformation <math>f : V \to A</math> to <math>\phi \circ f : V \to B</math>. | ||
| + | |||
| + | We can similarly obtain a contravariant function <math>\textrm{Hom}(-,V)</math> by | ||
| + | #An object <math>A</math> is sent to the vector space of linear maps <math>\textrm{Hom}(A,V)</math>. | ||
| + | #A map <math>\phi \in \textrm{Hom}(A,B)</math> is sent to a linear map <math>\textrm{Hom}(B,V) \to \textrm{Hom}(A,V)</math> by <math> \phi \mapsto (f \mapsto f \circ \phi)</math>. Given a linear map from B to V, we get one from A to V by composing with <math>\phi</math>. Note that morphisms now compose in the opposite direction: that is why this is a contravariant functor. | ||
==In Computer Science== | ==In Computer Science== | ||
Latest revision as of 00:43, August 18, 2016
The term functor has two distinct meanings.
In Pure Mathematics
In category theory, a functor is a map between categories satisfying certain relations. Functors can be thought of as expressing relations between categories, and have a wide range of applications. For example, given a problem about topological spaces, one might apply some functor (say, taking the homology groups), and obtain an equivalent problem about vector spaces. Since problems about vector spaces are generally much easier to answer than those about general topological spaces, this may make it easier to understand the original problem.
Functors, in a sense, provide for categories what group homomorphisms do for groups. To be precise, a function between two categories associates to each object Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in \textrm{Ob } \mathcal C} an object Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(X) \in \textrm{Ob } \mathcal D} , and to each morphism Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f \in \mathcal C(X,Y)} a morphism Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(f) \in \mathcal D(FX,FY)} such that:
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\textrm{id}_X) = id_{F(X)}\,}
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(g \circ f) = F(g) \circ F(f)} .
Functors are the fundamental objects used to relate structures between different categories.
The traditional terminology for the above is a "covariant functor", to distinguish it from "contravariant functors", which reverse the direction of compositions, and instead satisfy
- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(g \circ f) = F(f) \circ F(g)} .
We will see an example of this below.
Examples
Algebraic topology was the first field in which the usefulness of the notion of a functor was recognized. A basic example is the fundamental group functor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_1 : \textbf{Top}* \to \textbf{Grp}} . The action on objects is defined by sending a topological space to its fundamental group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_1(X)} . Recall that a map between two topological spaces Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : X \to Y} induces a map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_* : \pi_1(X) \to \pi(Y)} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_*([\gamma]) = [f \circ \gamma]} . Set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_1(f) = f_*\,} so defined. The functoriality of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi_1} boils down to the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\textrm{id}_X) = \textrm{id}_{\pi_1(X)}} , that is, the identity map on a topological space induces the identity map on its fundamental group, together with the fact that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(g \circ f) = F(g) \circ F(f)} , explained at fundamental group.
A simple example arises in the category of vector spaces. Fix a vector space Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} . We can define a functor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,-) : \textrm{Vect}_k \to \textrm{Vect}_k} by
- An object Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} (that is a vector space) is sent to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,A)} , the vector space of linear maps from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . We can think of these linear maps as matrices.
- A linear transformation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi : A \to B} (i.e., an element of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}_{\textrm{Vect}_k}(A,B)} is sent to a linear transformation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,A) \to \textrm{Hom}(V,B)} by setting Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,-)(\phi) = (f \mapsto \phi \circ f)} ). In other words, the image of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} is supposed to be a linear transformation from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,A)} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(V,B)} : it is defined by sending a linear transformation Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : V \to A} to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi \circ f : V \to B} .
We can similarly obtain a contravariant function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(-,V)} by
- An object Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} is sent to the vector space of linear maps Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(A,V)} .
- A map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi \in \textrm{Hom}(A,B)} is sent to a linear map Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textrm{Hom}(B,V) \to \textrm{Hom}(A,V)} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi \mapsto (f \mapsto f \circ \phi)} . Given a linear map from B to V, we get one from A to V by composing with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \phi} . Note that morphisms now compose in the opposite direction: that is why this is a contravariant functor.
In Computer Science
In computer science, the term "functor" is short for "function operator", also called a "function object". It is essentially a class method with no name. Many modern programming languages support this. For example, in C++ one can define a function object with the "operator()" notation, that is, a definition of what parentheses mean after an object.
class C {
public:
int operator()(int i, int j) { return k+i*j; }
int k;
.....
};
.....
C MyObject;
MyObject.k = 3;
int r = MyObject(4,5);
.....
We have effectively defined a nameless method for class C. Instead of making a named invocation like "MyObject.func(4,5)", we just write "MyObject(4,5)".