Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Category Theory Illustrated – Natural Transformations

abuseofnotation.github.io

Post reply on HN
Print view View original

31–40 of 86 posts

Re: Category Theory Illustrated – Natural Transformations

#31

Post by ajkjk »

ctenb wrote: post #23
tristramb wrote: post #17

Earlier quoted context omitted.

Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe. At first this might seem a perverse thing to do as mappings seem more complex than sets, but that is just because traditionally mappings have usually been defined in terms of sets. In set theory you can specify that two sets be equal and you can also specify that one set be an element of another. In categ…

> you can also specify that two mappings compose Two mappings with corresponding domain/codomain have to compose by definition of a category. It's not something you can specify.

That is probably what they mean by specifying that they compose.

If all you know is that you have two mappings you don't know they compose, until you get the additional information about their sources and targets. In a way that's what the source and targets are: just labels of what you can compose them with.

Re: Category Theory Illustrated – Natural Transformations

#32

Post by gcr »

Anyone who likes this might also like Stefan Miller’s paper, “a simple category theoretical understanding of category theory diagrams“, appearing in SIGBOVIK 2014. See https://sigbovik.org/2014/proceedings.pdf (starts on PDF page 65, or page 57 if you go by margin page numbers)

Re: Category Theory Illustrated – Natural Transformations

#33

Post by Twey »

hamburgererror wrote: post #8

What's the thing with category theory? I see this topic discussed quite frequently here but I don't get it why people are so into it

Category theory is popular in computer science because, at a fundamental level, they're very compatible ways of seeing the world.

In computing, we think about:

- a set of states

- with transformations between them

- including a ‘do nothing’ transformation

- that can be composed associatively (a sequence of statements `{a; b;}; c` transforms the state in the same way as a sequence of statements `a; {b; c;}`)

- but only in certain ways: some states are unreachable from other states

This is exactly the sort of thing category theory studies, so there's a lot of cross-pollination between the disciplines. Computation defines interesting properties of certain categories like ‘computation’ or ‘polynomial efficiency’ that can help category theorists track down interesting beasts to study in category theory and other branches of mathematics that have their own relationships to category theory. Meanwhile, category theory can give suggestions to computer science both about what sort of things the states and transformations can mean and also what the consequences are of defining them in different ways, i.e. how we can capture more expressive power or efficiency without straying too far from the comfort of our ‘do this then do that’ mental model.

This latter is really helpful in computer science, especially in programming language or API design, because in general it's a really hard problem to say, given a particular set of basic building blocks, what properties they'll have when combined in all the possible ways. Results in category theory usually look like that: given a set of building blocks of a particular form, you will always be able to compose them in such a way that the result has a desired property; or, no matter how they're combined, the result will never have a particular undesired property.

As an aside, it's common in a certain computer science subculture (mostly the one that likes category theory) to talk about computing in the language of typed functional programming, but if you don't already have a deep understanding of how functional programming represents computation this can hide the forest behind the trees: when a functional programmer says ‘type’ or ‘typing context’ you can think about sets of potential (sub)states of the computer.

Re: Category Theory Illustrated – Natural Transformations

#34

Post by moralestapia »

ctenb wrote: post #24
monarchwadia wrote: post #11

Earlier quoted context omitted.

For me.. It's a very useful mental model for thinking about architecture & logic

Examples? I haven't really seen many applications of CT, even though I looked for them since I find the idea of CT interesting

You have a function that does A() and another function that does B().

Upon careful inspection or after just writing/using them 10,000s of times[1] you realize they are both special cases of one general function f()[2]. Congrats, you're likely doing CT now, but barely scratching the surface, though.

Let's say you find a way to do a function factory that generates explicit instances of f() -> A() and f() -> B() at runtime for your different use cases as they are needed. You do this 100 times, 1,000 times[1] with many different functions, in many different contexts. You eventually realize that if all your functions and their signatures had the same structure[3] it would be quite easy to mix some (or all?) of them with each other, allowing you to handle a perhaps infinite amount of complexity in a way that's very clean to conceptualize and visualize. Isn't this just FP? Yes, they're very intimately related.

By this point you're 99.9999% doing CT now, but remember to shower regularly, touch grass etc.

CT formalized these structures with mathematical language, and it turns out that this line of thinking is very useful in many fields like ours (CS), Math, Physics, etc.

1. Which is what happened to me.

2. Which sometimes is a way more elegant and simple solution.

3. This term is fundamental and has way more meaning than what I could write here and what one would think on a first approach to it.

Re: Category Theory Illustrated – Natural Transformations

#35

Post by pdpi »

Twey wrote: post #33
hamburgererror wrote: post #8

What's the thing with category theory? I see this topic discussed quite frequently here but I don't get it why people are so into it

Category theory is popular in computer science because, at a fundamental level, they're very compatible ways of seeing the world. In computing, we think about: - a set of states - with transformations between them - including a ‘do nothing’ transformation - that can be composed associatively (a sequence of statements `{a; b;}; c` transforms the state in the same way as a sequence of statements `a; {b; c;}`) - but onl…

    > - with transformations between them
    >
    > - including a ‘do nothing’ transformation
    >
    > - that can be composed associatively (a sequence of statements `{a; b;}; c` transforms the state in the same way as a sequence of statements `a; {b; c;}`)
And this right here is that monoid in the famous "A monad is just a monoid in the category of endofunctors" meme.

Re: Category Theory Illustrated – Natural Transformations

#36

Post by alfiedotwtf »

tristramb wrote: post #17
hamburgererror wrote: post #8

What's the thing with category theory? I see this topic discussed quite frequently here but I don't get it why people are so into it

Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe. At first this might seem a perverse thing to do as mappings seem more complex than sets, but that is just because traditionally mappings have usually been defined in terms of sets. In set theory you can specify that two sets be equal and you can also specify that one set be an element of another. In categ…

> Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe

Why have I never seen it explained like this before. Wow, thank you!

Re: Category Theory Illustrated – Natural Transformations

#37

Post by ihm »

tristramb wrote: post #21
tristramb wrote: post #17

Earlier quoted context omitted.

Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe. At first this might seem a perverse thing to do as mappings seem more complex than sets, but that is just because traditionally mappings have usually been defined in terms of sets. In set theory you can specify that two sets be equal and you can also specify that one set be an element of another. In categ…

So category theory is really the theory of composition of mappings. I conjecture that all programming can be seen as just the composition of mappings. If this is correct then category theory is a theory of programming.

It can very much be. Here’s one example of this phenomenon (there are many others but this is the most famous): https://wiki.haskell.org/Curry-Howard-Lambek_correspondence

Re: Category Theory Illustrated – Natural Transformations

#38

Post by stared »

Twey wrote: post #33
hamburgererror wrote: post #8

What's the thing with category theory? I see this topic discussed quite frequently here but I don't get it why people are so into it

Category theory is popular in computer science because, at a fundamental level, they're very compatible ways of seeing the world. In computing, we think about: - a set of states - with transformations between them - including a ‘do nothing’ transformation - that can be composed associatively (a sequence of statements `{a; b;}; c` transforms the state in the same way as a sequence of statements `a; {b; c;}`) - but onl…

Still, what's in your opinion, the advantage of thinking in category theory rather than set theory? (For programming, not - algebraic geometry.)

I mean, all examples I heard can be directly treated with groups, monoids, and regular functions.

I know some abstract concepts that can be defined in a nice way with CT but not nearly as easy - set theory, e.g. (abstract) tensor product. Yet, for other concepts, including quantum mechanics, I have found that there is "abstract overhead" of CT with little added value.

Re: Category Theory Illustrated – Natural Transformations

#39

Post by stared »

tristramb wrote: post #17
hamburgererror wrote: post #8

What's the thing with category theory? I see this topic discussed quite frequently here but I don't get it why people are so into it

Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe. At first this might seem a perverse thing to do as mappings seem more complex than sets, but that is just because traditionally mappings have usually been defined in terms of sets. In set theory you can specify that two sets be equal and you can also specify that one set be an element of another. In categ…

> Category theory can be used to express some requirements in a very concise way.

Could you give an example in programming, what can be easier expressed in CT than with sets and functions?

Re: Category Theory Illustrated – Natural Transformations

#40

Post by tristramb »

thomasahle wrote: post #19
tristramb wrote: post #17

Earlier quoted context omitted.

Category theory is what you get when you take mappings instead of sets as the primitive objects of your universe. At first this might seem a perverse thing to do as mappings seem more complex than sets, but that is just because traditionally mappings have usually been defined in terms of sets. In set theory you can specify that two sets be equal and you can also specify that one set be an element of another. In categ…

> Category theory can be used to express some requirements in a very concise way. Can you an example?

Take a mapping a and precompose it with the identity mapping i. By the definition of the identity mapping the resulting composition is equal to a.

  i;a = a
(Here ';' represents forward composition. Mathematicians tend to use backward composition represented by '∘' but I find backward composition awkward and error-prone and so avoid using it.)

Now, if there is another mapping j that is different from i, such that

  j;a = a
then the mapping a loses information. By this I mean that if you are given the value of a(x) you cannot always determine what x was. To understand this properly you may need to work through a simple example by drawing circles, dots and arrows on a piece of paper.

If there is no such j then mapping a is said to be a monomorphism or injection (the set theoretic term) and it does not lose information.

This specification of the property 'loses information' only involves mapping equality and mapping composition. It does not involve sets or elements of sets.

An example of a mapping that loses information would be the capitalization of strings of letters. An example of a mapping that you would not want to lose information would be zip file compression.

If you alter the above specification to use post-composition (a;i = a and a;j = a) instead of pre-composition you get epimorphisms or surjections which capture the idea that a mapping constrains all the values in its codomain. I like to think of this as the mapping does not return uninitialized values or 'junk' as it is sometimes called.

Bartosz Milewski works through this in more detail (including from the set-theoretic side) in the last 10 minutes of https://www.youtube.com/watch?v=O2lZkr-aAqk&list=PLbgaMIhjbm... and the first 10 minutes of https://www.youtube.com/watch?v=NcT7CGPICzo&list=PLbgaMIhjbm....

Post reply on HN