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

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.