search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Pattern synonyms and Data instances #92

Closed treeowl closed 1 year ago

treeowl commented 1 year ago

Fixes #50.

treeowl commented 1 year ago

@konsumlamm I suspect we'll want similar pattern synonyms for max-queues, but do we want

(:>) :: Ord a => MaxQueue a -> a -> MaxQueue a

or

(<:) :: Ord a => a -> MaxQueue a -> MaxQueue a

I think the first option is clearer, since I think of the maximum as coming after the rest. But ergonomics will then be quite different between min-queues and max-queues, and I'm not sure how good that is. Hmmmmm....

Semi-separately: now that the Ord instance for Data.Ord.Down is decent, we should switch to it. We could then export MaxQueue and MaxPQueue concretely (with their constructors). Should they then use derived Data instances? I think that probably makes the most sense, but I'm not sure.

treeowl commented 1 year ago

@konsumlamm In case you didn't notice, I was hoping for a review of this.

konsumlamm commented 1 year ago

@konsumlamm In case you didn't notice, I was hoping for a review of this.

I did notice, don't worry. It just takes some time to get into the issue again and I still have other things to do.

konsumlamm commented 1 year ago

I'm reluctant about the pattern synonyms, as they're not O(1) (while standard patterns are) and people might expect them to be, unknowingly introducing a slowdown.

Is there a problem with keeping the Constrs as is?

konsumlamm commented 1 year ago

Btw, if you have time, could you take a look if #55 can be closed?

treeowl commented 1 year ago

I definitely like pattern synonyms for things that are at worst polylogarithmic. I think that's fine; I can document the bounds explicitly. I will update the PR to deal with the other issues you pointed out.

treeowl commented 1 year ago

@konsumlamm I think I've addressed all the issues. I would like to squash the commits rather than merging them intact.

treeowl commented 1 year ago

Is there a problem with keeping the Constrs as is?

I really don't like the inconsistency between the way the plain versions and Prio versions conceptualize their types. I also think it's much easier to "explain" the Data instances by reference to bidirectional patterns than by reference to plain functions (one of which doesn't even bother to exist). Since the Data instance for MinQueue was fairly broken from the jump, I'd be pretty surprised if anyone actually used them in any way that the proposed changes would break.

konsumlamm commented 1 year ago

Hmm, ok.

As for your question about :> vs <:, I don't really have an opinion on that. I'm fine with using :>, as that's similar to what Data.Sequence does.

Do you also want to improve the Data instances for max queues in this PR or leave that to a future PR?

treeowl commented 1 year ago

I don't want to make any decisions whatsoever about max queues in this PR. I'll open a new one for pattern synonyms for them.

konsumlamm commented 1 year ago

I would like to squash the commits rather than merging them intact.

That's what I always do anyway.

treeowl commented 1 year ago

Are you ready to approve?