Fold-... and Monoids

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.

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

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.

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

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

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

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

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.

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

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.

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

This was uniquely followable mathy code