Priority queue docs without dupes

.gitignore

_b0

.merlin

# Generated by brzo
S ./**
B /Users/dbuenzli/tmp/pqueue.mli/_b0/brzo/ocaml-doc/**
B /Users/dbuenzli/.opam/4.14.2+ocamlnat/lib/ocaml/**

BRZO

pqueue.mli

(**/**)
module type BasePoly := sig

   type 'a elt
   (** The type for elements. *)

   type 'a t
   (** The type for priority queues. *)

   val create : unit -> 'a t
   (** [create ()] is a new empty priority queue. *)

   (** {1:adding Adding elements} *)

   val add : 'a t -> 'a elt -> unit
   (** [add q p x] adds the element [x] with priority… *)
end

module type BaseMinPoly := sig
  include BasePoly (** @inline *)

  val min_elt : 'a t -> 'a elt
  (** [min_elt q] returns an element in queue [q] with minimal priority,
      without removing it from the queue, or raises {!Empty} if the queue
      is empty. *)
end

module type BaseMaxPoly := sig
  include BasePoly (** @inline *)

  val max_elt : 'a t -> 'a elt
  (** [max_elt q] returns an element in queue [q] with minimal priority,
      without removing it from the queue, or raises {!Empty} if the queue
      is empty. *)
end

module type BaseElt := sig

  (** {1:queues Queues} *)

  type elt
  (** The type for prioritized elements. *)

  type t
  (** The type for priority queues. *)
end

module type BasePriority := sig
  (** {1:queues Queues} *)

  type priority
  (** The type for priorities. *)
end
(**/**)


(** {1:order Ordered types} *)

(** The type for Ordered types. *)
module type OrderedType =
sig
  type t
  (** The ordered types. *)

  val compare : t -> t -> int
  (** [compare] is a total order on value of type {!t}. *)
end

(** {1:elements Queues with prioritized elements} *)

(** The type for queues sorted by minimal element. *)
module type MinElt = sig
  include BaseElt (** @inline *)
  include BaseMinPoly with type 'a elt := elt and type 'a t := t (** @inline *)
end

(** The type for queues sorted by maximal element. *)
module type MaxElt = sig
  include BaseElt (** @inline *)
  include BaseMaxPoly with type 'a elt := elt and type 'a t := t (** @inline *)
end

(** [MakeMinElt (Elt)] is a queue sorted minimal by [Elt.t] values. *)
module MakeMinElt (Elt : OrderedType) : MinElt with type elt = Elt.t

(** [MakeMinElt (Elt)] is a queue sorted maximal by [Elt.t] values. *)
module MakeMaxElt (Elt : OrderedType) : MaxElt with type elt = Elt.t

(** {1:queues Polymorphic queues with priorities} *)

(** The type for polymorphic queues sorted by minimal priority. *)
module type MinPriority = sig
  include BasePriority (** @inline *)
  include BaseMinPoly with type 'a elt = priority * 'a  (** @inline *)
end

(** The type for polymorphic queues sorted by maximal priority *)
module type MaxPriority = sig
  include BasePriority (** @inline *)
  include BaseMaxPoly with type 'a elt = priority * 'a (** @inline *)
end

(** [MakeMinPriority (P)] is a polymorphic queue sorted by minimal [P.t]
    values *)
module MakeMinPriority (Priority : OrderedType) : MinPriority
  with type priority = Priority.t

(** [MakeMaxPriority (P)] is a polymorphic queue sorted by maximal [P.t]
    values *)
module MakeMaxPriority (Priority : OrderedType) : MaxPriority
  with type priority = Priority.t

sync.sh

#!/bin/sh
rsync -a _b0/brzo/ocaml-doc/ erratique:erratique.ch/html-tmp/pqueue

@dbuenzli can we maybe iterate on your proposal here?

I would suggest the following changes for your consideration:

1. use module type Base := sig .. end, so that Base is not exported in the resulting signature. Same with other modules that are not meant to be shown to users.
2. use the Poly prefix to name signatures that use a parametrized type of elements: BasePoly, BasePolyMin, BasePolyMax
3. include the proposed the functors in the mli (we cannot bikeshed on their naming for now!)
4. instead of exposing {Min,Max}Priority, expose Poly{Min,Max}, and document their 'a elt = priority * 'a instance as a typical example.

I did that. The result is on https://erratique.ch/tmp/pqueue/html/pqueue/Pqueue/index.html

I went with Poly suffixing, because it's weird to have Elt suffixing and Poly prefixing and Elt prefixing is equally weird. I'm not sure what you meant by 4.

I went with Poly suffixing, because it's weird to have Elt suffixing and Poly prefixing and Elt prefixing is equally weird. I'm not sure what you meant by 4.

We could also maybe drop the Poly for the Poly ones.

To clarify: in my mind MinPriority and MinPoly are two different interfaces:

module type MinPriority = sig
  type priotity
  type 'a t
  val add : 'a t -> priority * 'a -> unit
end

module type MinPoly = sig
  type 'a elt
  type 'a t
  val add : 'a t -> 'a elt -> unit
end

module MakeMinPriority : functor (Prio : OrderedType) -> MinPriority with priority = Prio.t
module MakeMinPoly : functor (Elt : OrderedPolyType) -> MinPoly with type 'a elt = 'a Elt.t

in your first design you exposed (Make)MinPriority only. I propose to expose (Make)MinPoly only, not to use the name MinPoly for what you called MinPriority (I'm fine with that name).

Note: exposing only Make{Min,Max} and Make{Min,Max}Poly gives an easy way to name the sections in the interface:

• "Priority queues": (Make){Min,Max}
• "Polymorphic priority queues": (Make){Min,Max}Poly

(I can do the work of writing a patch myself if this is needed to clarify things.)

Ok I moved back Poly to Priority. Regarding exposing the pure Poly interface with the confusing OrdererdPolyType I don't think it should be done without offering a compelling use case in hand.

The programmer will already lose enough time pondering whether to use Elt vs Priority (which I wouldn't even have included), I don't think it's worth adding yet another choice, especially since I don't see a good use for it. I think it's always better to act on actual needs rather than hypothetical or phantasised needs; especially when the things you don't provide can be added later without disturbing what you added in the first place.

Also /cc @backtracking since he's the one who proposed all that.

with the confusing OrdererdPolyType

And just to make things clear as to why I deeply object to exposing this signature. As far as I'm concerned anything sound called OrderedPolyType in the Stdlib should be:

(** The type for Ordered polymorphic types. *)
module type OrderedPolyType =
sig
  type 'a t
  (** The ordered type. *)

  val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
  (** [compare] is a total order on value of type {!t}. *)
end

I don't think that it is that clear-cut that you want to take a comparison function of 'a. This only makes sense if 'a describes pieces of data included within 'a t (they occur in positive occurrences in the type), that is if t is a Functor. So this could be named OrderedFunctor and it is a slightly different notion.

Going back to MinPriority vs. MinPoly vs. nothing:

1. I prefer MinPoly because it is more general than MinPriority and not harder to use. In addition I think that there are less risk of misuse of MinPoly -- it is clearer when it should be used instead of just Min.
2. My main reason to ask to have both Min and MinPoly is that it is not clear that a given design for Min will later gracefully extend to support MinPoly or MinPriority if the need arises. This is partly alleviated by the fact that you have proposed a design that has this quality, it can be extended, so cutting it down to Min only now sounds reasonable.
3. This said, I would still be in favor of including (Make)MinPoly, because I think that there is not much cost (we can share all the code), and I have experienced being annoyed by lack of the generality of some stdlib modules in the past. In my experience improving things after the fact is difficult: users that hit a limitation typically don't tell us, and even when they do it is hard to make the change.

I guess that I would leave the final decision of including MinPoly or not to @backtracking.

To be extra clear, here is the interface that I have in mind, adapted from @dbuenzli's proposal:

(**/**)
module type PolyTypes := sig
   (** {1:queues Queues} *)

   type 'a elt
   (** The type for elements. *)

   type 'a t
   (** The type for priority queues. *)
end

module type MonoTypes := sig
   (** {1:queues Queues} *)

   type elt
   (** The type for elements. *)

   type t
   (** The type for priority queues. *)
end

module type BaseOps := sig
   type 'a elt
   (** The type for elements. *)

   type 'a t
   (** The type for priority queues. *)

   val create : unit -> 'a t
   (** [create ()] is a new empty priority queue. *)

   (** {1:adding Adding elements} *)

   val add : 'a t -> 'a elt -> unit
   (** [add q p x] adds the element [x] with priority… *)
end

module type MinOps := sig
  include PolyTypes (** @inline *)

  val min_elt : 'a t -> 'a elt
  (** [min_elt q] returns an element in queue [q] with minimal priority,
      without removing it from the queue, or raises {!Empty} if the queue
      is empty. *)
end

module type MaxOps := sig
  include PolyTypes (** @inline *)

  val max_elt : 'a t -> 'a elt
  (** [max_elt q] returns an element in queue [q] with minimal priority,
      without removing it from the queue, or raises {!Empty} if the queue
      is empty. *)
end
(**/**)

(** {1:mono Priority queues} *)

(** The type for Ordered elements. *)
module type OrderedType =
sig
  type t

  val compare : t -> t -> int
  (** [compare] is a total order on value of type {!t}. *)
end

(** The type of queues where the minimal element is first. *)
module type Min = sig
  include MonoTypes (** @inline *)
  include BaseOps with type 'a elt := elt and type 'a t := t (** @inline *)
  include MinOps with type 'a elt := elt and type 'a t := t (** @inline *)
end

(** The type of queues where the maximal element is first. *)
module type Max = sig
  include MonoTypes (** @inline *)
  include BaseOps with type 'a elt := elt and type 'a t := t (** @inline *)
  include MaxOps with type 'a elt := elt and type 'a t := t (** @inline *)
end

(** [MakeMin (Elt)] is a queue sorted by minimal [Elt.t] values. *)
module MakeMin (Elt : OrderedType) : Min with type elt = Elt.t

(** [MakeMin (Elt)] is a queue sorted by maximal [Elt.t] values. *)
module MakeMax (Elt : OrderedType) : Max with type elt = Elt.t

(** {1:queues Polymorphic priority queues}

    The following, more complex functors create polymorphic queues of
    type ['a t], just like other polymorphic containers (lists,
    arrays...). They requires a notion of "polymorphic elements" ['a
    elt] that can be compared without depending on choice of ['a].

    One usage scenario comes from certain polymorphic containers that
    embed priority information, for example:
    {[
      type 'a task = {
        run : unit -> 'a;
        cancel : unit -> unit;
        priority : int;
      }

      module TaskQueue = PQueue.MakeMaxPoly(struct
        type 'a elt = task
        let compare t1 t2 = Int.compare t1.priority t2.priority
      end)
    ]}

    Another usage scenario is if the user wants to pass priorities
    separately from the value stored in the queue. This is done by pu
    using pairs [priority * 'a] as elements.
    {[
      module Prio : OrderedType = ...
      
      module PrioQueue = PQueue.MakeMinPoly(struct
        type 'a elt = Prio.t * 'a
        let compare (p1, _) (p2, _) = Prio.compare p1 p2
      end)

      (* for example, we now have: *)
      PrioQueue.add : 'a PrioQueue.t -> Prio.t * 'a -> unit
      PrioQueue.min_elt : 'a PrioQueue.t -> (Prio.t * 'a) option
    ]}
  *)

(** The type for ordered elements of a polymorphic queue. *)
module type OrderedPolyType =
sig
  type 'a t

  val compare : 'a t -> 'b t -> int
  (** [compare] is a total order on value of type {!t}. *)
end

(** The type of polymorphic queues where the minimal element is first. *)
module type MinPoly = sig
  include PolyTypes (** @inline *)
  include BaseOps with type 'a elt := 'a elt and type 'a t := 'a t (** @inline *)
  include MaxOps with type 'a elt := 'a elt and type 'a t := 'a t (** @inline *)
end

(** The type of polymorphic queues where the maximal element is first. *)
module type MaxPoly = sig
  include PolyTypes (** @inline *)
  include BaseOps with type 'a elt := 'a elt and type 'a t := 'a t (** @inline *)
  include MaxOps with type 'a elt := 'a elt and type 'a t := 'a t (** @inline *)
end

(** [MakeMinPoly (Elt)] is a queue sorted by minimal [Elt.t] values. *)
module MakeMinPoly (Elt : OrderedPolyType) : MinPoly with type 'a elt := 'a Elt.t

(** [MakeMaxPoly (Elt)] is a queue sorted by maximal [Elt.t] values. *)
module MakeMaxPoly (Elt : OrderedPolyType) : MaxPoly with type 'a elt := 'a Elt.t

Notes:

• I find the resulting concepts more regular than with {Min,Max}Priority, there are less subtle name distinctions to find.
• I find the use-cases for polymorphic queues proposed in the documentation reasonably convincing -- if abstract.
• I realized when writing the documentation that the polymorphic version could have compare : 'a t -> 'b t -> int, which clarifies that the comparison should not depend on the type parameter.

Summary: I am now in favor of either including both (Make){Min,Max} and (Make){Min,Max}Poly or just (Make){Min,Max}, which I understand is now @dbuenzli's preference. I think that both options are good and I am happy with whatever has the preference of the people doing the work.

1. I prefer MinPoly because it is more general than MinPriority and not harder to use. In addition I think that there are less risk of misuse of MinPoly -- it is clearer when it should be used instead of just Min.

I find the result much harder to use.

1. It doesn't convey the basic simple distinction between priorities on elements (Elt) and separate priorities with and polymorphic elements (Priority). Some mental gymnastics is needed to get to this.
2. It cannot be used with simple and easy to understand classical functor arguments (Int, Float, etc.).

3. and I have experienced being annoyed by lack of the generality of some stdlib modules in the past.

The problem is that the Poly signature does not really solve the problem, what if my task type is:

type ('a, 'b) task 
(** The type for tasks taking a value of type ['a] and producing a value of type ['b]

improving things after the fact is difficult: users that hit a limitation typically don't tell us, and even when they do it is hard to make the change.

We have now shown it wouldn't be in this case.

• I find the use-cases for polymorphic queues proposed in the documentation reasonably convincing -- if abstract.

Personally not convinced :-) Am I going to create a priority queue for int tasks and another for string tasks ? No. Either you will use an 'a with a closed typed or an existential like:

type e_task = E_task : { task : 'a task; continue : 'a -> unit } 

In either case you are back to the Elt case. And if you are really into over-abstraction algorithmics you can represent can 'a task instance by a functor argument (sig type alpha type task = alpha task end) over the code you are trying to generalize and use Elt again.

I want to see a real use case, not an abstract one :-)

• I realized when writing the documentation that the polymorphic version could have compare : 'a t -> 'b t -> int, which clarifies that the comparison should not depend on the type parameter.

If OrderedPolyType really has to go in. That would be a good idea.

Summary: I am now in favor of either including both (Make){Min,Max} and (Make){Min,Max}Poly or just (Make){Min,Max}, which I understand is now @dbuenzli's preference. I think that both options are good and I am happy with whatever has the preference of the people doing the work.

Sorry I missed the summary. @gasche I think there is something that is not spelled out between our perspectives: the question is do we want to provide an easy way to create polymorphic queues with seperate priorities ?

If the answer is yes then my summary is as follows. In this case I would be in favor of not
having bare Make{Min,Max} so that reading the code conveys precisely what is being prioritized. We would have:

1. Make{Min,Max}Elt
2. Make{Min,Max}Priority
3. Make{Min,Max}Poly

1 or 1+2 would be fine with me. But I think we should avoid 1+2+3 or 1+3 for now.

If the answer is no then I think your:

1. Make{Min,Max}
2. Make{Min,Max}Poly

Makes sense, there's not need to spell out Elt because in either case it's always elements that are prioritized and with 2., with some mental gymnastics you can emulate polymorphic queues with separate priorities. In this case I am less against providing 1+2 now.

Having never felt the need for polymorphic queues I don't have a strong answer to this question. But if other people will also likely mostly use non-polymorphic queues, I agree @gasche's structure is perhaps more simple, regular and elegant.

Am I going to create a priority queue for int tasks and another for string tasks ?

I could for example model myself as having a TODO list of work-related tasks that I want to do, and also a TODO of leisure-related tasks that I want to do. Depending on my current state I will decide whether I want to work or have fun, and draw an element of one the two queues. Their descriptions have very different structure, so they have different types: work task queue vs. leisure task queue. But they both simply use float priorities or whatever. Certain days are holidays, where I normally work but also have the option to not work if I prefer; I draw 10 tasks from each queue and put them in a shared (work, leisure) Either.t task queue for the day.

Ah but on holidays I want to have different priorities between work and leisure…

Changing priorities during this trasition is possible with an interface such as map_into : from:'a t -> ('a -> 'b) -> into:'b t -> unit, which lets me convert a work task into a (work, leisure) Either.t task in a custom way. The only requirement imposed (which could of course be contested) is that the priority logic on 'a task does not depend on 'a -- that the priority logic of all three instances is the same. If the notion of priority itself is different between the instances, you need to use the monomorphic functor instead.

If the notion of priority itself is different between the instances, you need to use the monomorphic functor instead.

Yes that was my point. In any case let's leave it there :-) I'm generally unlikely to be convinced by these kind of abstract scenarios. I can't count the number of things I designed in the abstract to realize they were totally unfit in practice (in this particular case in a real program you would likely have your tasks under a single variant anyways, for UI purposes, search, serialization etc. and there would be little benefit in trying to type what you type above and a single monomorphic queue type would likely do equally well).

As I said I'm not against your proposal (perhaps without that task example which I don't find particularly enlightening) if people are ok with not giving a simple interface to create polymorphic queues; I think I am, I doubt there's a big need to do so and thus I feel the extra more expertful mind twisting is ok.