search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Deprecate seqSpine #95

Closed treeowl closed 1 year ago

treeowl commented 1 year ago

The seqSpine function was useful back in the day when all sorts of operations were written in a way that allowed thunks to accumulate along the spine. Now, we carefully force as much of the spine as the amortized bounds allow, which eliminates this problem in general. The only operations that still accumulate thunks along the spine are monotonic maps, and forcing the spines of those just leads to the creation of more thunks at the leaves—it's not really useful.

konsumlamm commented 1 year ago

Can you elaborate why mapU/mapKeysMonotonic don't benefit from seqSpine? Is it because all the work is accumulated in the elements?

treeowl commented 1 year ago

Can you elaborate why mapU/mapKeysMonotonic don't benefit from seqSpine? Is it because all the work is accumulated in the elements?

Exactly. I've updated the documentation to explain that, and I've also added references to more functions with similar issues in he Prio case.

treeowl commented 1 year ago

Mapping over a queue gives you (a thunk for) the first element, and a thunk for the rest of the queue. As you push your way down the spine, successive vertebrae each produce larger and larger numbers of thunks.

treeowl commented 1 year ago

Hahaha. This entire PR is based on me getting confused. Whooops. There really was a (minor) reason for these functions to persist, and it actually was only the functions that were in the documentation. I should explain more about why that is somewhere...