Contravariant Functors Are Weird
sanj.ink
Contravariant Functors Are Weird
1–10 of 26 posts
Re: Contravariant Functors Are Weird
#2I was super confused by contravariant functors until someone gave me a concrete example of an instance of it as "the left side of an arrow".
With a regular functor you have:
fmap :: Functor f => (a -> b) -> f a -> f b
newtype Identity a = Identity a
instance Functor Identity where
fmap f (Identity x) = Identity (f x)
contramap :: Contravariant f => (a -> b) -> f b -> f a
newtype Op a b = Op (b -> a)
instance Contravariant (Op a) where
contramap f (Op g) = Op (g . f)
contramap :: (a -> b) -> (b -> c) -> (a -> c)
Of course, there are other kinds of contravariant functors, but this was the one that stuck out the most to me.
Re: Contravariant Functors Are Weird
#3I was super confused by contravariant functors until someone gave me a concrete example of an instance of it as "the left side of an arrow". With a regular functor you have: fmap :: Functor f => (a -> b) -> f a -> f b and you can think of something relatively straightforward type that fulfills it it, e.g.: newtype Identity a = Identity a instance Functor Identity where fmap f (Identity x) = Identity (f x) With a cont…
I missed a step:
contramap :: (a -> b) -> Op c b -> Op c a -- substitute Contravariant f for the Op instance, c is introduced as a new type variable
contramap :: (a -> b) -> (b -> c) -> (a -> c)Re: Contravariant Functors Are Weird
#4Contravariant functors are actually really nice.
The classic example from maths is the spectrum (Spec) of a ring R. As a functor, Spec(R) = the set of prime ideals of R. An example anyone can understand: all the multiples of prime numbers p Z, in the integers Z.
Let R -> S is a ring homomorphism, then there is an induced map Spec(S) -> Spec(R).
Spec establishes a connection between the category of rings and topological spaces. Algebraic geometry is a whole area of maths that deals with this connection.
Re: Contravariant Functors Are Weird
#5Contravariant functors are actually really nice. The classic example from maths is the spectrum (Spec) of a ring R. As a functor, Spec(R) = the set of prime ideals of R. An example anyone can understand: all the multiples of prime numbers p Z, in the integers Z. Let R -> S is a ring homomorphism, then there is an induced map Spec(S) -> Spec(R). Spec establishes a connection between the category of rings and topologic…
While I know precisely what you are saying (have been learning scheme theory this summer), this is hardly an accessible example to pure math undergrads, let alone someone who's attempting to learn some functional programming, with no heavy experience with abstract algebra.
First of all, why use Spec? Use ideals/varieties, it contains roughly the same data, while being way better to intuit. I'll put my money where my mouth is, and give it a shot.
Say we have some collection of points in |R^2, and we want to find equations which define this set. We do this by creating a function
f: points in |R^2 -> set of polynomials whose common zeros are the points.
For example,
1. f(unit circle at the origin) = { x^2 + y^2 - 1 }, because all points on the unit circle satisfy x^2 + y^2 - 1 = 0.
2. f(the full space |R^2) = { 0 } because the constant zero / the zero polynomial is zero on the entire plane.
3. f(empty set) = { 1 } because the polynomial/constant 1 is Nonzero on the entire plane.
4. f({all points on either the X axis or the y axis }) = { xy }, because points on either the X axis or the y axis satisfy X = 0 or y = 0, which is implied by xy = 0
5. The intersection of the XY axes and the unit circle, which are the points { (+-1, +-1) } is cut out by the common roots of the polynomials { XY, x^2 + y^2 - 1 }.
After some rumination, one will notice that as we increase the number of "points", we will need to decrease the number of polynomials: each polynomial is a constraint, so having more polynomials is having less points that satisfy these constrains.
This is the crux of the contravariance between algebra and geometry: geometry describes the thing in itself, algebra describes how to get at the thing using constraints. These will always be dual to each other.
How did I do at an attempt at an explanation?
Re: Contravariant Functors Are Weird
#6I was super confused by contravariant functors until someone gave me a concrete example of an instance of it as "the left side of an arrow". With a regular functor you have: fmap :: Functor f => (a -> b) -> f a -> f b and you can think of something relatively straightforward type that fulfills it it, e.g.: newtype Identity a = Identity a instance Functor Identity where fmap f (Identity x) = Identity (f x) With a cont…
A slightly more concrete version of this is
data Predicate a = Predicate (a -> Bool)
Formally, you get the instance
contramap :: (b -> a) -> Predicate a -> Predicate b
contramap :: (b -> a) -> (a -> Bool) -> (b -> Bool)
some thought reveals that A -> B may tell us inconsistent colourings. For example, say we have a map {red, green} -> { b } where both "red" and "green" map to "b". So what color do we assign "b"? There is no reasonable choice.
On the other hand, say we have a function B -> A. Since each element in b maps to one element of A, we can say
color(b) = color of element that b maps to.
I tend to imagine the function from B to A as threads, whose endpoints in A are soaked with dye. This dye "moves backwards" towards B. The uniqueness in colors assigned to B is given by the fact that we can only have one thread from each point in B.
Re: Contravariant Functors Are Weird
#7Let me give you another example:
Let X be a set, and
Fun(X) = { real valued functions on X }.
Indeed, if $F: X -> Y$ is a map between set, and f \in Fun(Y). Then you have a natural function $f \circ F: X -> IR \in Fun(X)$. This is sometimes called a pull-back of $f$.
Functors of the kind Space -> { some stuff* that lives on X } are often contra-variant. E.g. functions, vector bundles, sheaves, differential forms, etc.
Re: Contravariant Functors Are Weird
#8Contravariant functors are actually really nice. The classic example from maths is the spectrum (Spec) of a ring R. As a functor, Spec(R) = the set of prime ideals of R. An example anyone can understand: all the multiples of prime numbers p Z, in the integers Z. Let R -> S is a ring homomorphism, then there is an induced map Spec(S) -> Spec(R). Spec establishes a connection between the category of rings and topologic…
While I know precisely what you are saying (have been learning scheme theory this summer), this is hardly an accessible example to pure math undergrads , let alone someone who's attempting to learn some functional programming, with no heavy experience with abstract algebra. First of all, why use Spec? Use ideals/varieties, it contains roughly the same data, while being way better to intuit. I'll put my money where my…
Let's just define Spec(R) = Hom(R,-) and call it a day.
Re: Contravariant Functors Are Weird
#9One thing I've never understood is polarity. To my understanding, positive types are defined in terms of their introduction rules and negative types are defined in terms of their elimination rules. However, don't types both have introduction and elimination rules, making them positive or negative based on how you choose to define them?
Also, how does polarity (emphasis on introduction versus elimination rules) relate to variance, as this article presents?
Re: Contravariant Functors Are Weird
#10Contravariant functors are actually really nice. The classic example from maths is the spectrum (Spec) of a ring R. As a functor, Spec(R) = the set of prime ideals of R. An example anyone can understand: all the multiples of prime numbers p Z, in the integers Z. Let R -> S is a ring homomorphism, then there is an induced map Spec(S) -> Spec(R). Spec establishes a connection between the category of rings and topologic…
While I know precisely what you are saying (have been learning scheme theory this summer), this is hardly an accessible example to pure math undergrads , let alone someone who's attempting to learn some functional programming, with no heavy experience with abstract algebra. First of all, why use Spec? Use ideals/varieties, it contains roughly the same data, while being way better to intuit. I'll put my money where my…
I have undergrad-level understanding of both abstract algebra and functional programming, and I have absolutely no idea how either your or the GP's example are connected to contravariant functors as understood through the lens of functional programming.