Improve worst-case bounds

[treeowl]

Previously, minView was amortized O(log n) but worst-case O(n). Improve that to amortized and worst-case O(log n) (ignoring the impact of repeated applications of mapMonotonic). In informal testing, these changes lead to large performance improvements.

• Previously, lots of things were suspended that didn't need to be. Document the actual laziness requirements with a debit invariant and be more eager where allowed.

• Rework extractBin to calculate the minimum on the way down instead of on the way up. This avoids building a chain of thunks that (if forced) actually rebuilds the queue.

I chose to make the internal nodes of the binomial tree quite strict. For most purposes, this is good. The only downside is that mapMonotonic is now slower, since it cannot be "operationally fused" with surrounding operations. This doesn't seem like a huge deal, since I don't imagine mapping over priority queues is something that happens all that much.

Closes #24

[treeowl]

Looks good, all in all. Just some minor nitpicks and questions, in general this looks good to go.

But disclaimer: I did not benchmark this to any noteworthy degree, and I don't feel like I can make an educated comment on the "Debit invariants". So I am a bit lost on the exact implications of the strictness changes, sorry.

If you have any expressions to test the performance with / highlight the changes I can re-test them and play around a bit. But I would be fine with merging it; the optimisations make sense and otherwise I trust your judgement.

For the new approach to forcing on insert, look at the Hinze-Paterson finger tree paper. If you just build a new thunk around the old child thunk, you get thunk chains with O(n) worst-case resolution. An easy test is to build a big heap (some millions or tens of millions of elements) with insert, evaluate it, print a message, then print take 5 . toAscList of the thing. Previously, there'd be a significant lag (a few seconds) between the two outputs. With these changes, there is no lag.

[treeowl]

Could you explain what I was unclear about regarding the debit invariant? That's kind of important to understanding what's going on!

[treeowl]

I think that should address all your concerns.

[lspitzner]

I have pushed a rebased version of this branch to this repository; there was only a very simple conflict. I can force-push to this branch as well, I just don't like to do that out of the blue.