8 ms·

I would be willing to drink the kool-aid if I saw it being used in a practical way. I always feel these posts are filled with category theory jargon without eve

I would be willing to drink the kool-aid if I saw it being used in a practical way. I always feel these posts are filled with category theory jargon without ever explaining why any of the jargon is relevant or useful. I’ve even watched some applied category theory courses online and have yet to feel I’ve gained anything substantive from them. However, as I started off with, I’m always willing to try something out or see the reason in something. Can anyone give me a practical applied way in which category theory is a benefit to your design rather than just creating higher level jargon to label your current design with?

floober 4y ago
For me, I use the simple stuff (Semigroup, Monoid, Monads, Functors, ..) the most. Often times I'll be reasoning about a problem I'm working on in Haskell and realize it is a monad and I can reuse all of the existing monadic control structures. It is also helpful the other way, where you start working with someone else's code and seeing that it is a e.g. Monad immediately tells you so much concrete info about the structure, where in a less structured language you might need to reed through a bunch of docs to understand how to manipulate some objects. The "killer app" is all of that extra structure shared throughout all of the codebases.
- picardo 4y ago
  Same here. I drank the cool aid a few years back, and started using fp-ts in my frontend projects, hoping to use algebraic data types regularly. But today all I use is the Monad. I can't find any motivation to write abstract algebra to build UI widgets.
  - floober 4y ago
    > I can't find any motivation to write abstract algebra to build UI widgets This made me chuckle, because I am at this very moment trying to apply the "tagless final style" described here[0] to a custom GUI in a personal-for-fun-and-learning ocaml project : ) [0] https://okmij.org/ftp/tagless-final/course/optimizations.html https://okmij.org/ftp/tagless-final/course/optimizations.htm...
hosh 4y ago
In Ruby and many other languages, you have this idea of a string concatenation: "foo" + "bar" -> "foobar" "foo" + "" -> "foo" That makes it a monoid. Instead of talking about OOP patterns, knowing that the "+" operator is a monoid for string objects lets us write code that is composable. Similarly, with arrays: [:foo,:bar] + [:baz] -> [:foo,:bar,:baz] [:foo,:bar] + [] -> [:foo,:bar] Some language platforms will implement the first concat, but not the latter. Without the latter, you couldn't do things like, accept an empty user input. You would have to write code like: defaults + user_input unless user_input_array.empty? This applies to things like, hashes, or even more complex objects -- such as ActiveRecord named scopes, even if they don't use a "+" operator. (But maybe, Hash objects can be "+" together instead of calling merge()) This is all applicable to how you can design libraries and DSLs that seem intuitive and easy to use. Instead of just thinking about bundling a number of methods together with a data structure, you can make sure that a single method within that bundle works the way you expected across a number of objects. You might even be using these ideas in your code, but don't realize it.
- musk_micropenis 4y ago
  Most of us can go our whole careers without the "insight" that string concatenation is a "monoid". I don't know any languages that would balk at "foo" + "" or [a, b].concat([]). This all seems academic beyond belief.
  - fdupress 4y ago
    Strings/lists under concatenation do not form a group since concatenation is not uniquely invertible. (In the sense of "there is no list -xs that you can concatenate onto xs to get the empty list.)
    - musk_micropenis 4y ago
      Again, I don't see how this piece of information is useful for a programmer. And if it is, I'll bet it's 10x more useful if expressed in more ordinary language.
wisnesky 4y ago
Category theory does provide new algorithms if you unroll all of its definitions. For example, it reveals that SQL conjunctive queries can be run both "forward" and "backward" - an algorithm that is invisible in traditional SQL literature because that literature lacks the vocabulary to even talk about what "running backward" even means - it isn't an 'inverse' relationship but an 'adjoint' one. We also use it to provide a new semantics for data integration. Link: https://www.categoricaldata.net https://www.categoricaldata.net
- zasdffaa 4y ago
  I see nothing in your link to justify what you say. Perhaps you can elaborate.
  - wisnesky 4y ago
    The way to run conjunctive SQL queries forward and backward is described in this paper, https://www.cambridge.org/core/journals/journal-of-functional-programming/article/algebraic-data-integration/AC36B1C39D4C76A18CB54F75B0D26796 https://www.cambridge.org/core/journals/journal-of-functiona... , (also available on the arxiv), where they are referred to as query 'evaluation' and 'co-evaluation', respectively. We never would have been able to discover co-evaluation if not for category theory! The previous link includes this paper, and many others.
    - charcircuit 4y ago
      So what is coevaluation and why is it useful? Please don't just point at the paper again.
      - wisnesky 4y ago
        Bi-directional data exchange has many uses. For example, given a set of conjunctive queries Q, because coeval_Q is left adjoint to eval_Q, the composition coeval_Q o eval_Q forms a monad, whose unit can be used to quantify the extent to which the original query Q is "information preserving" on a particular source (so query/data quality). As another example, we use the technique to load data into OWL ontologies from SQL sources, by specifying an OWL to SQL projection query (tends to be easy) and then running it in reverse (tends to be hard). But no doubt more applications await!
zmgsabst 4y ago
I think the real insight of category theory is you’re already doing it, eg, whiteboard diagrams. Category theory is the language of diagrams; it studies math from that perspective. However, it turns out that category theory is equivalent to type theory (ie, what computers use). So the reason why diagrams can be reliably used to represent the semantics of type theory expressions is category theory. My workflow of developing ubiquitous language with clients and then converting that into a diagram mapping classes of things and their relationships followed by translating that diagram into typed statements expressing the same semantics is applied category theory. The “category theory types” are just names for patterns in those diagrams. Trying to understand them without first getting that foundational relationship is the path to frustration — much like reading GoF before groking OOP.
- Twisol 4y ago
  > However, it turns out that category theory is equivalent to type theory (ie, what computers use). Just to elaborate on this a little, a program of type B in context of variables of types A1, A2, ..., An, can be modeled as an arrow (A1 * A2 * ... * An) -> B. (More elaborate type theories get, well, more elaborate.) The various ways you might put programs together (e.g. if-expressions, loops, ...) become various ways you can assemble arrows in your category. Sequential composition in a category is the most fundamental, since it describes dataflow from the output side of one program to the input site of another; but the other ways of composing programs together appear as additional structure on the category. Categories take "semicolon" as the most primitive notion, and that's all a category really is. In fact, if you've heard monads called "the programmable semicolon", it's because any monad induces a related category whose effectful programs `a ~> b` are really pure programs `a -> m b`, where `m` is the monad.
jerf 4y ago
"I’ve even watched some applied category theory courses online and have yet to feel I’ve gained anything substantive from them." To understand category theory's appeal in a programming context, you must understand the duality of power in programming languages. Some people call a language "powerful" when it lets you do whatever you want in the particular scope you are currently operating in, so, for instance, Ruby is a very powerful language because you can be sitting in some method in some class somewhere, and you can reach into any other class you like and rewrite that other class's methods entirely. Some call a language powerful when the language itself is capable of understanding what it is your code is doing, and further manipulating it, such as by being able to optimize it well, or offer further features on top of your language like lifetime management in Rust. This type of power comes from restricting what a programmer is capable of doing at any given moment. If your idea of "power" comes from the first sort of language, then category theory is going to be of very little value to you in my opinion. You pretty much have to be using something as deeply restrictive as Haskell to care about it at all. I am not making a value judgment here. If you never want to program in Haskell, then by all means keep walking past category theory. Haskell is very much a language that is powerful in the second way. It restricts the programmer moreso than any other comparable language; the only languages that go farther essentially go right past the limit of what you could call a "general purpose language" and I daresay there are those who would assert that Haskell is already past that point. Category theory then becomes interesting because it is simultaneously a set of deeply restricted primitives that are also capable of doing a lot of real work, and category theory provides a vocabulary for talking about such restricted primitives in a coherent way. There is some sense in which it doesn't "need" to be category theory; it is perfectly possible to come to an understanding of all the relevant concepts purely in a Haskell context without reference to "category theory", hence the completely correct claim that Haskell in no way necessitates "understanding category theory". You will hear terminology from it, but you won't need to separately "study" it to understand Haskell; you'll simply pick up on how Haskell is using the terminology on your own just fine. (Real mathematical category theory actually differs in a couple of slight, but important ways from what Haskell uses.) So, it becomes possible it Haskell to say things like "You don't really need a full monad for that; an applicative can do that just fine", and this has meaning (basically, "you used more power than was necessary, so you're missing out on the additional things that can be built on top of a lower-power, higher-guarantee primitive as a result") in the community. This mindset of using minimal-power primitives and "category theory" are not technically the same thing, but once you get deeply into using minimal-power primitives pervasively, and composing them together, you are basically stepping into category theory space anyhow. You can't help but end up rediscovering the same things category theorists discovered; there are a hundred paths to category theory and this is one of the more clear ones of them, despite the aforementioned slight differences. I'd say it's a fair thing to understand it as this progression; Haskell was the language that decided to study how much we could do with how little, and it so happens the branch of math that this ends up leading to is category theory, but as a programmer it isn't necessary to "study" category theory in Haskell. You'll osmose it just fine, if not better by concretely using it than any dry study could produce. To be honest, I'm not even convinced there's that much value in "studying" category theory as its own thing as a programmer. I never studied it formally, and I wrote Haskell just fine, and I understand what the people using category theory terms are talking about in a Haskell context. If nothing else, you can always check the Haskell code. There is a nearby parallel universe where the Haskell-Prime community in the late 1990s and early 2000s was otherwise the same, but nobody involved knew category theory terminology, so "monad" is called something else, nobody talks about category theory, and nobody has any angst over it, despite the language being otherwise completely identical other than the renames. In this universe, some people do point out that this thing in Haskell-Prime corresponds to some terms in category theory, but this is seen as nothing more than moderately interesting trivia and yet another place where category theory was rediscovered. But I bet their Monad-Prime tutorials still suck.
kelseyfrog 4y ago
Category theory as it applies to programming is not dissimilar to learning design patterns. Some people go their whole careers never touching them and write perfectly fine programs. The same is true for category theory. Those who learn either or both, have a larger set of mental abstractions that largely transcend any one programming language. They can say, this thing and that thing share a common salient property through a certain abstract pattern. There is a certain sense of mathematical beauty in recognizing common patterns and mechanisms. There is also the choice of subtly or drastically altering one's coding style. The same with each, a programmer can use just the right design pattern in just the right place and perhaps simplify or codify a section so that it's easier to understand the next time around (or decide not to!) or they can go completely wild and over-pattern their code. The same applies to category theory. One can recognize that some section is actually a closed reduction and accepts any semigroup and then decide to codify this into the program or not. I tend to be a collector of ideas, so learning category theory and it's application in programming gives me all these little gems and ways to re-understabd code. Sometimes I use them and sometimes I don't, but my life is more joyful just knowing them regardless.
rssoconnor 4y ago
Apologies for the jargon, but there isn't room in a comment box for a detailed explanation. "The Essence of the Iterator Pattern"[0] posed an open problem in type theory as to whether or not "lawful traversals", of type `∀ F:Applicative. (X -> F X) -> (B -> F B)` could appear for anything other than what is called a "finitary container"[1], B := ∃S. X^(P S) where the (P S) is a natural number (or equivalently a polynomial functor B := ∃n. C_n * X^n). Or rather, there was an open question as to what laws are needed so that "lawful traversals" would imply that B is a finitary container. Eventually I came up with a fairly long proof[2] that the original laws proposed in "The Essence of the Iterator Pattern" were in fact adequate to ensure that B is a finitary container. Mauro Jaskelioff[3] rewrote my proof in the language of category theory to be few lines long: use Yoneda lemma twice and a few other manipulations. Anyhow, the upshot of reframing this as a simple argument in Category Theory meant that, with the help of James Deikun, I was able go generalize the argument to other types of containers. In particular we were able to device a new kind of "optic"[6] for "Naperian containers" (also known as a representable functors) which are of the form B:=P->X (aka containers with a fixed shape). Since then people have been able to come up with a whole host of classes of containers, optics for those classes, representations for those optics, and a complete characterization of operations available for those classes of containers, and how to make different container classes transparently composable with each other[4]. For example, we know that finitary containers are characterized by their traversal function (i.e the essence of the iterator pattern). Naperian containers are characterized by their zip function. Unary containers are characterized by a pair of getter and setter functions, something implicitly understood by many programmers. And so on. I don't know if all this means that people should learn category theory. In fact, I really only know the basics, and I can almost but not quite follow "Doubles for Monoidal Categories"[5]. But now-a-days I have an "optical" view of the containers in, and forming, my data structures, slotting them into various named classes of containers and then knowing exactly what operations are available and how to compose them. [0]https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator... [1]https://en.wikipedia.org/wiki/Container_(type_theory) https://en.wikipedia.org/wiki/Container_(type_theory) [2]https://github.com/coq-contribs/traversable-fincontainer https://github.com/coq-contribs/traversable-fincontainer [3]https://arxiv.org/abs/1402.1699 https://arxiv.org/abs/1402.1699 [4]https://arxiv.org/abs/2001.07488 https://arxiv.org/abs/2001.07488 [5]https://golem.ph.utexas.edu/category/2019/11/doubles_for_monoidal_categorie.html https://golem.ph.utexas.edu/category/2019/11/doubles_for_mon... [6]https://r6research.livejournal.com/28050.html https://r6research.livejournal.com/28050.html
deltaseventhree 4y ago
Knowing category theory helps you better design interfaces. Exactly like the interfaces in OOP. Alot of the generic interfaces you design in OOP end up being useless. Never re-used and pointless. You never needed to make these interfaces in the first place In category theory, you will be able to create and identify interfaces that are universal, general and widely used throughout your code. Category theory allows you to organize your code efficiently via interfaces and thus enable Maximum reuse of logic. When creating an interface you largely use your gut. Category theory allows you to draw from established interfaces that are more fundamental. Basically class types in haskell. If you want to see the benefit of category theory, you really need to use haskell. Monads for example are a pattern from category theory. Also a lot of what people are talking about in this thread is exactly what I'm saying^^. I'm just saying it in less complicated jargon.
- Twisol 4y ago
  > you really need to use haskell. Or Scala. They're the only two common-use languages I'm aware of whose type systems are expressive enough to define what a monad (or a category, or a ...) is internally. Of course you can identify particular monads (or ...) in any language, but you can't talk about them inside most languages.
  - larve 4y ago
    C++ fits the bill as well (!) I wager that you can get pretty far with compile-time macros, even as rudimentary as C's, to encoder a fair bit of generic monad machinery.
pinjo333 4y ago
They describe composable patterns with a clear hierarchy. The jargon is useful, since it is the language in which they are described. I mean Turing machine, filesystem, socket and pipe are also jargon. A good example is LINQ, they use monads and functors. They just gave them other names.
epgui 4y ago
It's not kool-aid, it's applied maths. Just because you don't already know and understand it (and hence don't see the benefit of it) doesn't mean there's no clear and obvious benefit. But you do have to learn before you understand.
- salty_biscuits 4y ago
  To be fair though, there is a wide spectrum of "usefulness" for pure mathematics concepts in applied mathematics. For less contemporary examples you don't need to know about Lebesgue measure to do practical numerical quadrature for applications. Or you don't need to know that rotation matrices are part of the SO3 group to do computer graphics. Sometimes the abstractions are powerful and sometimes they are kind of a distraction (or even make communication a problem). There typically needs to be a super compelling application to motivate a shift in baseline knowledge.
DalekBaldwin 4y ago
Here are some of the more practical insights for medium/large-scale software design that have stuck with me. They apply regardless of whether I'm working in a language that lets me easily express categorical-ish stuff in the type system: - Triviality The most trivial cases are actually the most important. If I build a little DSL, I give it an explicit "identity" construction in the internal representation, and use it liberally in the implementation, transformation phases, and tests, even though obviously its denotation as a no-op will be optimized away by my little DSL compiler, and it may not even be exposed as an atomic construct in the user-facing representation. - Free constructions When it's difficult to separate a model from an implementation, when simple interfaces are not enough because the model and implementation are substantially complex, multilayered systems on their own, often the answer is to use a free construction. Free constructions are a killer tool for allowing the late-binding of rather complex concerns, while allowing for reasoning, transformation, and testing of the underlying components without worrying about that late-bound behavior. "Late-bound" here does not have to mean OO-style dynamic dispatch -- in fact now you have more expressive power to fuse some behaviors together in a staged manner with no runtime indirection, or to make other behaviors legitimately dynamic, differing from one call to the next. Tradeoffs in the flexibility/performance space are easier to make, to change, and to self-document. This is particularly useful when you need to start addressing "meta" concerns as actual user-facing concerns -- when your project matures from a simple application that does Foo into a suite of tools for manipulating and reasoning about Foo and Fooness. Your Foo engine currently just does Foo, but now you want it to not just do Foo, but return a description of all the sub-Foo tasks it performed -- but only if the configuration has requested those details, because sometimes the user just wants to Foo. So you embed the basic, non-meta-level entities representing the actual component tasks in a free construction, compose them within that free construction, and implement the configurable details of that composition elsewhere. - "Sameness" Making clear distinctions between different notions of sameness is important. Identity, equality, isomorphism, adjointness -- sure, you might never explicitly implement an adjunction, but these are important notions to keep separate, at least conceptually if not concretely in source code entities, as a piece of software grows more complex. If you treat two things as fundamentally the same in more ways than they really are, you reach a point where you now can no longer recover crucial information in a later phase of computation. In an indexed/fibered construction, this X may be basically the same as that X, but this X, viewed as the image of a transformation applied to Y is quite different from that X, viewed as the image of a transformation applied to Z, although the images are equal. So can I just pass my X's around everywhere, or do I need to pass or at least store somewhere the references to Y and Z? What if computationally I can only get an X as the result of applying a function to Y, but conceptually the functional dependency (that is, as a mathematical function) points the other way around, from X to Y? Paying attention to these easy-to-miss distinctions can save you from code-architecting yourself into a corner. You may discover that the true reserve currency of the problem domain is Y when it looks like X, or vice versa.
ukj 4y ago
Category theory is to functional/declarative programming what design patterns are to OO programming. Patterns for decomposing problems and composing solutions. To ask “How is it useful?” Is to ask “How are design patterns useful in OO?”. But you already know the answer… Is there an advantage over just inventing your own vocabulary? Yeah! You don’t have to reinvent 70+ years of Mathematics, or teach your language to other people before you can have a meaningful design discussion.
- charcircuit 4y ago
  >You don’t have to reinvent 70+ years of Mathematics What do those 70 years of mathematics do for me as a software engineer? >or teach your language to other people before you can have a meaningful design discussion. It's the other way around. Most engineers will have no clue what you are saying.
  - ukj 4y ago
    >What do those 70 years of mathematics do for me as a software engineer? You mean other than inventing the entire industry in which you work? It's a weird question that I have no idea how to answer for you. What is 70+ years of computer science doing for you as a software engineer? Are you standing on the shoulder of giants; or are you inventing/re-discovering everything by yourself from first principles? >It's the other way around. Most engineers will have no clue what you are saying. So how do engineers understand each other if we all invent our own meta-language to speak about software design in the abstract? Misscommunication is what happens by default unless you intentionally become part of a community and learn the meta-language. Mathematics is one such community which has existed for millenia and benefits from the network effect. It's an anti-entropy thing. There are many parallels here to the Tower of Babel.
    - charcircuit 4y ago
      >What is 70+ years of computer science doing for you as a software engineer? No, what does category theory unlock from mathematics that I can not get without it.
mrkeen 4y ago
> I always feel these posts are filled with category theory jargon The 80/20 rule really applies here. Most of the time there's only a few key type classes that people use. Pretty much just Monad, Monoid, Applicative, Functor. If you grok those, then what people say makes a lot more sense. > Can anyone give me a practical applied way in which category theory is a benefit to your design Monad is probably the best example, because so many different, important libraries use it. Once you know how to code against one of them, you kinda know how to code against all of them! The following is code written in the STM monad. It handles all the locking and concurrency for me: transfer x from to = do f <- getAccountMoney from when (f < x) abort t <- getAccountMoney to setAccountMoney to (t + x) setAccountMoney from (f - x) This same code could be in the State monad (excluding the line with 'abort' on it). Or it could be in the ST monad. Or the IO monad. Each of those is doing radically different things under the hood, which I don't have the brainpower to understand. But because they expose a monadic interface to me, I already know how to drive them using simple, readable, high-level code. As well as the 4 monads mentioned above, parsers are monadic, same with Maybe and Either, List. The main concurrency library 'async' is also monadic (though it just uses the IO monad rather than defining an Async monad). Often the people writing your mainstream libraries know this stuff too. If you're calling flatMap (or thenCompose), you're calling monadic code. The writers just shirk from calling it monadic because they're worried people will suddenly not understand it if it has a scary name.
- shakow 4y ago
  Looks like to the hard part is ‶handl[ing] all the locking and concurrency″ with a pretty interface; that it satisfies the definition of a monad is a convenience because the `do` keyword requires it, but so would it be if it satisfied any other one, wouldn't it?
  - larve 4y ago
    I would say it's the other way around: 1. Because the underlying concept for handling composing locks (STM, which I don't know much about, but I'm going to assume is a way to wrap operations within a transaction) is sound 2. it is easy to define the corresponding monad 3. which makes it usable in a do notation 4. producing readable and future-proof code The step 2 is almost trivial, 1 is where the thinking is at. The do notation is nice to have, but not that important (to me at least). I have no problem writing this in CPS style when using javascript or c++: const transfer = (x, from, to, onSuccess, onError) => { return getAccountMoney(from, (f) => { if (f < x) { return onError(); } else { return getAccountMoney(to, (t) => { return setAccountMoney(to, t+x, () => { return setAccountMoney(from, f-x, onSuccess, onError); }, onError); }, onError); }, onError); } } The main point is that I can add 80 edge cases to this and it will continue to compose nicely, not a single lock in sight.
gilmi 4y ago
If you have 24 minutes, George Wilson's talk about propagators is really interesting and demonstrates how we can find solutions to problems by looking at math. https://www.youtube.com/watch?v=nY1BCv3xn24 https://www.youtube.com/watch?v=nY1BCv3xn24
franknstein 4y ago
I feel like another application which is maybe not talked about all that much is that knowing category theory gives you power to name some design pattern, google that, and tap into that vast mathematical knowledge that humanity already discovered. This becomes incredibly valuable once you become aware of how much you don't know. Or maybe just write that bare manimum code that works, idc. Oh and also when you recognize your design to be something from ct its probably quality. Shit code cant be described with simple math (simple as in all math is simple, not as in math that is easy to understand).
klodolph 4y ago
I’m a math major. I learned category theory in school. I think of category theory as an easy way to remember things. If some concept can be expressed as category theory, it can often be expressed in a very simple way that’s easy to remember. However, if you try to teach math using category theory from the beginning, it feels a little like trying to teach literature to someone who can’t read yet. Anything directly useful from category theory can be expressed as something more concrete, so you don’t NEED category theory, in that sense. But category theory has the funny ability to generalize results. So you take some theorem you figured out, express it using category theory, and realize that it applies to a ton of different fields that you weren’t even considering. The effort to reward of category theory is not especially high for most people. It did give us some cool things which are slowly filtering into day to day life—algebraic data types and software transactional memory are two developments that owe a lot to category theory.
- barbariangrunge 4y ago
  Pardon me: what IS category theory?
  - klodolph 4y ago
    Almost every field you can study in mathematics can be thought of as a “category”, and when you take a math class in undergrad, it usually focuses on one or two specific categories. Category theory is the study of categories in general. As in, “What if, instead of studying a specific field of math, you studied what these different fields had in common, and the relationships between them.” The part where it gets wacky is when you realize that “categories” is, itself, a category. https://youtu.be/yAi3XWCBkDo https://youtu.be/yAi3XWCBkDo

floober 4y ago

For me, I use the simple stuff (Semigroup, Monoid, Monads, Functors, ..) the most. Often times I'll be reasoning about a problem I'm working on in Haskell and realize it is a monad and I can reuse all of the existing monadic control structures. It is also helpful the other way, where you start working with someone else's code and seeing that it is a e.g. Monad immediately tells you so much concrete info about the structure, where in a less structured language you might need to reed through a bunch of docs to understand how to manipulate some objects. The "killer app" is all of that extra structure shared throughout all of the codebases.

picardo 4y ago
Same here. I drank the cool aid a few years back, and started using fp-ts in my frontend projects, hoping to use algebraic data types regularly. But today all I use is the Monad. I can't find any motivation to write abstract algebra to build UI widgets.
- floober 4y ago
  > I can't find any motivation to write abstract algebra to build UI widgets This made me chuckle, because I am at this very moment trying to apply the "tagless final style" described here[0] to a custom GUI in a personal-for-fun-and-learning ocaml project : ) [0] https://okmij.org/ftp/tagless-final/course/optimizations.html https://okmij.org/ftp/tagless-final/course/optimizations.htm...

hosh 4y ago

In Ruby and many other languages, you have this idea of a string concatenation: "foo" + "bar" -> "foobar" "foo" + "" -> "foo" That makes it a monoid. Instead of talking about OOP patterns, knowing that the "+" operator is a monoid for string objects lets us write code that is composable. Similarly, with arrays: [:foo,:bar] + [:baz] -> [:foo,:bar,:baz] [:foo,:bar] + [] -> [:foo,:bar] Some language platforms will implement the first concat, but not the latter. Without the latter, you couldn't do things like, accept an empty user input. You would have to write code like: defaults + user_input unless user_input_array.empty? This applies to things like, hashes, or even more complex objects -- such as ActiveRecord named scopes, even if they don't use a "+" operator. (But maybe, Hash objects can be "+" together instead of calling merge()) This is all applicable to how you can design libraries and DSLs that seem intuitive and easy to use. Instead of just thinking about bundling a number of methods together with a data structure, you can make sure that a single method within that bundle works the way you expected across a number of objects. You might even be using these ideas in your code, but don't realize it.

musk_micropenis 4y ago
Most of us can go our whole careers without the "insight" that string concatenation is a "monoid". I don't know any languages that would balk at "foo" + "" or [a, b].concat([]). This all seems academic beyond belief.
- fdupress 4y ago
  Strings/lists under concatenation do not form a group since concatenation is not uniquely invertible. (In the sense of "there is no list -xs that you can concatenate onto xs to get the empty list.)
  - musk_micropenis 4y ago
    Again, I don't see how this piece of information is useful for a programmer. And if it is, I'll bet it's 10x more useful if expressed in more ordinary language.

wisnesky 4y ago

Category theory does provide new algorithms if you unroll all of its definitions. For example, it reveals that SQL conjunctive queries can be run both "forward" and "backward" - an algorithm that is invisible in traditional SQL literature because that literature lacks the vocabulary to even talk about what "running backward" even means - it isn't an 'inverse' relationship but an 'adjoint' one. We also use it to provide a new semantics for data integration. Link: https://www.categoricaldata.net https://www.categoricaldata.net

zasdffaa 4y ago
I see nothing in your link to justify what you say. Perhaps you can elaborate.
- wisnesky 4y ago
  The way to run conjunctive SQL queries forward and backward is described in this paper, https://www.cambridge.org/core/journals/journal-of-functional-programming/article/algebraic-data-integration/AC36B1C39D4C76A18CB54F75B0D26796 https://www.cambridge.org/core/journals/journal-of-functiona... , (also available on the arxiv), where they are referred to as query 'evaluation' and 'co-evaluation', respectively. We never would have been able to discover co-evaluation if not for category theory! The previous link includes this paper, and many others.
  - charcircuit 4y ago
    So what is coevaluation and why is it useful? Please don't just point at the paper again.
    - wisnesky 4y ago
      Bi-directional data exchange has many uses. For example, given a set of conjunctive queries Q, because coeval_Q is left adjoint to eval_Q, the composition coeval_Q o eval_Q forms a monad, whose unit can be used to quantify the extent to which the original query Q is "information preserving" on a particular source (so query/data quality). As another example, we use the technique to load data into OWL ontologies from SQL sources, by specifying an OWL to SQL projection query (tends to be easy) and then running it in reverse (tends to be hard). But no doubt more applications await!

zmgsabst 4y ago

I think the real insight of category theory is you’re already doing it, eg, whiteboard diagrams. Category theory is the language of diagrams; it studies math from that perspective. However, it turns out that category theory is equivalent to type theory (ie, what computers use). So the reason why diagrams can be reliably used to represent the semantics of type theory expressions is category theory. My workflow of developing ubiquitous language with clients and then converting that into a diagram mapping classes of things and their relationships followed by translating that diagram into typed statements expressing the same semantics is applied category theory. The “category theory types” are just names for patterns in those diagrams. Trying to understand them without first getting that foundational relationship is the path to frustration — much like reading GoF before groking OOP.

Twisol 4y ago
> However, it turns out that category theory is equivalent to type theory (ie, what computers use). Just to elaborate on this a little, a program of type B in context of variables of types A1, A2, ..., An, can be modeled as an arrow (A1 * A2 * ... * An) -> B. (More elaborate type theories get, well, more elaborate.) The various ways you might put programs together (e.g. if-expressions, loops, ...) become various ways you can assemble arrows in your category. Sequential composition in a category is the most fundamental, since it describes dataflow from the output side of one program to the input site of another; but the other ways of composing programs together appear as additional structure on the category. Categories take "semicolon" as the most primitive notion, and that's all a category really is. In fact, if you've heard monads called "the programmable semicolon", it's because any monad induces a related category whose effectful programs `a ~> b` are really pure programs `a -> m b`, where `m` is the monad.

jerf 4y ago

"I’ve even watched some applied category theory courses online and have yet to feel I’ve gained anything substantive from them." To understand category theory's appeal in a programming context, you must understand the duality of power in programming languages. Some people call a language "powerful" when it lets you do whatever you want in the particular scope you are currently operating in, so, for instance, Ruby is a very powerful language because you can be sitting in some method in some class somewhere, and you can reach into any other class you like and rewrite that other class's methods entirely. Some call a language powerful when the language itself is capable of understanding what it is your code is doing, and further manipulating it, such as by being able to optimize it well, or offer further features on top of your language like lifetime management in Rust. This type of power comes from restricting what a programmer is capable of doing at any given moment. If your idea of "power" comes from the first sort of language, then category theory is going to be of very little value to you in my opinion. You pretty much have to be using something as deeply restrictive as Haskell to care about it at all. I am not making a value judgment here. If you never want to program in Haskell, then by all means keep walking past category theory. Haskell is very much a language that is powerful in the second way. It restricts the programmer moreso than any other comparable language; the only languages that go farther essentially go right past the limit of what you could call a "general purpose language" and I daresay there are those who would assert that Haskell is already past that point. Category theory then becomes interesting because it is simultaneously a set of deeply restricted primitives that are also capable of doing a lot of real work, and category theory provides a vocabulary for talking about such restricted primitives in a coherent way. There is some sense in which it doesn't "need" to be category theory; it is perfectly possible to come to an understanding of all the relevant concepts purely in a Haskell context without reference to "category theory", hence the completely correct claim that Haskell in no way necessitates "understanding category theory". You will hear terminology from it, but you won't need to separately "study" it to understand Haskell; you'll simply pick up on how Haskell is using the terminology on your own just fine. (Real mathematical category theory actually differs in a couple of slight, but important ways from what Haskell uses.) So, it becomes possible it Haskell to say things like "You don't really need a full monad for that; an applicative can do that just fine", and this has meaning (basically, "you used more power than was necessary, so you're missing out on the additional things that can be built on top of a lower-power, higher-guarantee primitive as a result") in the community. This mindset of using minimal-power primitives and "category theory" are not technically the same thing, but once you get deeply into using minimal-power primitives pervasively, and composing them together, you are basically stepping into category theory space anyhow. You can't help but end up rediscovering the same things category theorists discovered; there are a hundred paths to category theory and this is one of the more clear ones of them, despite the aforementioned slight differences. I'd say it's a fair thing to understand it as this progression; Haskell was the language that decided to study how much we could do with how little, and it so happens the branch of math that this ends up leading to is category theory, but as a programmer it isn't necessary to "study" category theory in Haskell. You'll osmose it just fine, if not better by concretely using it than any dry study could produce. To be honest, I'm not even convinced there's that much value in "studying" category theory as its own thing as a programmer. I never studied it formally, and I wrote Haskell just fine, and I understand what the people using category theory terms are talking about in a Haskell context. If nothing else, you can always check the Haskell code. There is a nearby parallel universe where the Haskell-Prime community in the late 1990s and early 2000s was otherwise the same, but nobody involved knew category theory terminology, so "monad" is called something else, nobody talks about category theory, and nobody has any angst over it, despite the language being otherwise completely identical other than the renames. In this universe, some people do point out that this thing in Haskell-Prime corresponds to some terms in category theory, but this is seen as nothing more than moderately interesting trivia and yet another place where category theory was rediscovered. But I bet their Monad-Prime tutorials still suck.

kelseyfrog 4y ago

Category theory as it applies to programming is not dissimilar to learning design patterns. Some people go their whole careers never touching them and write perfectly fine programs. The same is true for category theory. Those who learn either or both, have a larger set of mental abstractions that largely transcend any one programming language. They can say, this thing and that thing share a common salient property through a certain abstract pattern. There is a certain sense of mathematical beauty in recognizing common patterns and mechanisms. There is also the choice of subtly or drastically altering one's coding style. The same with each, a programmer can use just the right design pattern in just the right place and perhaps simplify or codify a section so that it's easier to understand the next time around (or decide not to!) or they can go completely wild and over-pattern their code. The same applies to category theory. One can recognize that some section is actually a closed reduction and accepts any semigroup and then decide to codify this into the program or not. I tend to be a collector of ideas, so learning category theory and it's application in programming gives me all these little gems and ways to re-understabd code. Sometimes I use them and sometimes I don't, but my life is more joyful just knowing them regardless.

rssoconnor 4y ago

Apologies for the jargon, but there isn't room in a comment box for a detailed explanation. "The Essence of the Iterator Pattern"[0] posed an open problem in type theory as to whether or not "lawful traversals", of type `∀ F:Applicative. (X -> F X) -> (B -> F B)` could appear for anything other than what is called a "finitary container"[1], B := ∃S. X^(P S) where the (P S) is a natural number (or equivalently a polynomial functor B := ∃n. C_n * X^n). Or rather, there was an open question as to what laws are needed so that "lawful traversals" would imply that B is a finitary container. Eventually I came up with a fairly long proof[2] that the original laws proposed in "The Essence of the Iterator Pattern" were in fact adequate to ensure that B is a finitary container. Mauro Jaskelioff[3] rewrote my proof in the language of category theory to be few lines long: use Yoneda lemma twice and a few other manipulations. Anyhow, the upshot of reframing this as a simple argument in Category Theory meant that, with the help of James Deikun, I was able go generalize the argument to other types of containers. In particular we were able to device a new kind of "optic"[6] for "Naperian containers" (also known as a representable functors) which are of the form B:=P->X (aka containers with a fixed shape). Since then people have been able to come up with a whole host of classes of containers, optics for those classes, representations for those optics, and a complete characterization of operations available for those classes of containers, and how to make different container classes transparently composable with each other[4]. For example, we know that finitary containers are characterized by their traversal function (i.e the essence of the iterator pattern). Naperian containers are characterized by their zip function. Unary containers are characterized by a pair of getter and setter functions, something implicitly understood by many programmers. And so on. I don't know if all this means that people should learn category theory. In fact, I really only know the basics, and I can almost but not quite follow "Doubles for Monoidal Categories"[5]. But now-a-days I have an "optical" view of the containers in, and forming, my data structures, slotting them into various named classes of containers and then knowing exactly what operations are available and how to compose them. [0]https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator... [1]https://en.wikipedia.org/wiki/Container_(type_theory) https://en.wikipedia.org/wiki/Container_(type_theory) [2]https://github.com/coq-contribs/traversable-fincontainer https://github.com/coq-contribs/traversable-fincontainer [3]https://arxiv.org/abs/1402.1699 https://arxiv.org/abs/1402.1699 [4]https://arxiv.org/abs/2001.07488 https://arxiv.org/abs/2001.07488 [5]https://golem.ph.utexas.edu/category/2019/11/doubles_for_monoidal_categorie.html https://golem.ph.utexas.edu/category/2019/11/doubles_for_mon... [6]https://r6research.livejournal.com/28050.html https://r6research.livejournal.com/28050.html

deltaseventhree 4y ago

Knowing category theory helps you better design interfaces. Exactly like the interfaces in OOP. Alot of the generic interfaces you design in OOP end up being useless. Never re-used and pointless. You never needed to make these interfaces in the first place In category theory, you will be able to create and identify interfaces that are universal, general and widely used throughout your code. Category theory allows you to organize your code efficiently via interfaces and thus enable Maximum reuse of logic. When creating an interface you largely use your gut. Category theory allows you to draw from established interfaces that are more fundamental. Basically class types in haskell. If you want to see the benefit of category theory, you really need to use haskell. Monads for example are a pattern from category theory. Also a lot of what people are talking about in this thread is exactly what I'm saying^^. I'm just saying it in less complicated jargon.

Twisol 4y ago
> you really need to use haskell. Or Scala. They're the only two common-use languages I'm aware of whose type systems are expressive enough to define what a monad (or a category, or a ...) is internally. Of course you can identify particular monads (or ...) in any language, but you can't talk about them inside most languages.
- larve 4y ago
  C++ fits the bill as well (!) I wager that you can get pretty far with compile-time macros, even as rudimentary as C's, to encoder a fair bit of generic monad machinery.

pinjo333 4y ago

They describe composable patterns with a clear hierarchy. The jargon is useful, since it is the language in which they are described. I mean Turing machine, filesystem, socket and pipe are also jargon. A good example is LINQ, they use monads and functors. They just gave them other names.

epgui 4y ago

It's not kool-aid, it's applied maths. Just because you don't already know and understand it (and hence don't see the benefit of it) doesn't mean there's no clear and obvious benefit. But you do have to learn before you understand.

salty_biscuits 4y ago
To be fair though, there is a wide spectrum of "usefulness" for pure mathematics concepts in applied mathematics. For less contemporary examples you don't need to know about Lebesgue measure to do practical numerical quadrature for applications. Or you don't need to know that rotation matrices are part of the SO3 group to do computer graphics. Sometimes the abstractions are powerful and sometimes they are kind of a distraction (or even make communication a problem). There typically needs to be a super compelling application to motivate a shift in baseline knowledge.

DalekBaldwin 4y ago

Here are some of the more practical insights for medium/large-scale software design that have stuck with me. They apply regardless of whether I'm working in a language that lets me easily express categorical-ish stuff in the type system: - Triviality The most trivial cases are actually the most important. If I build a little DSL, I give it an explicit "identity" construction in the internal representation, and use it liberally in the implementation, transformation phases, and tests, even though obviously its denotation as a no-op will be optimized away by my little DSL compiler, and it may not even be exposed as an atomic construct in the user-facing representation. - Free constructions When it's difficult to separate a model from an implementation, when simple interfaces are not enough because the model and implementation are substantially complex, multilayered systems on their own, often the answer is to use a free construction. Free constructions are a killer tool for allowing the late-binding of rather complex concerns, while allowing for reasoning, transformation, and testing of the underlying components without worrying about that late-bound behavior. "Late-bound" here does not have to mean OO-style dynamic dispatch -- in fact now you have more expressive power to fuse some behaviors together in a staged manner with no runtime indirection, or to make other behaviors legitimately dynamic, differing from one call to the next. Tradeoffs in the flexibility/performance space are easier to make, to change, and to self-document. This is particularly useful when you need to start addressing "meta" concerns as actual user-facing concerns -- when your project matures from a simple application that does Foo into a suite of tools for manipulating and reasoning about Foo and Fooness. Your Foo engine currently just does Foo, but now you want it to not just do Foo, but return a description of all the sub-Foo tasks it performed -- but only if the configuration has requested those details, because sometimes the user just wants to Foo. So you embed the basic, non-meta-level entities representing the actual component tasks in a free construction, compose them within that free construction, and implement the configurable details of that composition elsewhere. - "Sameness" Making clear distinctions between different notions of sameness is important. Identity, equality, isomorphism, adjointness -- sure, you might never explicitly implement an adjunction, but these are important notions to keep separate, at least conceptually if not concretely in source code entities, as a piece of software grows more complex. If you treat two things as fundamentally the same in more ways than they really are, you reach a point where you now can no longer recover crucial information in a later phase of computation. In an indexed/fibered construction, this X may be basically the same as that X, but this X, viewed as the image of a transformation applied to Y is quite different from that X, viewed as the image of a transformation applied to Z, although the images are equal. So can I just pass my X's around everywhere, or do I need to pass or at least store somewhere the references to Y and Z? What if computationally I can only get an X as the result of applying a function to Y, but conceptually the functional dependency (that is, as a mathematical function) points the other way around, from X to Y? Paying attention to these easy-to-miss distinctions can save you from code-architecting yourself into a corner. You may discover that the true reserve currency of the problem domain is Y when it looks like X, or vice versa.

ukj 4y ago

Category theory is to functional/declarative programming what design patterns are to OO programming. Patterns for decomposing problems and composing solutions. To ask “How is it useful?” Is to ask “How are design patterns useful in OO?”. But you already know the answer… Is there an advantage over just inventing your own vocabulary? Yeah! You don’t have to reinvent 70+ years of Mathematics, or teach your language to other people before you can have a meaningful design discussion.

charcircuit 4y ago
>You don’t have to reinvent 70+ years of Mathematics What do those 70 years of mathematics do for me as a software engineer? >or teach your language to other people before you can have a meaningful design discussion. It's the other way around. Most engineers will have no clue what you are saying.
- ukj 4y ago
  >What do those 70 years of mathematics do for me as a software engineer? You mean other than inventing the entire industry in which you work? It's a weird question that I have no idea how to answer for you. What is 70+ years of computer science doing for you as a software engineer? Are you standing on the shoulder of giants; or are you inventing/re-discovering everything by yourself from first principles? >It's the other way around. Most engineers will have no clue what you are saying. So how do engineers understand each other if we all invent our own meta-language to speak about software design in the abstract? Misscommunication is what happens by default unless you intentionally become part of a community and learn the meta-language. Mathematics is one such community which has existed for millenia and benefits from the network effect. It's an anti-entropy thing. There are many parallels here to the Tower of Babel.
  - charcircuit 4y ago
    >What is 70+ years of computer science doing for you as a software engineer? No, what does category theory unlock from mathematics that I can not get without it.

mrkeen 4y ago

> I always feel these posts are filled with category theory jargon The 80/20 rule really applies here. Most of the time there's only a few key type classes that people use. Pretty much just Monad, Monoid, Applicative, Functor. If you grok those, then what people say makes a lot more sense. > Can anyone give me a practical applied way in which category theory is a benefit to your design Monad is probably the best example, because so many different, important libraries use it. Once you know how to code against one of them, you kinda know how to code against all of them! The following is code written in the STM monad. It handles all the locking and concurrency for me: transfer x from to = do f <- getAccountMoney from when (f < x) abort t <- getAccountMoney to setAccountMoney to (t + x) setAccountMoney from (f - x) This same code could be in the State monad (excluding the line with 'abort' on it). Or it could be in the ST monad. Or the IO monad. Each of those is doing radically different things under the hood, which I don't have the brainpower to understand. But because they expose a monadic interface to me, I already know how to drive them using simple, readable, high-level code. As well as the 4 monads mentioned above, parsers are monadic, same with Maybe and Either, List. The main concurrency library 'async' is also monadic (though it just uses the IO monad rather than defining an Async monad). Often the people writing your mainstream libraries know this stuff too. If you're calling flatMap (or thenCompose), you're calling monadic code. The writers just shirk from calling it monadic because they're worried people will suddenly not understand it if it has a scary name.

shakow 4y ago
Looks like to the hard part is ‶handl[ing] all the locking and concurrency″ with a pretty interface; that it satisfies the definition of a monad is a convenience because the `do` keyword requires it, but so would it be if it satisfied any other one, wouldn't it?
- larve 4y ago
  I would say it's the other way around: 1. Because the underlying concept for handling composing locks (STM, which I don't know much about, but I'm going to assume is a way to wrap operations within a transaction) is sound 2. it is easy to define the corresponding monad 3. which makes it usable in a do notation 4. producing readable and future-proof code The step 2 is almost trivial, 1 is where the thinking is at. The do notation is nice to have, but not that important (to me at least). I have no problem writing this in CPS style when using javascript or c++: const transfer = (x, from, to, onSuccess, onError) => { return getAccountMoney(from, (f) => { if (f < x) { return onError(); } else { return getAccountMoney(to, (t) => { return setAccountMoney(to, t+x, () => { return setAccountMoney(from, f-x, onSuccess, onError); }, onError); }, onError); }, onError); } } The main point is that I can add 80 edge cases to this and it will continue to compose nicely, not a single lock in sight.

gilmi 4y ago

If you have 24 minutes, George Wilson's talk about propagators is really interesting and demonstrates how we can find solutions to problems by looking at math. https://www.youtube.com/watch?v=nY1BCv3xn24 https://www.youtube.com/watch?v=nY1BCv3xn24

franknstein 4y ago

I feel like another application which is maybe not talked about all that much is that knowing category theory gives you power to name some design pattern, google that, and tap into that vast mathematical knowledge that humanity already discovered. This becomes incredibly valuable once you become aware of how much you don't know. Or maybe just write that bare manimum code that works, idc. Oh and also when you recognize your design to be something from ct its probably quality. Shit code cant be described with simple math (simple as in all math is simple, not as in math that is easy to understand).

klodolph 4y ago

I’m a math major. I learned category theory in school. I think of category theory as an easy way to remember things. If some concept can be expressed as category theory, it can often be expressed in a very simple way that’s easy to remember. However, if you try to teach math using category theory from the beginning, it feels a little like trying to teach literature to someone who can’t read yet. Anything directly useful from category theory can be expressed as something more concrete, so you don’t NEED category theory, in that sense. But category theory has the funny ability to generalize results. So you take some theorem you figured out, express it using category theory, and realize that it applies to a ton of different fields that you weren’t even considering. The effort to reward of category theory is not especially high for most people. It did give us some cool things which are slowly filtering into day to day life—algebraic data types and software transactional memory are two developments that owe a lot to category theory.

barbariangrunge 4y ago
Pardon me: what IS category theory?
- klodolph 4y ago
  Almost every field you can study in mathematics can be thought of as a “category”, and when you take a math class in undergrad, it usually focuses on one or two specific categories. Category theory is the study of categories in general. As in, “What if, instead of studying a specific field of math, you studied what these different fields had in common, and the relationships between them.” The part where it gets wacky is when you realize that “categories” is, itself, a category. https://youtu.be/yAi3XWCBkDo https://youtu.be/yAi3XWCBkDo