Fold-... and Monoids
funcall.blogspot.com
Fold-... and Monoids
1–10 of 48 posts
Re: Fold-... and Monoids
#2Is it useful in solving leetcode problems ?
Re: Fold-... and Monoids
#3Is 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.
Re: Fold-... and Monoids
#4This was uniquely followable mathy code
Re: Fold-... and Monoids
#5Very 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.
Re: Fold-... and Monoids
#6A 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.
Re: Fold-... and Monoids
#7Not 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.
Re: Fold-... and Monoids
#8Not 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 ve…
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)
Re: Fold-... and Monoids
#9> 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