6 ms·

Fold-... and Monoids

103 points by ykm 2y ago

revskill 2y ago
Is it useful in solving leetcode problems ?
- noelwelsh 2y ago
  Dynamic programming is often (always?) structured as a monoid, and that's the kind of thing that shows up in leetcode.
  - sullyj3 2y ago
    Can you elaborate or point to resources?
    - noelwelsh 2y ago
      I did a quick search and found this: https://aclanthology.org/C08-5001.pdf https://aclanthology.org/C08-5001.pdf Also good was section 4 of https://par.nsf.gov/servlets/purl/10237543 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.
- whateveracct 2y ago
  years ago, i solved plenty of HackerRank problems in Haskell with code that contained "instance Monoid ... where" :)
gleenn 2y ago
This was uniquely followable mathy code
tpoacher 2y ago
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.
Gehinnn 2y ago
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.
quchen 2y ago
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.
- tpoacher 2y ago
  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)
  - marcosdumay 2y ago
    > 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.
    - recursive 2y ago
kqr 2y ago
> 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
- recursive 2y ago
  In fold-left, the folding happens on the left. > it's easier to remember that ... Whoa, we have very different experiences remembering things.
- ahoka 2y ago
  It's even easier if you just remember that left and right in fold means left associative and right associative application of the function.
mrkeen 2y ago
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.
wesselbindt 2y ago
> 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.
- asplake 2y ago
  But in between those two extremes, the curious. I know enough to be intrigued but not to critique. Hoping for some insight here.
  - jerf 2y ago
    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.
- marcosdumay 2y ago
  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.
cartoffal 2y ago
> 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`.
mcphage 2y ago
> 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.
TypingOutBugs 2y ago
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 https://www.youtube.com/watch?v=ADqLBc1vFwI
- TeMPOraL 2y ago
  That's surprisingly good compared to typical video of this type :). Quite accurate too.
- behnamoh 2y ago
  I have watched this scene many times, each time for a different topic, and yet it never gets old!
- kinow 2y ago
  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/ https://old.reddit.com/r/functionalprogramming/top/
  - agumonkey 2y ago
    need to adjust the timespan https://old.reddit.com/r/functionalprogramming/top/?sort=top&t=all https://old.reddit.com/r/functionalprogramming/top/?sort=top... ps: nice punchline https://imgur.com/a/5g9wxPg https://imgur.com/a/5g9wxPg pps: thanks for the sub
- deleted 2y ago
  [deleted]
jnhnum1 2y ago
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.
- TypingOutBugs 2y ago
  Semigroup with an identity becomes a monoid right?
tmoertel 2y ago
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_09_002_find_unbalanced_node.lhs 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/dailycodingproblem_com/count_unival_subtrees.py https://github.com/tmoertel/practice/blob/master/dailycoding...
- satvikpendem 2y ago
  Yes, that is because folds work on catamorphisms in category theory.
  - tmoertel 2y ago
    Indeed! The first example I linked to explains this connection in detail.

103 points by ykm 2y ago

revskill 2y ago

Is it useful in solving leetcode problems ?

noelwelsh 2y ago
Dynamic programming is often (always?) structured as a monoid, and that's the kind of thing that shows up in leetcode.
- sullyj3 2y ago
  Can you elaborate or point to resources?
  - noelwelsh 2y ago
    I did a quick search and found this: https://aclanthology.org/C08-5001.pdf https://aclanthology.org/C08-5001.pdf Also good was section 4 of https://par.nsf.gov/servlets/purl/10237543 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.
whateveracct 2y ago
years ago, i solved plenty of HackerRank problems in Haskell with code that contained "instance Monoid ... where" :)

gleenn 2y ago

This was uniquely followable mathy code

tpoacher 2y ago

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.

Gehinnn 2y ago

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.

quchen 2y ago

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.

tpoacher 2y ago
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)
- marcosdumay 2y ago
  > 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.
  - recursive 2y ago

kqr 2y ago

> 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

recursive 2y ago
In fold-left, the folding happens on the left. > it's easier to remember that ... Whoa, we have very different experiences remembering things.
ahoka 2y ago
It's even easier if you just remember that left and right in fold means left associative and right associative application of the function.

mrkeen 2y ago

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.

wesselbindt 2y ago

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

asplake 2y ago
But in between those two extremes, the curious. I know enough to be intrigued but not to critique. Hoping for some insight here.
- jerf 2y ago
  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.
marcosdumay 2y ago
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.

cartoffal 2y ago

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

mcphage 2y ago

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

TypingOutBugs 2y ago

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 https://www.youtube.com/watch?v=ADqLBc1vFwI

TeMPOraL 2y ago
That's surprisingly good compared to typical video of this type :). Quite accurate too.
behnamoh 2y ago
I have watched this scene many times, each time for a different topic, and yet it never gets old!
kinow 2y ago
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/ https://old.reddit.com/r/functionalprogramming/top/
- agumonkey 2y ago
  need to adjust the timespan https://old.reddit.com/r/functionalprogramming/top/?sort=top&t=all https://old.reddit.com/r/functionalprogramming/top/?sort=top... ps: nice punchline https://imgur.com/a/5g9wxPg https://imgur.com/a/5g9wxPg pps: thanks for the sub
deleted 2y ago
[deleted]

jnhnum1 2y ago

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.

TypingOutBugs 2y ago
Semigroup with an identity becomes a monoid right?

tmoertel 2y ago

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_09_002_find_unbalanced_node.lhs 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/dailycodingproblem_com/count_unival_subtrees.py https://github.com/tmoertel/practice/blob/master/dailycoding...

satvikpendem 2y ago
Yes, that is because folds work on catamorphisms in category theory.
- tmoertel 2y ago
  Indeed! The first example I linked to explains this connection in detail.