Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fold-... and Monoids

funcall.blogspot.com

Post reply on HN
Print view View original

11–20 of 48 posts

Re: Fold-... and Monoids

#11

Post by mrkeen »

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.

Re: Fold-... and Monoids

#12

Post by noelwelsh »

sullyj3 wrote: post #10
noelwelsh wrote: post #3

Earlier quoted context omitted.

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.

Re: Fold-... and Monoids

#13

Post by wesselbindt »

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

Re: Fold-... and Monoids

#14

Post by asplake »

wesselbindt wrote: post #13

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

Re: Fold-... and Monoids

#15

Post by cartoffal »

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

Re: Fold-... and Monoids

#16

Post by lambdas »

quchen wrote: post #7

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 ve…

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

Re: Fold-... and Monoids

#17

Post by mcphage »

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

Re: Fold-... and Monoids

#19

Post by jnhnum1 »

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.

Re: Fold-... and Monoids

#20

Post by TeMPOraL »

TypingOutBugs wrote: post #18

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.
Post reply on HN