[HN Gopher] Fold-... and Monoids
___________________________________________________________________
Fold-... and Monoids
Author : ykm
Score : 84 points
Date : 2025-01-06 02:18 UTC (2 days ago)
(HTM) web link (funcall.blogspot.com)
(TXT) w3m dump (funcall.blogspot.com)
| revskill wrote:
| Is it useful in solving leetcode problems ?
| noelwelsh wrote:
| Dynamic programming is often (always?) structured as a monoid,
| and that's the kind of thing that shows up in leetcode.
| sullyj3 wrote:
| Can you elaborate or point to resources?
| noelwelsh wrote:
| 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.
| whateveracct wrote:
| years ago, i solved plenty of HackerRank problems in Haskell
| with code that contained "instance Monoid ... where" :)
| gleenn wrote:
| This was uniquely followable mathy code
| tpoacher wrote:
| 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 wrote:
| A nice property of monoids is associativity, which allows for
| some interesting incremental algorithms, e.g. by using balanced
| trees: If the fold of x on a list is computed in clever way, the
| fold of x 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 x is a commutative group operation (i.e. inverse elements
| exist and axb=bxa), that can even be done in constant time in a
| trivial way.
| quchen wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| 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?
| TuringTest wrote:
| 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.
| ndriscoll wrote:
| 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.
| recursive wrote:
| 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!
| ndriscoll wrote:
| 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
| pizza wrote:
| 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.
| jandrese wrote:
| 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.
| marcosdumay wrote:
| 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.
| ndriscoll wrote:
| 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.
| epolanski wrote:
| 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.
| marcosdumay wrote:
| > 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.
| ndriscoll wrote:
| 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.
| epolanski wrote:
| Scala/Typescript
| lambdas wrote:
| > 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.
| kqr wrote:
| > 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(o, [a, b, ...]) ~= a o (b o ...)
|
| where the right term for each operator is given by the recursive
| call. In contrast, then, foldl must be the iterative variant
| where foldl(o, z, [a, b, ...]) ~= z
| o= a z o= b ... return z
| ahoka wrote:
| It's even easier if you just remember that left and right in
| fold means left associative and right associative application
| of the function.
| recursive wrote:
| In fold-left, the folding happens on the left.
|
| > it's easier to remember that ...
|
| Whoa, we have very different experiences remembering things.
| mrkeen wrote:
| 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 wrote:
| > 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 wrote:
| But in between those two extremes, the curious. I know enough
| to be intrigued but not to critique. Hoping for some insight
| here.
| jerf wrote:
| 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 wrote:
| 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 wrote:
| > 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 wrote:
| > 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 wrote:
| 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
| TeMPOraL wrote:
| That's surprisingly good compared to typical video of this type
| :). Quite accurate too.
| behnamoh wrote:
| I have watched this scene many times, each time for a different
| topic, and yet it never gets old!
| kinow wrote:
| 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/
| agumonkey wrote:
| need to adjust the timespan https://old.reddit.com/r/function
| alprogramming/top/?sort=top...
|
| ps: nice punchline https://imgur.com/a/5g9wxPg
|
| pps: thanks for the sub
| jnhnum1 wrote:
| 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 wrote:
| Semigroup with an identity becomes a monoid right?
| tmoertel wrote:
| 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...
| satvikpendem wrote:
| Yes, that is because folds work on catamorphisms in category
| theory.
| tmoertel wrote:
| Indeed! The first example I linked to explains this
| connection in detail.
___________________________________________________________________
(page generated 2025-01-08 23:01 UTC)