search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Reconsider the implementation of minView #36

Closed treeowl closed 3 years ago

treeowl commented 3 years ago

minView pushes carries down separately, which must lead to extra allocation. A possible alternative is to use the classical binomial heap deletion. Walk down the spine to find the minimum, walk back up to the minimal node, walk down its children, and then on the way up, merge those children into the original tree. This ends up case-matching on the spine twice, but that's pretty cheap. I'm not 100% sure I can make this idea work without additional heap allocation, but I think I probably can.

treeowl commented 3 years ago

No.... I don't think I can. This would work with a GADT-based implementation, but the higher-order nested datatype approach seems incompatible; we'd need to build up a function that knows how to walk the node. Grrr....