search

lspitzner / pqueue

Haskell priority queue package
Other
15 stars 13 forks source link

Reason that internal functions take (<=) as argument #22

Closed konsumlamm closed 2 years ago

konsumlamm commented 4 years ago

What is the reason that some functions (for example insert and union) delegate to internal helper functions that take a less-than-or-equal function? As far as I can tell, they are only ever called with (<=), which eliminates the point of having them, unless I'm missing something.

treeowl commented 3 years ago

Yes, this seems to be so. Once I'm finished with #24, I will take a look. The way it's currently written also seems likely to block up the GHC specializer. That could presumably be fixed, but the fix would require ScopedTypeVariables. I love that extension myself, but this package seems very Report Haskell.

treeowl commented 2 years ago

We definitely want to arrange for Ord specialization, because it really does make the queues faster. There are two possible approaches:

  1. Get rid of the Leq stuff and add a few INLINABLE pragmas. Blam, specialization happens.
  2. Try to give @Fuuzetsu what they have asked for, preserving the Leq stuff. This absolutely requires ScopedTypeVariables. Unfortunately, it's also a bit tricky to actually get things to specialize. I was only able to do so by adding copious INLINE pragmas—INLINABLE doesn't do the trick. This makes me a bit nervous from the standpoint of code size, compilation time, etc. I think I'd rather not :slightly_frowning_face:.
Fuuzetsu commented 2 years ago

Just to be clear, I think 2 shouldn't require you to do anything special. I'm just asking something like this: "if there's a function in the code that's used internally to perform something efficiently but is not exposed because it relies on internal invariants, please expose it and allow everyone to use it at their own risk".

I'm definitely not asking for you to arrange internals in some specific way.

treeowl commented 2 years ago

@Fuuzetsu , okay. To be clear, I think it would be nice to be able to do that "you provide an operator and promise it's a total ordering of equivalence classes". That's why I put some effort into getting it to work nicely. I'm happy to expose internals, and especially the internal types that make up the queues.

konsumlamm commented 2 years ago

@treeowl would you be ok with a PR to remove the LEq a arguments (and use Ord a => a instead)? This would mean that #34 most likely won't happen (at least not by reusing the internal functions, but we both agree that the interface would be ugly).

As far as I understand, #18 is only about exposing internal modules in general, not functions taking a LEq a argument specifically (@Fuuzetsu correct me if I'm wrong).

Fuuzetsu commented 2 years ago

Yes, #18 is only about asking for access to code that's already written and available and merely needs exposing by moving module(s) to a different section in cabal file. The whole LEq stuff was just an example of what this is useful for for the code at that point in time.In the end though, it is just .Internals: it is up to you to change the implementation without warning and if I don't like it, I will use a specific version.

There should be 0 effort being put into anything to keep some sort of specific implementation just because of #18 or anything said within.

treeowl commented 2 years ago

Let's get #33 merged in some form first, even if it's not quite ready to expose yet, to limit the churn. Then yes, let's do the simplest specialization thing.