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

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.