Haskell in 5 steps - HaskellWiki

System.IO

Text.Megaparsec.Char

Megaparsec tutorial

aoc2024/07-01-operations/app/Puzzle.hs at d23ee9139e6645022504fce2dc26f39601e66933 · mcclure/aoc2024

Advent of Code 2024 challenge (laid-back/"babel" version) - mcclure/aoc2024

This video is the only thing I've ever seen that made "categories" make sense to me

So the video takes about four minutes to start getting to the point, and frankly I'm not sure it will make much sense to someone who doesn't already sorta get group theory, but I stumbled on this YouTube video: A Sensible Introduction to Category Theory": YouTube link [https://staging.cohostcdn.org/attachment/474a951d-02f2-4a93-831d-c98a11f37a1b/cateogry.png] [https://www.youtube.com/watch?v=yAi3XWCBkDo] And the critical idea in this video that made things click for me is: Categories are about things that can be composed. When category theory people start trying to describe it they often go on about "structure preserving maps", and that does seem to be what the theory is mainly used to talk about, but a category itself is something simpler: 1. You have a collection¹ of things; 2. You have a collection of relationships between the things (just defined pairs that mean something to you; these are the "morphisms") and 3. You know how to compose the relationships ("morphisms"). Composing the relationships has to follow an associativity law, and there have to exist "identity morphisms" for every object that "do nothing" (in the sense that if you have an a -> b relationship, "precomposing" the identity for a, or "postcomposing" the identity for b, is "equivalent" to just a -> b within whatever meaning the relationship you defined has). And... that's all. So usually the morphisms are things "shaped like" one-argument functions so that they can stand in for set injections or group homomorphisms or continuous functions between topologies, and in these cases, they are structure-preserving maps because that's what we decided to consider. But the video gives a much simpler example of a category where the objects are real numbers, and the morphisms are every accurate instance of "less than or equal to". There's a morphism X -> Y if X ≤ Y. Composition is just the trivial stringing together X ≤ Y ≤ Z. The identity is comparing a number to itself. Some morphisms don't exist, like there is no 3 -> 2 because in fact 3 is larger than 2, but that's fine. What's important is when relationships exist, you know how to compose them. So if this is all category theory is, this explains why computer scientists latch onto it so hard, and why when category theorists start talking it sometimes sounds like they're just doing graph theory with some slightly obtuse terminology. Because they are. I still think their terminology is obtuse, but at least now I get why they're doing it! I DON'T KNOW WHAT A "GROUP" IS AND I DON'T GET WHY YOU THINK THIS IS INTERESTING ...Well. ---------------------------------------- Okay. So did you ever have a day in elementary school that the teacher taught you about "properties"? Like, the "commutative property" meaning that 3 + 4 and 4 + 3 are the same. So in 1854 this guy named Arthur Cayley started writing down all the properties of grade-school number-line addition and subtraction and asked the question: Imagine we had this list of properties², but we didn't know what "numbers" were. Say we started trying to write proofs about the behavior of numbers based only on these properties. What would we have? It turns out you can reproduce quite a lot of math about the integers, but Cayley noticed also you can reproduce interesting behaviors of some other things 1800s mathematicians were playing with that were not numbers, like substitution ciphers and matrices and quaternions (an unbelievably freakish thing involving imaginary numbers but more imaginary), all of which follow those same properties. He named these things "groups" (i.e., the quaternions are "a group" because they follow the rules for a group) after a term the substitution cipher people had been using. Once people started picking at the group idea they started realizing certain groups were interchangeable. Like, if you start imagining groups where there are exactly four "numbers" to do arithmetic on, it turns out there are only two of those. Two groups of size four, I mean. Any other group of size four you try to invent will just turn out to be one of the main two in disguise. This interchangeability idea turned out to be incredibly important in the twentieth century because it meant we could convert³ things that are hard to do math on into things that are easy to do math on, do the math, and then convert back. Like at some point someone figured out the group quaternions of magnitude one (a subgroup of the quaternions) are exactly interchangeable with the group of rotations in three dimensions, making graphics programmers miserable for the rest of time. Groups turned out to be the first acquisition in the zoo of "abstract algebra". If you add a second operation (cuz maybe you want to add and multiply) to a group we call that a ring, and if you add some more properties to the ring we call that a field, and there's various categories⁴ like this that if you start with "I have a set and these binary operators" you can slot it into one of the categories based on how many of the standard properties the operators follow and now you know lots of useful facts about it and possibly have a list of well-researched existing [groups, rings, fields] that the thing you invented is convertible from or into. Anyway I think the reason this video jumped out to me is that by just plainly stating what the definition of a Category is it gave me a way of kind of sorting Categories into the abstract algebra zoo, or an annex to the zoo maybe. Categories are about one-argument functions ("morphisms") where the abstract algebra beasties are all about two-argument functions (binary operators) but that's not such an interesting distinction to me. Groups are about things you can add (in some sense) and Categories are about things you can compose (in some sense) but you can think of either as being about collections and the properties those collections follow, and thinking about it that way gives me a way to bring category theory (which I've never understood) into context with something I do understand. Although I do still wish their terminology were not so obtuse. ¹ The word "collection" is used in many definitions of "a Category" I find and it seems to be intentionally not be defined in any rigorous way, I assume because they don't want to paint themselves in a corner where they say "a set of objects" and now all of a sudden they can't talk about categories where the objects form a proper class. I do hope the loosey-goosey terminology there doesn't turn out to create problems of unsoundness. ² Though commutativity wasn't on his list actually. Adding commutativity to a group gets you an "abelian group", and rings (which I mention a little later on) are actually based on abelian groups, not groups. ³ I couldn't find any natural way to just slip this in here: The "conversion" from one group to another I'm handwaving here is called a "homomorphism", which you might notice I mentioned earlier as being the "morphism" relationship that category theory considers important on groups. For the Category of groups the "objects" are the groups themselves, the "morphisms" are the homomorphisms/conversions between groups, and composition means performing the homomorphisms serially. ⁴ Notice my use of the lowercase letter here⁵. ⁵ …although incidentally all the things I mention here are also Categories.