Monuses and Heaps

9 points by lalitm

Maybe I'm a bit too thick for this post, but coming from mostly using imperative languages nowadays, I'm struggling to come up with concrete practical examples where the articulated abstraction is useful over the "stupid" thing you would do.

E.g. for general graph search, I'd reach for Dijkstra or A*. I don't think you can get away with storing relative distances there due to the presence of multiple paths.

For the Phases example, if you have ordering constraints, you probably have dynamic dependencies between things so you have a Monad, not just an Applicative. When you have a shared resource used by individual computations one different branches, they cannot happen "completely independently."

Consider you have a build DAG and you want to do a critical path search. If the actions themselves are nodes, then the naive thing would be to store the time for each action at the corresponding node (not the total time from the start).

Re: the Search type, I've used that kind of lazy tree representation before and it's all fine and dandy until the memory usage blows up in your face because there's no explicit tracking for "how much of the state space I'm holding" at any given time.

It's quite possible I'm missing something -- I would love if someone could share a concrete example of a problem they've hit where they think having the formulation in the article would've been genuinely useful.

rprospero
Not really touching on the heaps part of the article, but, out of necessity, I've invented a poorly implemented, half baked version of monuses multiple times when dealing with undo.

I always get there via the same, three-step process:
1. Every time the program state changes, push the new state onto a stack. When the user performs an undo, pop the old state off the stack. This is easy, but it devours memory.
2. Create a monoid that represents user actions and store those actions on the stack. When the user performs an undo, pop the last action off the stack and recompute the current state. This generally uses far less memory, but undo is now O(n) in time, where n is the size of the undo list.
3. Make the monoid action a monus. When the user perform an action, push (0 ∸ action) to the stack, where 0 is the monoid's identity element. When the user performs an undo, pop the top item off the stack and apply it to the current state to get the previous state. Undo goes back to being O(1), but still retains the memory efficiency.
- typesanitizer
  
  That's a neat example, thanks!