The for latency you could keep histogram counts.
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.
seanhunter•5mo ago
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•5mo ago
I think the identity element would be 1 for integers and multiplication, right?
0 would be the identity element for integers and addition.
aranchelk•5mo ago
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•5mo ago
[1] https://xi-editor.io/docs/rope_science_00.html
seanhunter•5mo ago
xeonmc•5mo ago
Jaxan•5mo ago
sd9•5mo ago
Put it all together and it’s called a ring
ndriscoll•5mo ago
IngoBlechschmid•5mo ago
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.