Hacker News Reader

Comment by vertex-four | Hacker News Reader

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?

View on HN

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.

I think, I've always known if my type was a monoid without knowing the word.

It's a simple concept that appears all over in computing. I'm not surprised that that's the case.

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.

OK, so when was the last time knowing something is a monoid helped you solve a problem that you were having difficulty with?

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.

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.

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/

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

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.

Interesting, although I am not sure how Unit and Bottom are related to monoids. Also, how does this translate, say, into C or C++? Unit is easy:

  struct Unit {};

but what about Bottom?

How about:

class Bottom { private: Bottom(){} };

This does not look right. If I understand correctly, the position of Bottom in the hierarchy of types is exactly the opposite to that of Unit: the latter could serve as the "universal base" (like the type Object), whereas the former could be seen as the "universal descendant" (some kind of Null type). In other words, Unit is "anything" and Bottom is "nothing".

See https://en.wikipedia.org/wiki/Top_type

Even Haskell doesn't have a way to declare a value precisely of type Bottom.

As far as the connection with monoids goes, Bottom is a subtype of all types in the same way that the empty element of a monoid is a "zero" of the elements of the monoid. I don't know if that helps, but the similarity is that the types form a lattice, and so do the elements of the monoid. AIUI lattices (in the mathematical sense) have top and bottom elements, and in between they look like a DAG...

This leaves out the possibility that breaking down problems as abstract mathematical structures helps you avoid difficult problems.

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.

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...

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?

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 :-)

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.

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.

I guess the underlying discussion here is about viewing programming as a kind of applied algebra, which is common within functional programming and not so common in other traditions.

I happen to find that view really fascinating and generative, but I don't blame others if they aren't interested.

I also wouldn't insert the monoid concept into a codebase that isn't Haskell or doesn't already have some alignment with algebra, because it would seem weird... and Haskell has features (typeclasses and purity) that make monoids really nice to use.

I also don't generally do language advocacy, and I have a great respect for the diversity of ways of thinking and learning. But I also wish people wouldn't dismiss concepts that other people find useful and good just because they don't immediately see the point.

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

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.

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.

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_...

I don't tend to handle things in the domain you're talking about here - 99% of problems I solve are along the lines of "how do I split the function to solve this problem up in such a way that it obviously matches the spec and each part is difficult to misuse". Think security-centric applications - an identity server implementing OpenID Connect and SCIM, for example.

As a result, I currently use languages with decent type systems - Rust, recently F# - but I've still never come across a reason to know that something is a monoid, and I don't regularly come across duplicated code, so I'm not exactly sure what problem knowing something is a monoid is supposed to solve in my domain.

In my experience, it's more important to know that something isn't a monoid / semilattice / <insert structure here>

The CRDTs linked by the parent are a great example. If you're working on an eventually consistent system, and you see a structure that doesn't form a monoid, it's most likely the case that there's going to be some sort of race condition. That isn't to say that any given monoid is going to solve the problem, but it can definitely help to pinpoint possible problems in otherwise complicated code.

It definitely doesn't come up in every discipline, but studying these structures has improved my engineering a ton. If design patterns are about class and object composition, then I'd argue that algebraic structures are the equivalent for function composition.

Full disclosure: I write mostly functional Erlang code for a living

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

Reply on news.ycombinator.com