treeowl · GitHub

@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.
* Force on cascade in `insertMin`.
* Expand the strictification to key-value queues. This should
  be good for performance of everything except `mapKeysMonotonic`,
  `mapWithKey`, and `fmap`.
Closes lspitzner#24
Improve list conversion
* Implement a strictly accumulating `fromAscList`.
* Use one less comparison per element in `fromList`.
Make min-replacement faster
Use `insertMin`/`incrMin` to avoid further comparisons when the
new key replaces the minimum.

Read the original on github.com ↗