Fix mapMaybe and mapEither

lspitzner / pqueue

Haskell priority queue package

Other

15 stars 13 forks source link

Fix mapMaybe and mapEither #111

Closed treeowl closed 1 year ago

treeowl commented 1 year ago

Fix incorrect behavior of mapMaybe and mapEither for MinQueue.

To do:

[x] Add tests.
[x] Port all these changes to MinPQueue.

Fixes #110.

treeowl commented 1 year ago

Another thing: we should verify that the monotonic versions are actually faster than the simple ones. That's not even slightly obvious to me. They're extremely hard to understand. At first, I thought they were structured to avoid unnecessary comparisons, but looking at them more closely, that doesn't seem to be the case.

treeowl commented 1 year ago

Ah, but maybe it could be made so? I have to think this over....

treeowl commented 1 year ago

I fixed the monotonic code to take what advantage it can of the ordering. However, it was still significantly (although modestly) slower than just using plain old mapMaybe and mapEither. So let's not add these monotonic specials, and just do the simplest possible thing. Less code, less error prone, and faster sounds like a nice trifecta to me.

treeowl commented 1 year ago

@konsumlamm, would you please try to review this soon?

treeowl commented 1 year ago

I believe I've dealt with all your concerns.