@shachaf @pkhuong I’m not sure I understand your point, Okasaki’s whole book is dedicated to exactly the topic of evaluating the cost of lazy languages, and showing the actual costs by being careful about which values are evaluated when (in the case of queues it uses a really cleaver trick to evaluate the reversing of the input list one step at a time as the output is popped)

As I was replying, I realised that what I’m suggesting is basically exactly what the code actually does, I’d missed the “staging product” being kept around, for exactly the purpose I’m going through below. I’m going to keep it because I spent like half an hour writing it, and at the very least it’s something I can refer to in the future.

This can definitely be done by using a few stacks, if you have laziness available, I’ll have to see if I can make the Haskell version work as I expect, it’s not a big change from classical Okasaki queues at all, except with the addition of the A/B tags below.

—— feel free to stop reading here ——

Anyway, the point I’m making is that at any time after you take the ingestion queue and add it to the end of the excretion queue, the monoid product of all the old values, eg a!c, b!c plus the sum computed in the ingestion list d!f, plus whatever has been computed in the ingestion queue h!k is the total product. So in your case, when using mutable arrays, you can stop moving the write pointer once you’ve reached the old elements, i.e, c, as long as you hold onto the sum d!f. You don’t need to keep updating at that point.

You just store d!f when you start moving the write pointer and mark each element in the excretion list with a tag saying whether it’s an old or a new item (which is part of the work done with the write pointer). This can be done by just using a single bool or enum A or B to signify if the value in the excretion list needs the have the stored d!f added to it or not:

I’m just trying to understand if there’s a reason to recompute d!f again when it’s been computed once during ingestion and them seemingly thrown away. As long as you maintain the invariants that you will always have moved the write pointer up the first place where B occurs by the time you dequeue it, you end up with the same monoidal product*, but you do less work because you don’t need to add d!f to a!c - c!c except when you dequeue

• or sum - we usually talk about monoidal sums in Haskell land for some reason, which is why I’ve used sum and + here.

@shachaf @pkhuong laziness is the thing that makes Okasaki queues work, by carefully controlling what is evaluated when, to get O(1) enqueue and dequeue.

But the observation I made from your post was that I think you’re doing more work than you need to - all the values in the old excretion list when combined with the product calculated for the product of the new tail of the new list (the previous ingestion list’s product), and the current ingestion list’s product makes the total product. So you just need to know when you’ve reached the end of the old excretion list, which can be done with an extra bool per item.

@pkhuong @shachaf I just finished reading this, and it feels to me that the idea that we can’t use stacks might be wrong - the classic Okasaki three-stack O(1) purely functional queue feels very similar, the function that handles reversing the of the ingestion-to-staging process, which appends to the end of the old excretion queue seems to be sitting at exactly the right place to be computing the write pointer data, at least for the staging data.

It also feels like you don’t need to actually write into the old-excretion stack at all, as long as you keep a reference to the ingestion product as you’re reversing, the monoid product of any of the old ingestion values is always its current product, times the old ingestion product, times the current product.

I feel I need to go build this in Haskell now (though I feel like @shachaf would have beaten me to that). I’ve probably missed something important though.

@wezm Thanks, as always, Wes, for a great response to my public whinging 😄 I'll check out the forum and see what they have to say.

I agree with the level of security assessment for BitWarden, this is the main thing which keeps me using 1Password - every other part of the experience of the app has been going down hill, 1Password 8 was, and continues to be, an awful user experience. I'm constantly lost trying to find the sections I'm looking for when they were always right there in v7.

And as you've pointed out in the past, the use of Electron is deeply troubling, and always reminds me of