Monoid-Augmented Fifos, Deamortised

Posted5 months agoActive5 months ago

todsacerdoti

34 points

14 comments

pvk.caTechstory

calmpositive

Debate

20/100

Data StructuresAlgorithmsAbstract Algebra

Key topics

Data Structures

Algorithms

Abstract Algebra

Discussion about monoid-augmented FIFOs and their applications in data processing and latency reduction.

Snapshot generated from the HN discussion

Discussion Activity

Moderate engagement

First comment

Peak period

0-6h

Avg / period

3.5

Comment distribution14 data points

Loading chart...

Based on 14 loaded comments

Key moments

01Story posted
Aug 19, 2025 at 11:35 PM EDT
5 months ago
Step 01
02First comment
Aug 20, 2025 at 1:09 AM EDT
2h after posting
Step 02
03Peak activity
8 comments in 0-6h
Hottest window of the conversation
Step 03
04Latest activity
Aug 24, 2025 at 1:43 AM EDT
5 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (14 comments)

Showing 14 comments

seanhunter

5 months ago

3 replies

For people who haven’t done abstract algebra, don’t be put off by the word “monoid”. A monoid in algebra is just a set with some associative binary operation and an identity element. Mathematicians in the 19th and 20th centuries realised you can study these types of structures and prove things which are true for all of them rather than having to do each one separately, and that led to “abstract algebra”.

So for example, if I have the integers and multiplication, this is a monoid[1]. The identity element is zero, which is an integer, and multiplication is an associative binary operation. It takes two integers and returns an integer.

Once you realise you have a monoid, if you do maths that only relies on the monoid properties then it applies to all monoids, so you could drop a different monoid in there and everything would still work. This ends up being very much like how typeclasses work in Haskell or traits in Rust.

[1] For the curious, it’s not a “group” because the integers don’t have multiplicative inverses. If I have x=2, there is no integer that I can multiply that by to get 1. Integers with addition on the other hand is a group, which is a monoid with the additional property that inverses are present.

bern4444

5 months ago

2 replies

> The identity element is zero

I think the identity element would be 1 for integers and multiplication, right?

0 would be the identity element for integers and addition.

aranchelk

5 months ago

1 reply

That and also why start with multiplication? String concatenation, addition, list concatenation all make more intuitive sense to a working programmer.

What's a straightforward way to combine a bunch of numbers? Just keep multiplying them to get a resulting volume in an ever-higher dimensional space.

mananaysiempre

5 months ago

The working programmer might be interested in the series on ropes on the Xi Editor website[1] as a practical application, as it motivates the concept as it goes. (Alternatively, if you’ve taken an algorithms class you have probably encountered the idea of computing things over an interval of an array by storing them in for each node of a tree that flattens to that array, such as a search tree or interval tree.)

[1] https://xi-editor.io/docs/rope_science_00.html

seanhunter

5 months ago

Yes. Sorry I edited my original to change the operation.

xeonmc

5 months ago

3 replies

    For the curious, it’s not a “group” because the integers don’t have multiplicative inverses. If I have x=2, there is no integer that I can multiply that by to get 1. Integers with addition on the other hand is a group, which is a monoid with the additional property that inverses are present.

Would one be correct to say that square matrices are an example of monoids, since they have an identity element and are associative, but might not necessarily have inverses if their determinant is zero?

Jaxan

5 months ago

Yes

sd9

5 months ago

The operation is important too. Square matrices over integers with matrix multiplication is (just) a monoid. Square matrices with addition are a monoid too (but also a group, because there is an additive inverse).

Put it all together and it’s called a ring

ndriscoll

5 months ago

Additionally, if you restrict to invertible matrices with matrix multiplication, they are also a monoid (so they are a submonoid), and in fact a group, the general linear group. If you restrict again to matrices with determinant 1, it's again itself a group (a subgroup, and also a submonoid), the special linear group.

IngoBlechschmid

5 months ago

Somebody asked in a now-deleted comment: 'Right, and what does it mean in the context of "A monad is just a monoid in the category of endofunctors"?'

Here is an answer to this question:

What the parent poster referred to are "monoids in the category of sets". You can recognize this as they have introduced the carrier as (just a) set.

But the notion can be generalized. For instance, a "monoid in the category of datatypes" would not be given by a mathematical set and a mathematical binary operation, but by a datatype and a computable binary operation. (To make this precise, I would need to fix which "category of datatypes" I have in mind. It could be the category of Haskell types and Haskell functions, for instance; but C types and functions would work just as well. I could also go all the way to the effective topos, which contains lots of types which most mainstream programming languages are missing such as true quotient types.)

Finally, a "monoid in the category of endofunctors" is given by an endofunctor and a natural transformation. Endofunctors can be pictured as container kinds (e.g. ordered lists, unordered lists, Maybe/Optional, trees, vectors of length n, pairs, ...) and the additional datum of the natural transformation is what singles out those container kinds which support a "flattening operation" from those which don't. For instance, we can flatten a list of lists into one (long) list, but we cannot flatten a pair of pairs into one pair (we would need to drop two of the four elements).

Just as it is quite convenient that many results about integers or lists also hold for all monoids in the category of sets, it is quite nice that many results about monoids in the category of sets also hold for all monoids in all categories and hence in particular to monads.

mgaunard

5 months ago

1 reply

Something I've found useful is being able to maintain a CDF over a sliding window of samples.

The way I've traditionally done it is with an augmented binary tree where I can easily compute the prefix sum of the sample values.

I'm not sure if there are any insights from that article that would allow me to do it better.

pizza

5 months ago

FWIW you might be interested in this, generalizing to many types of materialized views over increments of data via an equivalent of the chain rule over streams https://muratbuffalo.blogspot.com/2024/11/dbsp-automatic-inc...

renox

5 months ago

Interesting topic, too bad I didn't know about this a few years ago..

fuckaj

5 months ago

I am interested in the type of problem where you need last N values but last approx N values will not do. If you can make do with approx then just bucket them into 100s or whatever. Then there is no need to fo anything fancy for deletes and buckets are already aggregated.

The for latency you could keep histogram counts.

View full discussion on Hacker News

ID: 44958421Type: storyLast synced: 11/20/2025, 6:48:47 PM

Want the full context?

Jump to the original sources

Read the primary article or dive into the live Hacker News thread when you're ready.

Open link View on HN