Factor out (the deprecated) Lwt_pqueue

[aantron]

Lwt_pqueue (.mli, .ml) is a pretty ordinary priority queue, implemented as min-heap, that Lwt uses internally.

Since Lwt is not a basic data structures library, Lwt would much rather rely on a priority queue implementation in the standard library, or some data structures library that we choose. Unfortunately, priority queues are not included in the standard library.

This issue is for tracking Lwt_pqueue, lobbying for priority queues in the standard library, and any other related activity or discussion.

Despite the fact that Lwt_pqueue is an implementation detail of Lwt, it is accessible when linking with Lwt. There is some code that takes advantage of its existence, which is why Lwt deprecated Lwt_pqueue in c86cba3. We don't plan to actually remove it in the near future, to avoid breaking code that still uses it. We just want to switch to a common implementation.

The technical side of this issue is easy, but it is organizationally difficult to get this arranged.

[c-cube]

The module is pretty simple, though. How much of a technical debt is it? Lobbying for heaps in the stdlib would take a while anyway, and only work on the next version of OCaml…

[aantron]

How much of a technical debt is it?

It's not a big technical debt. Still, I think it's a good idea to permanently note that priority queues belong elsewhere (ideally in stdlib), and Lwt was apparently forced to implement its own version of them.

Other projects that currently refer to Lwt_pqueue also would have benefitted from a priority queue in the stdib. These projects might have an easier time deciding to use an extra data structures library, however.

This is an issue for the long term. If there are related discussions elsewhere about this, this issue provides people with something to link to. Maybe it will stimulate or remind people that this ought to eventually be done.

Lobbying for heaps in the stdlib would take a while anyway, and only work on the next version of OCaml…

True, but eventually the minimum version of Lwt might catch up to that version of OCaml, and we can switch. There may be shims available. Lwt currently uses the result shim, admittedly a simple one, which is only necessary while Lwt continues to support 4.02 (which I think we intend to do for a while).

IMO the sooner stdlib gets a more thorough set of basic data structures, the better.

[aantron]

Also, #135 ("Lwt_pqueue not documented") is the previous issue on Lwt_pqueue.

[c-cube]

I agree on adding more of these useful structures to the stdlib, but I'm tired of trying and a bit pessimistic. Nice to hear that you want to continue supporting 4.02 :-)

[aantron]

Closing this, as we've made it an implementation detail, deprecated using it, and can factor it out later as needed.

Also found psq.