The queue method is popular, but there's a much faster (branch-free) and in my opinion simpler way, known as the van Herk/Gil-Werman algorithm in image processing. It splits the input into windows and pairs up a backward scan on one window with a forward scan on the next. This works for any associative function. I was very surprised when I learned about it that it's not taught more often (the name's not doing it any favors)! And I wrote a tutorial page on it for my SIMD-oriented language, mostly about vectorizing it which I didn't quite finish writing up, but with what I think is a reasonable presentation in the first part: https://github.com/mlochbaum/Singeli/blob/master/doc/minfilt...

I also found an interesting streaming version here recently: https://signalsmith-audio.co.uk/writing/2022/constant-time-p...

EDIT: On closer inspection, this method is equivalent to the one I described, and not the one I'm used to seeing with queues (that starts my tutorial). The stack-reversing step is what forms a backwards scan. The combination of turning it sequential by taking in one element at a time but then expressing this in functional programming makes for a complicated presentation, I think.

This is similar to an approach I use but instead of a queue, I accomplish this using a ring buffer that wraps around and overwrites entries older than window size. We maintain a global window aggregate, subtract ring buffer slot aggregate for entries dropping out and accumulate new entries into new slot aggregate while adding it to the global aggregate. Everything is o(1) including reads, which just returns the global window aggregate.

That was a well written and easily approachable blog post on what I found to be an interesting topic. Aside from the topic itself, I think I also learned a bit about structuring technical articles.

This is a very interesting algorithm which is more or less known in the folklore, but is still relatively obscure. I have used it as a part of temporal logic monitoring procedure: https://github.com/Agnishom/lattice-mtl/blob/master/src/Moni...

I have made a quick c++ implementation for those unfamiliar with Haskell :

https://gist.github.com/unrealwill/5ca4db9beefafaa212465277b...

I translated this to F# for my own edification. It's more verbose, but perhaps easier to understand for non-Haskellers.

https://github.com/brianberns/AnnotatedStack

Competitive Programming in Haskell...I can only define this as Masochistic Aesthetics...