3 ms·

Contravariant 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 id

by foxes 6y ago

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

bollu 6y ago
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?
- euiq 6y ago
  Let's just define Spec(R) = Hom(R,-) and call it a day.
  - DanielMcLaury 6y ago
    This is why affine schemes as a thing never really took off until Grothendieck, despite Noether and Krull noting some of their interesting properties decades before. If you're just using affine schemes you don't get anything you don't get just by doing commutative algebra. However, once you start gluing affine schemes together, you start getting things that represent functors you can't represent if you're working over the category of commutative rings alone.
- Sharlin 6y ago
  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.
  - foxes 6y ago
    Maybe a good example that ties both together is some sort of filter on a list? If you add more constraints (more processing) the list gets smaller. Suppose I have a function f : x -> y. x -> y is also a functor in y. If you have an x-> y but want x->z, you can use y->z and adjust your original function by post processing the output of f. However suppose you want w -> y but you still only have f. You need to post process with w->x. So f is covariant in y, contravariant in x. Things change in the opposite direction of the adaptor. Perhaps serialisation is a useful example? Perhaps contravariance becomes even more useful if you use it in some profunctor dimap where you have a producer and consumer and process, eg moving through a data structure and pre/post processing things. https://www.youtube.com/watch?v=OJtGECfksds https://www.youtube.com/watch?v=OJtGECfksds
    - magicalhippo 6y ago

by foxes 6y ago

bollu 6y ago

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?

euiq 6y ago
Let's just define Spec(R) = Hom(R,-) and call it a day.
- DanielMcLaury 6y ago
  This is why affine schemes as a thing never really took off until Grothendieck, despite Noether and Krull noting some of their interesting properties decades before. If you're just using affine schemes you don't get anything you don't get just by doing commutative algebra. However, once you start gluing affine schemes together, you start getting things that represent functors you can't represent if you're working over the category of commutative rings alone.
Sharlin 6y ago
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.
- foxes 6y ago
  Maybe a good example that ties both together is some sort of filter on a list? If you add more constraints (more processing) the list gets smaller. Suppose I have a function f : x -> y. x -> y is also a functor in y. If you have an x-> y but want x->z, you can use y->z and adjust your original function by post processing the output of f. However suppose you want w -> y but you still only have f. You need to post process with w->x. So f is covariant in y, contravariant in x. Things change in the opposite direction of the adaptor. Perhaps serialisation is a useful example? Perhaps contravariance becomes even more useful if you use it in some profunctor dimap where you have a producer and consumer and process, eg moving through a data structure and pre/post processing things. https://www.youtube.com/watch?v=OJtGECfksds https://www.youtube.com/watch?v=OJtGECfksds
  - magicalhippo 6y ago