6 ms·

OK... So exactly why is it useful to me, as someone writing programs in the real world rather than theorising about how computation works, that a list type unde

OK... So exactly why is it useful to me, as someone writing programs in the real world rather than theorising about how computation works, that a list type under concatenation and a money type under summation are monoids? Can I actually write useful code with this knowledge?

bstamour 9y ago
At least in C++, knowing your type forms a monoid with your operation informs you when you are safe to use various parallel algorithms. e.g. `std::accumulate` with an associative operator is safe to run in parallel.
- Koshkin 9y ago
  I think, I've always known if my type was a monoid without knowing the word.
  - bstamour 9y ago
    It's a simple concept that appears all over in computing. I'm not surprised that that's the case.
tw1010 9y ago
Sometimes learning things like this actually changes the way you think. You might not notice it the first month you study these things, but little by little you'll grow comfortable with it and eventually it becomes second nature. Eventually this can help you reason about things in ways you weren't able to before, which is useful for certain especially challenging scenarios.
- vertex-four 9y ago
  OK, so when was the last time knowing something is a monoid helped you solve a problem that you were having difficulty with?
  - tw1010 9y ago
    Not sure about monoids themselves. But learning about monoids was a stepping stone towards mastering parts of pure mathematics, which has definitely contributed to my problem solving abilities. Sometimes you need to just bite your tongue and learn some stuff that short-term feels useless but long-term becomes valuable.
    - vertex-four 9y ago
      Or if people are generally incapable of explaining how something they learned has helped them solve a problem in a domain I work in/close to, perhaps it's not that necessary to learn after all.
      - theoh 9y ago
        Here's an example of a monoidal structure used in the design of an elegant algebra for manipulating graphs (the network-of-nodes kind) https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ Representing graphs is a bit of a problem in Haskell, due to the difficulty of creating/working with cyclical structures, and the previous solutions were not really convincing. So in some ways this might be seen as a problem immutable data purists created for themselves. (Not my opinion) But, either way, the ability to reason about and derive algebraic models for some problem domain is worth pursuing in general. Mathematically structured software is a fast track to robust, reliable, verified solutions to problems. That's propaganda but there's a fair amount of support for it. An idea that comes up in functional programming that has a similar algebraic quality to monoids etc. is the notion of a type which contains only one value (usually called "Unit") and a type which contains no values ("Bottom" or _|_). The latter is described as "uninhabited" and is used, among other things, to usefully describe the type of a function which never returns. https://en.wikipedia.org/wiki/Bottom_type https://en.wikipedia.org/wiki/Bottom_type Unit represents a value which is like a point in a space which contains only one point. It gets used to send signals with no content. For example, in predecessors of Go, there's the pattern of sending on a "channel of unit" as a way to essentially indicate an event to the receiver. Obviously in that use case, a type with any distinguishable values would be superfluous.
- Koshkin 9y ago
  On the other hand, a little knowledge is often worse that no knowledge at all. A lack of experience using abstract concepts - the experience which can only be gained by learning much more of, let's say, abstract algebra, than just the definition of monoid - will inevitably lead to wasting one's time or, worse yet, to the finished product being an over-engineered monstrosity.
jerf 9y ago
If you don't work in a language with a type system sufficiently powerful enough to express monoids, or weak enough to express monoids dynamically, there's not much practical value. But note that while cleanly expressing the monad interface is challenging for a type system, monoid is not so hard, and most things that have interfaces or concepts or traits or something like that can do it. At that point you can write generic code that uses them, and you'd be surprised how much value you can get out of that. You write a lot of code manually doing things to monoids that you could have done once. (It is unfortunate that monoids sound like monad's more complicated brother, when in fact it is exactly the opposite way around. Monoids are so simple that a common reaction once you actually get it is to go "Seriously? That's it?") The other useful thing about monoids is that because of the associativity, they provide a useful, yet easy, way of breaking up a task for multiprocessing. If you can prove that your data type and the operations you desire to use on it are monoidal (and by "prove" I mean the informal sort of things programmers do all the time, not grabbing a proof system and going at it), then you have some really easy options, and it's really easy to write a system that very cleanly breaks up "the strategy of how I'm going to multiprocess this" from "what it is I want to multiprocess". Because of this, it is likely that you're going to continue hearing more about these things over time, rather than less. Monoids are just about the simplest non-trivial example of such things, and the more sophisticated steps up (lattices, CRDTs [1]) are probably also things you're going to hear more about in the future. Personally, I think in a lot of ways we are still have collectively done next to nothing as a community to address the multicore world we live in. Right now we're taking advantage of some things like Go's green threads or "asynchronous" programming to deal with the common case where we have some problem where a single core is adequate to solve it, but we need some complicated scheduling or we have huge numbers of these relatively small problems coming at us at once, but we still have made very little progress in doing complex tasks truly in parallel. It is very likely that those solutions are going to involve coming to understand these mathematical abstractions and why they are important. Monoid is going to be the first of them you'll encounter, because it is, as I said, probably the simplest non-trivial one. But on its own it won't get you all that far in general. [1]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- vertex-four 9y ago
Dolores12 9y ago
monoids are perfectly parallelized. map/reduce are built on top of that.
- vertex-four 9y ago
  Which is great, if you're theorising about why map/reduce work or trying to recreate it from first principles. I don't think many of us are trying to do that.
- imtringued 9y ago
  Parallelising things is the easy part. Making them run faster than the single threaded version is often the harder part because the overhead will eat all your gains if your workload isn't large enough. The easy cases are already covered by things like OpenMP and the difficult problems also usually benefit from being written in a language that allows you to tweak your memory layout and allocation patterns manually. I just wish that higher level languages would give me this freedom without sacrificing productiviy or safety. I'm not even asking for completely unreasonable things. At the bare minimum all I really need are off gc heap allocation (with reasonable safety via reference counting or whatever rust does), value types and a way to launch threads that bypass the garbage collector stop the world pause. It's just a checkbox of features and the latter is not that important because you already can sort of do that by calling into C and launching an OS thread. For some reason though nobody is checking those boxes. I still stick to C++ and C but it gets old to spend hours fixing memory leaks and other possibly security related bugs from other developers. I feel like I'm writing too much semi-offtopic things just because I have no other place to express them.
mbrock 9y ago
If you code Haskell then you'll run into monoids all the time, and if you understand what that word means then you can write more concise and idiomatic code that makes use of the wide range of monoid instances available under the common monoid API. You can then make sure to expose the monoid interface for users of your Haskell libraries and they'll be happier because your values will cleanly fit with the rest of the ecosystem. If you don't code Haskell then it's not like monoids are crucial learning for a successful career. Maybe you could approach them with some curiosity and find something interesting and useful about basic algebraic structures. But probably all these monoid nerds are just puttin' you on...
- vertex-four 9y ago
  No, I don't code Haskell. So is all this about monoids/monads/other-simple-ideas-with-complex-names just people solving problems in their language of choice that have already been solved in other languages, or just don't come up in other languages?
  - jstimpfle 9y ago
    In other languages this kind of problem is typically solved with an explicit accumulator and a for loop. Plus a little crutch in places where higher order functions would really make sense :-)
  - mbrock 9y ago
    First of all, what makes "monoid" a "complex" name? Is your complaint basically about terminological aesthetics? I'd say no to your question. I've linked an article elsewhere in the thread that to me shows pretty clearly that monoid is a useful and generative concept. On a more basic level, I personally really enjoy taking inspiration from math and logic into programming. You mentioned composing programs in a way that is safe and correct; I think the algebraic approach to programming is a really excellent and deeply fascinating way to approach that goal.
    - Koshkin 9y ago
      IMHO, naming things sometimes only makes sense in a specific, wider context. Thus, using a domain-specific jargon to name a simple thing like an associative operation with an identity does not make much sense outside of the domain (in this case, abstract algebra). The extreme example of the same nature is the notion of "magma" that finds some use in algebra. Would you use this word to describe a function with two arguments (that have the same type)? There's nothing to be gained by doing this outside algebra.
tome 9y ago
https://news.ycombinator.com/item?id=15242204 https://news.ycombinator.com/item?id=15242204

bstamour 9y ago

At least in C++, knowing your type forms a monoid with your operation informs you when you are safe to use various parallel algorithms. e.g. `std::accumulate` with an associative operator is safe to run in parallel.

Koshkin 9y ago
I think, I've always known if my type was a monoid without knowing the word.
- bstamour 9y ago
  It's a simple concept that appears all over in computing. I'm not surprised that that's the case.

tw1010 9y ago

Sometimes learning things like this actually changes the way you think. You might not notice it the first month you study these things, but little by little you'll grow comfortable with it and eventually it becomes second nature. Eventually this can help you reason about things in ways you weren't able to before, which is useful for certain especially challenging scenarios.

vertex-four 9y ago
OK, so when was the last time knowing something is a monoid helped you solve a problem that you were having difficulty with?
- tw1010 9y ago
  Not sure about monoids themselves. But learning about monoids was a stepping stone towards mastering parts of pure mathematics, which has definitely contributed to my problem solving abilities. Sometimes you need to just bite your tongue and learn some stuff that short-term feels useless but long-term becomes valuable.
  - vertex-four 9y ago
    Or if people are generally incapable of explaining how something they learned has helped them solve a problem in a domain I work in/close to, perhaps it's not that necessary to learn after all.
    - theoh 9y ago
      Here's an example of a monoidal structure used in the design of an elegant algebra for manipulating graphs (the network-of-nodes kind) https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ Representing graphs is a bit of a problem in Haskell, due to the difficulty of creating/working with cyclical structures, and the previous solutions were not really convincing. So in some ways this might be seen as a problem immutable data purists created for themselves. (Not my opinion) But, either way, the ability to reason about and derive algebraic models for some problem domain is worth pursuing in general. Mathematically structured software is a fast track to robust, reliable, verified solutions to problems. That's propaganda but there's a fair amount of support for it. An idea that comes up in functional programming that has a similar algebraic quality to monoids etc. is the notion of a type which contains only one value (usually called "Unit") and a type which contains no values ("Bottom" or _|_). The latter is described as "uninhabited" and is used, among other things, to usefully describe the type of a function which never returns. https://en.wikipedia.org/wiki/Bottom_type https://en.wikipedia.org/wiki/Bottom_type Unit represents a value which is like a point in a space which contains only one point. It gets used to send signals with no content. For example, in predecessors of Go, there's the pattern of sending on a "channel of unit" as a way to essentially indicate an event to the receiver. Obviously in that use case, a type with any distinguishable values would be superfluous.
Koshkin 9y ago
On the other hand, a little knowledge is often worse that no knowledge at all. A lack of experience using abstract concepts - the experience which can only be gained by learning much more of, let's say, abstract algebra, than just the definition of monoid - will inevitably lead to wasting one's time or, worse yet, to the finished product being an over-engineered monstrosity.

jerf 9y ago

If you don't work in a language with a type system sufficiently powerful enough to express monoids, or weak enough to express monoids dynamically, there's not much practical value. But note that while cleanly expressing the monad interface is challenging for a type system, monoid is not so hard, and most things that have interfaces or concepts or traits or something like that can do it. At that point you can write generic code that uses them, and you'd be surprised how much value you can get out of that. You write a lot of code manually doing things to monoids that you could have done once. (It is unfortunate that monoids sound like monad's more complicated brother, when in fact it is exactly the opposite way around. Monoids are so simple that a common reaction once you actually get it is to go "Seriously? That's it?") The other useful thing about monoids is that because of the associativity, they provide a useful, yet easy, way of breaking up a task for multiprocessing. If you can prove that your data type and the operations you desire to use on it are monoidal (and by "prove" I mean the informal sort of things programmers do all the time, not grabbing a proof system and going at it), then you have some really easy options, and it's really easy to write a system that very cleanly breaks up "the strategy of how I'm going to multiprocess this" from "what it is I want to multiprocess". Because of this, it is likely that you're going to continue hearing more about these things over time, rather than less. Monoids are just about the simplest non-trivial example of such things, and the more sophisticated steps up (lattices, CRDTs [1]) are probably also things you're going to hear more about in the future. Personally, I think in a lot of ways we are still have collectively done next to nothing as a community to address the multicore world we live in. Right now we're taking advantage of some things like Go's green threads or "asynchronous" programming to deal with the common case where we have some problem where a single core is adequate to solve it, but we need some complicated scheduling or we have huge numbers of these relatively small problems coming at us at once, but we still have made very little progress in doing complex tasks truly in parallel. It is very likely that those solutions are going to involve coming to understand these mathematical abstractions and why they are important. Monoid is going to be the first of them you'll encounter, because it is, as I said, probably the simplest non-trivial one. But on its own it won't get you all that far in general. [1]: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...

vertex-four 9y ago

Dolores12 9y ago

monoids are perfectly parallelized. map/reduce are built on top of that.

vertex-four 9y ago
Which is great, if you're theorising about why map/reduce work or trying to recreate it from first principles. I don't think many of us are trying to do that.
imtringued 9y ago
Parallelising things is the easy part. Making them run faster than the single threaded version is often the harder part because the overhead will eat all your gains if your workload isn't large enough. The easy cases are already covered by things like OpenMP and the difficult problems also usually benefit from being written in a language that allows you to tweak your memory layout and allocation patterns manually. I just wish that higher level languages would give me this freedom without sacrificing productiviy or safety. I'm not even asking for completely unreasonable things. At the bare minimum all I really need are off gc heap allocation (with reasonable safety via reference counting or whatever rust does), value types and a way to launch threads that bypass the garbage collector stop the world pause. It's just a checkbox of features and the latter is not that important because you already can sort of do that by calling into C and launching an OS thread. For some reason though nobody is checking those boxes. I still stick to C++ and C but it gets old to spend hours fixing memory leaks and other possibly security related bugs from other developers. I feel like I'm writing too much semi-offtopic things just because I have no other place to express them.

mbrock 9y ago

If you code Haskell then you'll run into monoids all the time, and if you understand what that word means then you can write more concise and idiomatic code that makes use of the wide range of monoid instances available under the common monoid API. You can then make sure to expose the monoid interface for users of your Haskell libraries and they'll be happier because your values will cleanly fit with the rest of the ecosystem. If you don't code Haskell then it's not like monoids are crucial learning for a successful career. Maybe you could approach them with some curiosity and find something interesting and useful about basic algebraic structures. But probably all these monoid nerds are just puttin' you on...

vertex-four 9y ago
No, I don't code Haskell. So is all this about monoids/monads/other-simple-ideas-with-complex-names just people solving problems in their language of choice that have already been solved in other languages, or just don't come up in other languages?
- jstimpfle 9y ago
  In other languages this kind of problem is typically solved with an explicit accumulator and a for loop. Plus a little crutch in places where higher order functions would really make sense :-)
- mbrock 9y ago
  First of all, what makes "monoid" a "complex" name? Is your complaint basically about terminological aesthetics? I'd say no to your question. I've linked an article elsewhere in the thread that to me shows pretty clearly that monoid is a useful and generative concept. On a more basic level, I personally really enjoy taking inspiration from math and logic into programming. You mentioned composing programs in a way that is safe and correct; I think the algebraic approach to programming is a really excellent and deeply fascinating way to approach that goal.
  - Koshkin 9y ago
    IMHO, naming things sometimes only makes sense in a specific, wider context. Thus, using a domain-specific jargon to name a simple thing like an associative operation with an identity does not make much sense outside of the domain (in this case, abstract algebra). The extreme example of the same nature is the notion of "magma" that finds some use in algebra. Would you use this word to describe a function with two arguments (that have the same type)? There's nothing to be gained by doing this outside algebra.

tome 9y ago

https://news.ycombinator.com/item?id=15242204 https://news.ycombinator.com/item?id=15242204