Fold-... and Monoids | Hacker News Reader

Fold-... and Monoids

funcall.blogspot.com

103 pointsykm46 comments

Not sure why the article has to mention monads? I mean there’s the (mathematically correct) joke that »monads are monoids in the category of endofunctors«, but understanding that requires getting elbow deep into category theory, and if you’re not one of the maybe 10 people in the world gifted that way has zero practical use when programming.

> A monad is a monoid over a set of curried functions.

Is that so? Sounds very wrong to me. If we want to go the monad joke way, monads have to have an operation (a -> m b) that composes, but those are just normal functions, and there’s nothing curried about it. It’s a statement that one could bend enough so it’s kind of right, but what it really does is raise eyebrows.

> Monads force sequential processing because you set up a pipeline and the earlier stages of the pipeline naturally must run first.

No, a counterexample is the (esoteric) reverse state monad, where values flow the normal way but state comes from the results of future computations.

I found it useful to have them mentioned, since people new to this topic (or, e.g., Haskell) tend to bump onto monoids when they first try to understand monads.

A 'handwavy' association that somewhat makes sense and allows you to have some sort of perspective when moving on to monads is better than simply omitting the link to monads completely, just because one can "kindof maybe" find holes in the simplified explanation provided.

(fair enough, the words "this is somewhat oversimplified, but" could have been added, but personally I didn't care)

> tend to bump onto monoids when they first try to understand monads

That's unfortunate. They should be bumping onto monoids much earlier, and much more often.

Yeah, IO and do notation put monads on the face of people way before they have time to adapt to it. But monoids are the one that are extremely valuable, simple, and easy to learn. Also, they make for a nice step in a progressive adaptation to the "generalized thinking" one need to understand why Haskell does the things it does.

Why? Serious question, but what's the use of monoids? I encountered the term years ago, when I had an ill-fated ambition to make sense of monads. I've let it go and made peace with the world. But outside that narrow context, I've never even heard the term "monoid". What are people using it for in the real world?

As the article explains, fold functions are a simpler way to think about monoids. So in recursive pure functional programming, many important iterative processes (pipelines, accumulators, machine states...) can be expressed as an application of fold-l or fold-r.

Roughly, something is a monoid exactly when a parallel reduce type of algorithm can be used. The associativity lets you break it into sub-problems, and the unit lets you insert padding where necessary to get same-sized blocks for parallel processors. It's also a useful concept to know for library design. e.g. when there's a "combine" or "reduce" operation on some data type, it should occur to you that your users will probably want a neutral "do-nothing" element and that your operation should give you a monoid. APIs without one are usually annoying to work with and require extra if statements/special casing.

More generically, named concepts like this give you a way to compress knowledge, which makes it easier to learn new things in the future. You get comfortable with the idea of a monoid, and when you meet a new one in the future, you immediately have an intuitive ground to build on to understand how your new thing behaves.

Thanks. Parallelization of T[] => T operations makes a lot of sense. Monoids seem to introduce exactly the necessary constraint to allow some kinds of operation re-ordering needed for various perf optimizations like parallelization. I get it!

Taking that one step further, a monoid homomorphism is a function that transforms one monoid into another while preserving that essential structure (homo-morph: same-shape), so that map-then-reduce is the same as reduce-then-map. Being able to swap the two might be a useful optimization if one is more expensive than the other, for example. e.g. `e^(a+b) = e^a*e^b` turns addition into multiplication. Fourier transforms turn convolution (expensive, complicated) into multiplication (cheap, simple), if you know what that is.

In some other contexts, it's useful to talk about transforming your problem while preserving its essential structure. e.g. in engineering a Fourier transform is a common isomorphism (invertible homomorphism) which lets you transform your problem into an easier one in the frequency domain, solve it, and then pull that solution back into the normal domain. But to understand what's going on with preserving structures, you need to first understand what structures are even present in your problems in the first place, and what it means to preserve them.

This stuff isn't strictly necessary to understand to get real work done, but without it, you get lots of engineers that feel like the techniques they learn in e.g. a differential equations class are essentially random magic tricks with no scaffold for them to organize the ideas.

Another useful purpose of these concepts is to have the vocabulary to ask questions: A semigroup is a monoid without a unit. Given a semigroup, can you somehow add a unit to make a monoid without breaking the existing multiplication? A group is a monoid where the multiplication has inverses/division (So if your unit is called 1, then for any x, there's a "1/x" where x/x = 1). Can you take a monoid and somehow add inverses to make it into a group? etc. In a programming context, these are generic questions about how to make better APIs (e.g. see [0]). It also turns out that groups exactly capture the notion of symmetry, so they're useful for things like geometry, physics, and chemistry. If the symmetries of the laws of physics include shifts, rotations, Lorentz boosts, and adding certain terms to the electromagnetic potential, can I somehow understand those things individually, and then somehow understand the "group of the universe" as being made out of those pieces (plus some others) put together? Can we catalogue all of the possible symmetries of molecules (which can tell you something about the the states they can be in and corresponding energy levels), ideally in terms of some comprehensible set of building blocks? etc.

[0] https://izbicki.me/blog/gausian-distributions-are-monoids

It's a type of nice structure. Lists with concat, strings with append, etc. "Friendly chunkability", if you like. For instance, map reduce is a monoid homomorphism - when I see 'monoid homomorphism' in the wild, I think 'parallelizable' etc. It's a handy concept.

Pretty much every time you see people start talking about monoids/monads/endofucntors/etc... they are trying to get their compiler to automatically vectorize their program.

The value of monoids is being a single concept that generalizes the ideas of several different things like arrays/lists/strings, integral numbers, or paralelizable computation.

In the world that I imagine could exist, we'd do away with algebra 2 and pre-calculus in high school, which are a waste of 2 years, and instead do something like algebra -> geometry -> calc1 -> calc2 -> linear algebra -> abstract algebra, with linear algebra being concrete things like adding arrows and solving systems, and abstract algebra introducing basics of monoids, groups, vector spaces, and homomorphisms. It's sort of unfortunate that even the basic ideas of algebraic thinking (i.e. structures and structural transformations) are pretty much not even hinted at to anyone but math majors, and yet we spend years of school on something called "algebra". So even technical people can't see the point of structural modeling.

It's kind of natural that you need to progress from a magma/semi group monoid (algebra) to functors/applicative/monad (category theory)

Would it help if you defined a monoid as a combination of 3 things?

1) a data type A

2) an associative operation on A

3) an identity (or empty element)

Then you can correctly say that the string data type, admits an associative operation (concatenation of two strings) and you have an empty element (the empty string).

I think too many people talking about functional programming really overblow how much you need to understand about mathematics, they serious do.

Think about my definition and you can quickly understand that there are many monoid instances for numbers (with the associative operation being addition to get a monoid or multiplication to get another monoid instance).

There's infinite numbers of monoid instances for various data types.

Haskell has several shortcomings from what I remember and Haskell developers incorrectly assume that you can only have one semi group (or equality, monoid, etc) instances for your data type because they believe they are the closest to math, but in reality their language has its own limitations.

> Haskell developers incorrectly assume that you can only have one semi group (or equality, monoid, etc) instances for your data type

They don't assume that. The devs bent the compiler backwards several times trying to support more than one instance, but they still couldn't design an implementation that is actually good to use.

If you know of any language where this works well, it would be nice to know. AFAIK, representing that kind of thing is an open problem, nobody has an answer.

Scala does it well. Implicits make it easy to pass along the instance you mean. You can put a default on the companion object if you want, but you can override where needed. Implicits on the companion object have lower priority than those in current scope.

Scala/Typescript

I think Idris addresses this fairly well, if there's more than one instance (and the code is ambiguous) you have to annotate which one.

> Is that so? Sounds very wrong to me. If we want to go the monad joke way, monads have to have an operation (a -> m b) that composes, but those are just normal functions, and there’s nothing curried about it. It’s a statement that one could bend enough so it’s kind of right, but what it really does is raise eyebrows.

I can see where they’re coming from, but they certainly haven’t set the stage for it to be a something you could deduce without already knowing what they’re referencing.

So to me, it seems they’re referencing the Free Monad, recursion schemes and a little of HomFunctor/Yoneda Lemma.

The free monad gives a coproduct of functions, where the value is either a recursive call or a value (branch vs node). To get from a set to a free monad, you need to define a Functor over the set, and given most things are representable, this is trivial.

Given this free monad, an algebra can be formed over it by providing a catamorphism, where the binary function would indeed be composition.

> A monad is a monoid over a set of curried functions

I think this statement will have two kinds of readers. People who are not familiar with monads, for whom it'll fly right over their heads, and people who are familiar with monads, who will be annoyed at its inaccuracy.

But in between those two extremes, the curious. I know enough to be intrigued but not to critique. Hoping for some insight here.

If there is any concept in the whole of the programming world that has demonstrated that people can be screwed up by dropping the wrong misconception in at just the right time, it is the monad concept.

It's best to not learn from wrong things, which is, unfortunately, statistically most of the things talking about monads.

I'm pretty sure it will reach a few people that are just at that point where they don't understand a monad, but are ready to and just need an explanation that clicks. And it will completely ruin their understanding of both monads and currying, because it's wrong.

A nice property of monoids is associativity, which allows for some interesting incremental algorithms, e.g. by using balanced trees: If the fold of × on a list is computed in clever way, the fold of × on a list where one element is modified can be computed in logarithmic time, given the computation of the first list.

A good example for a monoid are strings with the string concatenation operation! This is used a lot in text editors. Homomorphisms are also of practical relevance here.

If × is a commutative group operation (i.e. inverse elements exist and a×b=b×a), that can even be done in constant time in a trivial way.

> Although fold-left is commonly used to accumulate results, it is more general than that. We can use fold-left as a driver for a state machine. The second argument to fold-left is the initial state, and the combining function is the state transition function. The list argument provides a single input to the state machine on each state transition.

At that point you've lost associativity: ((state * transition) * transition) is meaningful, but (state * (transition * transition)) isn't well defined. Which means you're no longer talking about monoids.

Another way to look at it—by associativity, fold-left and fold-right should be equal. If they're not, or if one is defined and the other isn't, then you don't have associativity.

> If I haven’t used fold-left or fold-right in a while, I sometimes forget which one computes what.

I'm glad I'm not the only one struggling with this! Though I have started remembering it a different way: I pretend the 'r' in 'foldr' stands for recursive. Thus it's easier to remember that

    foldr(º, [a, b, ...]) ~=
        a º (b º ...)

where the right term for each operator is given by the recursive call. In contrast, then, foldl must be the iterative variant where

    foldl(º, z, [a, b, ...]) ~=
        z º= a
        z º= b
        ...
        return z

It's even easier if you just remember that left and right in fold means left associative and right associative application of the function.

In fold-left, the folding happens on the left.

> it's easier to remember that ...

Whoa, we have very different experiences remembering things.

> Here are some monoids: string-append over strings, addition over integers, state transition over machine states, compose over unary functions.

Correction: function composition is not a monoid over unary functions, only over families of endofunctions (functions of type `a -> a` for some `a`). You can't compose a function of type `a -> b` with a function of type `a -> b` for example, when `a` /= `b`, because one gives back a value of type `b` which cannot be passed into a function expecting a value of type `a`.

Thinking in terms of monoids can be quite helpful even if you're not in pure functions land.

For instance, if you're putting together an on-disk full-text search index, immutability techniques become very relevant (since you can't insert into the middle of files like you can do with in-memory hashmaps). Just make small indexes and a (binary, associative) index-merge operation. Now you have an online&updatable search engine which doesn't need to wait for full reindexes over the data to include new documents.

Anytime I see Monads or Monoids in the title I am obligated to share one of the greatest YouTube videos of all time :)

https://www.youtube.com/watch?v=ADqLBc1vFwI

That's surprisingly good compared to typical video of this type :). Quite accurate too.

I have watched this scene many times, each time for a different topic, and yet it never gets old!

12 years after I created r/functionalprogramming, and the post with this video is still the top submission on reddit https://old.reddit.com/r/functionalprogramming/top/

need to adjust the timespan https://old.reddit.com/r/functionalprogramming/top/?sort=top...

ps: nice punchline https://imgur.com/a/5g9wxPg

pps: thanks for the sub

Lost me when they got the definitions of semigroups and monoids wrong.

Semigroups are not required to have any identity, and the monoidal identity needs to be both a left and right identity.

Semigroup with an identity becomes a monoid right?

What's particularly interesting is that folds are not limited to processing lists. For any recursive data structure, you can create a corresponding fold. What's even more interesting is that you can organize your code to automatically create the corresponding fold from a given recursive data structure!

Here's one example I wrote up using trees as the data structure:

https://github.com/tmoertel/practice/blob/master/EPI/09/soln...

Here's another example, this one in Python: https://github.com/tmoertel/practice/blob/master/dailycoding...

Yes, that is because folds work on catamorphisms in category theory.

Indeed! The first example I linked to explains this connection in detail.

Very nice article, thank you.

One of the clearest, most relatable definitions of what a monoid actually is, why you should care if at all, and how it relates to monads at the end. Great!

Might have been nice to add a footnote on what an "endofunctor" is as well, broadly speaking, given the whole "a monad is a monoid in the category of endofunctors" mantra that one first hears when they try to figure out monads.

This was uniquely followable mathy code

Is it useful in solving leetcode problems ?

Dynamic programming is often (always?) structured as a monoid, and that's the kind of thing that shows up in leetcode.

Can you elaborate or point to resources?

I did a quick search and found this:

https://aclanthology.org/C08-5001.pdf

Also good was section 4 of

https://par.nsf.gov/servlets/purl/10237543

Both work with semirings, which are a structure with two monoids.

I found these papers fairly readable on a quick skim, but I have a background in closely related stuff. They might not be so readable if you're not used to the style of presentation.

years ago, i solved plenty of HackerRank problems in Haskell with code that contained "instance Monoid ... where" :)

Reply on news.ycombinator.com