5 ms·

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 [

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.
  - larve 4y ago
    This is useful for example when implementing compiler optimizations, or concrete string implementations. It means that you can reduce "foo" + "bar" + foo to at least "foobar" + foo and that you can intern "foobar". Would that work the same without calling it a monoid? Of course, monoid is just a name. But that name allows you to go shopping in a wide variety of other fields and work other people have done and mine it for ideas or even concrete implementations.
    - musk_micropenis 4y ago
      A vast, overwhelming majority of programmers will never implement a concrete string type or compiler optimizations. Can you show me how this kind of theory is practical for a working programmer who does things like batch processing jobs, web applications, embedded software, event-driven distributed systems, etc?
      - lmm 4y ago
        I once wrote a unifying parent class for several client-specific reports we had. Think the parent class implementing the top-level control flow/logic and the child implementations having methods that it calls into, sometimes once (e.g. for the header) and sometimes per-row. Specific reports needed various kinds of customization. Some needed to call the client's web API to get some extra data for each row (and since this was across the internet, it needed to be async). Some needed to accumulate statistics on each row and sum them over the whole report at the end. One needed to query an ancillary database for each row, but all those queries had to be part of the same transaction so that they would be consistent. Now in theory you can do ad-hoc things for each of those cases. You could make the per-row method always async (i.e. return Future), so that you can override it to do a web API call sometimes. You could stash the statistics in a mutable variable in the report that accumulates them, remembering to do locking. You could use a session on the ancillary database bound to a threadlocal to do the transaction management (most database libraries assume that's how you're doing things anyway), and as long as your returned Futures are never actually async then it would probably work. But realistically it would be very hard to do safely, and I'd never have spotted the underlying symmetry that let me pull out the high-level logic. More likely we'd've stuck with three distinct copy-pasted versions of the report code, with all the maintenance burden that implies. In principle an abstraction never tells you something you didn't already know - whatever properties you're using, you could've always worked them out "by hand" for that specific case. Like, imagine programming without the concept of a "collection" or any idea of the things you can do on a collection generically (such as traverse it) - instead you just figure out that it's possible to traverse a linked list or a red-black tree or an array, so you write the code that works on all of them when you need it. That's absolutely a way that you can program. But if you don't have this vocabulary of concepts and patterns then realistically you miss so many chances to unify and simplify your code. And if you have the rigorous category-theory concepts, rather than fuzzier design patterns, then you have quick, objective rules for figuring out when your patterns apply - and, even more importantly, when they don't. You can use library code for handling those concepts with confidence, instead of e.g. wondering whether it's ok for your custom iterator to expect the library to always call hasNext() before it calls next(). It's a huge multiplier in practice.
      - larve 4y ago
hosh 4y ago
For most of my years in primary education, math was easy. Until it was not. I ran headlong into the idea of "instantaneous rate of change", and I was confronted with the existential crises that there is nothing inherently concrete or "real" about the idea of instantaneous rate of change. My mind just got stuck on there, and I nearly failed the course in high school. Everything after that point was not easy, and somewhere, there was a belief forming that maybe I was not so good at math. Two things I encountered changed my perspective on that. The first was reading a math graduate student's experience where they talk about struggling with concepts, like groping about in a dark room until one day, you find the light switch and you see it all come together. The other is Kalid Azad's "Math, Better Explained" series. His approach is to introduce the intuition first, before going into the rigor. Between those two, I realized that I had never really learned how to learn math. Once I started with the intuition, I also realized why people get stuck on things. There are people who don't get negative numbers. They keep looking for something concrete, as if there were something intrinsic to reality that makes negative numbers "real". And there isn't. And yet, in my day-to-day life, I work with negative numbers. I am far better able to reason and navigate the modern world because I grok the intuition of negative numbers. Then there are the cultures where there isn't even a notion of natural numbers. Their counting system is, "one", "two", and "many". In their day to day life, to echo your sentiment, they can go on their whole life without the "insight" that things can be countable. Many of them probably won't even care that they don't have the intuition of countable things. And yet, in this modern culture, I find myself introducing the idea to my toddler. Ultimately, it's up to each individual's decision how far they want to go with this. Each culture and civilization has a norm of a minimum set of intuitions in order for that person to navigate that civilization. Category Theory is outside that norm, even among the software engineer subculture. Perhaps one day, it will be the norm, but not today. Beyond that, no one can make you grok a mathematical intuition, as useful as they are once grokked.
- mettamage 4y ago
  I am not great at math. But I learned about complex numbers for fun. It took a bit to make them “real” for me, 3B1B helped a lot as did asking myself how I find negative numbers real (negative integer: if something in the future will exist, it won’t and the negative integer will be incremented, aka a debt to the future existence of whatever the number represents). Complex numbers: the number line is just a metaphor. What would happen if you make it 2D? Oh you can solve negative roots. Whenever a number needs to spin or have a negative root, it’s a useful tool. Numbers are tools. Cool, that’s “real” enough for me. I know I will never ever use it. Or at least, not in my current state of how I live my life. I liked learning it, there’s something to be said for what is beyond your horizon. But I do think just like complex numbers, category theory needs a motivation that is compelling. In retrospect, learning complex numbers is most likely not useful for me. Oh wait a second, complex numbers helped me to understand trig. I never understood it in high school but 3B1B made it intuitive with complex numbers Nevermind, I’ll just let this all stand here. It’s fun to be open and convinced by myself to the other side while writing my comment :’) I’m sure if I would have learned category theory, I would have written a similar comment as I think there are a lot of parallels there.
jiggawatts 4y ago
I can think of hundreds of “exceptions” to the category theoretic approach. So for example anything you can do to “string” type that isn’t based on human language you should be able to do to an array of bytes, integers, or “well-behaved” objects. (Also “escaped” strings or strings in various encodings such as UTF-16 or MBCS.) Show me a language that implements all of those functions with interchangeable and uniform syntax! What does it even mean when I say “well behaved”? It means that those objects need to have some traits in common with characters, such as: copyable, comparable, etc… To implement regex for objects would also require a “range” trait and perhaps others. Category Theory lets us talk about these traits with a formal language with mathematically proven strict rules. With C++ template meta programming it’s possible to get most of the above, but not all, and it’s not used that way in most code. It’s also weakly typed in a sense that C++ can’t express the required trait bounds properly. Rust and Haskell try as well but still fall short. Category Theory shows us what we should aspire to. Unfortunately the tooling hasn’t matured enough yet, but now that GATs have made it into Rust I’m hopeful there will be some progress!
bo1024 4y ago
For example, your language can implement sum(Array<X>) for any monoid X. And the sum of an empty list of integers can automatically return 0, while the sum of an empty list of strings can automatically return "". This sounds simple, but many programming languages make you learn special commands and notation for strings. A compiler could also leverage the fact that length() is a homomorphism, so length(a + b) = length(a) + length(b). Monoids are really simple, so you probably won't get a lot more examples there. But monads are a different story. Once you know the pattern, you really miss them. For example, Promises in Javascript are like painful versions of monads. There is a lot of special-case language support and reasoning around Promises that only apply to Promises. In a language with native support for monads, you could use the same code or libraries to handle patterns arising when using promises, as patterns arising with other monads like I/O. In summary, if you never try it, you may never know or care what you're missing, but that doesn't mean you're not missing anything...
- larve 4y ago
  I find I get a lot of value out of monads even if the language doesn't expose them. For example, it allows me to quickly draw a single arrow in a big architecture diagram because I know I'll be able to take a list of promises and turn it into a promise of a list, and then take a function that takes a list and returns more lists, and flatmap it on top of that. Even if Promise is "not really" a monad, and I will probably have to write the machinery manually. It's what I mean when I say "you can bulldoze your way through a lot of broken abstractions when programming", but at the conceptual stage and when designing, you can get a lot of mileage out of the theoretical constructs.
valenterry 4y ago
That's correct. But understanding that string concatenation forms a monoid is quite nice, because it means that libraries can offer you this as an interface and you can choose the type you want to use. Sorry for the wall of text, but I think to maybe help you understand why people (like me) like to work with it a bit more explicitly, I'll have to make it more concrete and give lots of examples. The good stuff comes at the end. So let's say you have a list or array type. You want to aggregate all the things inside. Let me write pseudo code from here let balances = List(1, 4, 23, 7) let overallBalance = ??? How do you calculate that? Well it's simple - use a for-loop or call .reduce on it or maybe your language even has a builtin sum() function that works for lists of numbers right? let overallBalance = sum(balances) Now what happens if you want to concatenate strings instead? Can you reuse sum()? Probably not - you will have to hope that your language / std lib has another function for that. Or you have to fall back to implementing it yourself. Not so if monoids are explicitly supported. Because then, it will be exactly(!) the same function (which has been implemented only once) - no type-overloading or anything. let overallBalance = combineAll(balances) let concattenated = combineAll(listOfStrings) Okay, seems a little bit helpful but also doesn't seem super readable, so I guess that's maybe not very convincing. But the reason why I personally love to work with monoids as an explicit concept is the thing that comes next. Let's say you got bitten because you used plain numbers (or even proper money-types) for the balances but in the code at some point you mixed up two things and you added a balance to the users age (or something like that) because you used the wrong variable by accident. You decide to make Balance an explicit type class Balance( private innerValue of type number/money ) So the code changes let balances = List(Balance(1), Balance(4), Balance(23), Balance(7)) let overallBalance = sum(balances) But the second line stops compiling. The std lib sum function doesn't support your custom balance class for obvious reasons. You will have to unwrap the inner values and then wrap them again (both for the sum() method or in your handwritten for-loop). In case you use a duck-typed language where you can just "delegate" the plus-operation to the inner value: congratulations, you are already using monoids without calling it like that. Unfortunately, there is no protection against problems, such as that + might mean different things on different types and they can be used with sum() but cause unexpected results (read: bugs). In case you use a language that has good supports for monoids, you essentially have to add just one line: a monoid exists for class Balance using Balance.innerValue That's it. You can now do let balances = List(Balance(1), Balance(4), Balance(23), Balance(7)) let overallBalance = combineAll(balances) And, magically, "overallBalance" will be of type Balance and be the aggregated balance. In case you think that it can't work as easy as that, I'm happy to show you some runnable code in a concrete language that does exactly that. :) On top of that, it does not end here. Let's take it a step further. Let's say don't only have the account-balances of a single person (that would be the example above). You have that for multiple people. So essentially, you've got let listOfBalances = List( List(Balance(1), Balance(4)), List(Balance(23), Balance(7)), List(), List(Balance(42) ) And you want to calculate the overall combined balance. Now it gets interesting. Even in a duck-typed language, you can't use sum() anymore, because the inner lists don't support that. You will have to to fall back to a manual two step process, such as sum(listOfBalances.map(balances => sum(balances))) But with monoids it's different. Since we know how to combine balances in a monoidic way, we also automatically know how to do that for a list that contains balances. In fact, we can do so for any list that contains something that we know of how to combine it. That means, without any other code changes required, you can simply do let overallBalance = combineAll(combineAll(listOfBalances)) This is recursive and goes as far as you want. And it does not only work with lists, but also Maps and other structures. Imagine you have a map with keys that are strings and values that are of any type but constrained to be a monoid. E.g. Map("user1" -> Balance(3), "user2" -> Balance(5)). Or Map("user1" -> List(Balance(2), Balance(3), "user2" -> List(Balance(5))). Or even maps of maps. Now if we have two of those and we know that the values are monoids, we can combine them as well, using again the same function, no matter what is inside. E.g.: let map1 = Map("user1" -> Balance(3), "user2" -> Balance(4)) let map2 = Map("user2" -> Balance(5), "user3" -> Balance(6)) let aggregated = combine(map1, map2) And the result will be Map("user1" -> Balance(3), "user2" -> Balance(9), "user3" -> Balance(6)) This is such a powerful concept and makes a lot of things so convenient that I'm always crying when I work in a language that does not support it and I have to handroll all of my aggregations. One note at the end: all of this can be absolutely typesafe in the sense that if you try to call combine/combineAll on something that isn't combinable (= is not a monoid) it will fail to compile and tell you so. This is not theory, I use this every day at work.

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.
- larve 4y ago
  This is useful for example when implementing compiler optimizations, or concrete string implementations. It means that you can reduce "foo" + "bar" + foo to at least "foobar" + foo and that you can intern "foobar". Would that work the same without calling it a monoid? Of course, monoid is just a name. But that name allows you to go shopping in a wide variety of other fields and work other people have done and mine it for ideas or even concrete implementations.
  - musk_micropenis 4y ago
    A vast, overwhelming majority of programmers will never implement a concrete string type or compiler optimizations. Can you show me how this kind of theory is practical for a working programmer who does things like batch processing jobs, web applications, embedded software, event-driven distributed systems, etc?
    - lmm 4y ago
      I once wrote a unifying parent class for several client-specific reports we had. Think the parent class implementing the top-level control flow/logic and the child implementations having methods that it calls into, sometimes once (e.g. for the header) and sometimes per-row. Specific reports needed various kinds of customization. Some needed to call the client's web API to get some extra data for each row (and since this was across the internet, it needed to be async). Some needed to accumulate statistics on each row and sum them over the whole report at the end. One needed to query an ancillary database for each row, but all those queries had to be part of the same transaction so that they would be consistent. Now in theory you can do ad-hoc things for each of those cases. You could make the per-row method always async (i.e. return Future), so that you can override it to do a web API call sometimes. You could stash the statistics in a mutable variable in the report that accumulates them, remembering to do locking. You could use a session on the ancillary database bound to a threadlocal to do the transaction management (most database libraries assume that's how you're doing things anyway), and as long as your returned Futures are never actually async then it would probably work. But realistically it would be very hard to do safely, and I'd never have spotted the underlying symmetry that let me pull out the high-level logic. More likely we'd've stuck with three distinct copy-pasted versions of the report code, with all the maintenance burden that implies. In principle an abstraction never tells you something you didn't already know - whatever properties you're using, you could've always worked them out "by hand" for that specific case. Like, imagine programming without the concept of a "collection" or any idea of the things you can do on a collection generically (such as traverse it) - instead you just figure out that it's possible to traverse a linked list or a red-black tree or an array, so you write the code that works on all of them when you need it. That's absolutely a way that you can program. But if you don't have this vocabulary of concepts and patterns then realistically you miss so many chances to unify and simplify your code. And if you have the rigorous category-theory concepts, rather than fuzzier design patterns, then you have quick, objective rules for figuring out when your patterns apply - and, even more importantly, when they don't. You can use library code for handling those concepts with confidence, instead of e.g. wondering whether it's ok for your custom iterator to expect the library to always call hasNext() before it calls next(). It's a huge multiplier in practice.
    - larve 4y ago

hosh 4y ago

For most of my years in primary education, math was easy. Until it was not. I ran headlong into the idea of "instantaneous rate of change", and I was confronted with the existential crises that there is nothing inherently concrete or "real" about the idea of instantaneous rate of change. My mind just got stuck on there, and I nearly failed the course in high school. Everything after that point was not easy, and somewhere, there was a belief forming that maybe I was not so good at math. Two things I encountered changed my perspective on that. The first was reading a math graduate student's experience where they talk about struggling with concepts, like groping about in a dark room until one day, you find the light switch and you see it all come together. The other is Kalid Azad's "Math, Better Explained" series. His approach is to introduce the intuition first, before going into the rigor. Between those two, I realized that I had never really learned how to learn math. Once I started with the intuition, I also realized why people get stuck on things. There are people who don't get negative numbers. They keep looking for something concrete, as if there were something intrinsic to reality that makes negative numbers "real". And there isn't. And yet, in my day-to-day life, I work with negative numbers. I am far better able to reason and navigate the modern world because I grok the intuition of negative numbers. Then there are the cultures where there isn't even a notion of natural numbers. Their counting system is, "one", "two", and "many". In their day to day life, to echo your sentiment, they can go on their whole life without the "insight" that things can be countable. Many of them probably won't even care that they don't have the intuition of countable things. And yet, in this modern culture, I find myself introducing the idea to my toddler. Ultimately, it's up to each individual's decision how far they want to go with this. Each culture and civilization has a norm of a minimum set of intuitions in order for that person to navigate that civilization. Category Theory is outside that norm, even among the software engineer subculture. Perhaps one day, it will be the norm, but not today. Beyond that, no one can make you grok a mathematical intuition, as useful as they are once grokked.

mettamage 4y ago
I am not great at math. But I learned about complex numbers for fun. It took a bit to make them “real” for me, 3B1B helped a lot as did asking myself how I find negative numbers real (negative integer: if something in the future will exist, it won’t and the negative integer will be incremented, aka a debt to the future existence of whatever the number represents). Complex numbers: the number line is just a metaphor. What would happen if you make it 2D? Oh you can solve negative roots. Whenever a number needs to spin or have a negative root, it’s a useful tool. Numbers are tools. Cool, that’s “real” enough for me. I know I will never ever use it. Or at least, not in my current state of how I live my life. I liked learning it, there’s something to be said for what is beyond your horizon. But I do think just like complex numbers, category theory needs a motivation that is compelling. In retrospect, learning complex numbers is most likely not useful for me. Oh wait a second, complex numbers helped me to understand trig. I never understood it in high school but 3B1B made it intuitive with complex numbers Nevermind, I’ll just let this all stand here. It’s fun to be open and convinced by myself to the other side while writing my comment :’) I’m sure if I would have learned category theory, I would have written a similar comment as I think there are a lot of parallels there.

jiggawatts 4y ago

I can think of hundreds of “exceptions” to the category theoretic approach. So for example anything you can do to “string” type that isn’t based on human language you should be able to do to an array of bytes, integers, or “well-behaved” objects. (Also “escaped” strings or strings in various encodings such as UTF-16 or MBCS.) Show me a language that implements all of those functions with interchangeable and uniform syntax! What does it even mean when I say “well behaved”? It means that those objects need to have some traits in common with characters, such as: copyable, comparable, etc… To implement regex for objects would also require a “range” trait and perhaps others. Category Theory lets us talk about these traits with a formal language with mathematically proven strict rules. With C++ template meta programming it’s possible to get most of the above, but not all, and it’s not used that way in most code. It’s also weakly typed in a sense that C++ can’t express the required trait bounds properly. Rust and Haskell try as well but still fall short. Category Theory shows us what we should aspire to. Unfortunately the tooling hasn’t matured enough yet, but now that GATs have made it into Rust I’m hopeful there will be some progress!

bo1024 4y ago

For example, your language can implement sum(Array<X>) for any monoid X. And the sum of an empty list of integers can automatically return 0, while the sum of an empty list of strings can automatically return "". This sounds simple, but many programming languages make you learn special commands and notation for strings. A compiler could also leverage the fact that length() is a homomorphism, so length(a + b) = length(a) + length(b). Monoids are really simple, so you probably won't get a lot more examples there. But monads are a different story. Once you know the pattern, you really miss them. For example, Promises in Javascript are like painful versions of monads. There is a lot of special-case language support and reasoning around Promises that only apply to Promises. In a language with native support for monads, you could use the same code or libraries to handle patterns arising when using promises, as patterns arising with other monads like I/O. In summary, if you never try it, you may never know or care what you're missing, but that doesn't mean you're not missing anything...

larve 4y ago
I find I get a lot of value out of monads even if the language doesn't expose them. For example, it allows me to quickly draw a single arrow in a big architecture diagram because I know I'll be able to take a list of promises and turn it into a promise of a list, and then take a function that takes a list and returns more lists, and flatmap it on top of that. Even if Promise is "not really" a monad, and I will probably have to write the machinery manually. It's what I mean when I say "you can bulldoze your way through a lot of broken abstractions when programming", but at the conceptual stage and when designing, you can get a lot of mileage out of the theoretical constructs.

valenterry 4y ago

That's correct. But understanding that string concatenation forms a monoid is quite nice, because it means that libraries can offer you this as an interface and you can choose the type you want to use. Sorry for the wall of text, but I think to maybe help you understand why people (like me) like to work with it a bit more explicitly, I'll have to make it more concrete and give lots of examples. The good stuff comes at the end. So let's say you have a list or array type. You want to aggregate all the things inside. Let me write pseudo code from here let balances = List(1, 4, 23, 7) let overallBalance = ??? How do you calculate that? Well it's simple - use a for-loop or call .reduce on it or maybe your language even has a builtin sum() function that works for lists of numbers right? let overallBalance = sum(balances) Now what happens if you want to concatenate strings instead? Can you reuse sum()? Probably not - you will have to hope that your language / std lib has another function for that. Or you have to fall back to implementing it yourself. Not so if monoids are explicitly supported. Because then, it will be exactly(!) the same function (which has been implemented only once) - no type-overloading or anything. let overallBalance = combineAll(balances) let concattenated = combineAll(listOfStrings) Okay, seems a little bit helpful but also doesn't seem super readable, so I guess that's maybe not very convincing. But the reason why I personally love to work with monoids as an explicit concept is the thing that comes next. Let's say you got bitten because you used plain numbers (or even proper money-types) for the balances but in the code at some point you mixed up two things and you added a balance to the users age (or something like that) because you used the wrong variable by accident. You decide to make Balance an explicit type class Balance( private innerValue of type number/money ) So the code changes let balances = List(Balance(1), Balance(4), Balance(23), Balance(7)) let overallBalance = sum(balances) But the second line stops compiling. The std lib sum function doesn't support your custom balance class for obvious reasons. You will have to unwrap the inner values and then wrap them again (both for the sum() method or in your handwritten for-loop). In case you use a duck-typed language where you can just "delegate" the plus-operation to the inner value: congratulations, you are already using monoids without calling it like that. Unfortunately, there is no protection against problems, such as that + might mean different things on different types and they can be used with sum() but cause unexpected results (read: bugs). In case you use a language that has good supports for monoids, you essentially have to add just one line: a monoid exists for class Balance using Balance.innerValue That's it. You can now do let balances = List(Balance(1), Balance(4), Balance(23), Balance(7)) let overallBalance = combineAll(balances) And, magically, "overallBalance" will be of type Balance and be the aggregated balance. In case you think that it can't work as easy as that, I'm happy to show you some runnable code in a concrete language that does exactly that. :) On top of that, it does not end here. Let's take it a step further. Let's say don't only have the account-balances of a single person (that would be the example above). You have that for multiple people. So essentially, you've got let listOfBalances = List( List(Balance(1), Balance(4)), List(Balance(23), Balance(7)), List(), List(Balance(42) ) And you want to calculate the overall combined balance. Now it gets interesting. Even in a duck-typed language, you can't use sum() anymore, because the inner lists don't support that. You will have to to fall back to a manual two step process, such as sum(listOfBalances.map(balances => sum(balances))) But with monoids it's different. Since we know how to combine balances in a monoidic way, we also automatically know how to do that for a list that contains balances. In fact, we can do so for any list that contains something that we know of how to combine it. That means, without any other code changes required, you can simply do let overallBalance = combineAll(combineAll(listOfBalances)) This is recursive and goes as far as you want. And it does not only work with lists, but also Maps and other structures. Imagine you have a map with keys that are strings and values that are of any type but constrained to be a monoid. E.g. Map("user1" -> Balance(3), "user2" -> Balance(5)). Or Map("user1" -> List(Balance(2), Balance(3), "user2" -> List(Balance(5))). Or even maps of maps. Now if we have two of those and we know that the values are monoids, we can combine them as well, using again the same function, no matter what is inside. E.g.: let map1 = Map("user1" -> Balance(3), "user2" -> Balance(4)) let map2 = Map("user2" -> Balance(5), "user3" -> Balance(6)) let aggregated = combine(map1, map2) And the result will be Map("user1" -> Balance(3), "user2" -> Balance(9), "user3" -> Balance(6)) This is such a powerful concept and makes a lot of things so convenient that I'm always crying when I work in a language that does not support it and I have to handroll all of my aggregations. One note at the end: all of this can be absolutely typesafe in the sense that if you try to call combine/combineAll on something that isn't combinable (= is not a monoid) it will fail to compile and tell you so. This is not theory, I use this every day at work.