-
-
Save dbuenzli/22c177c7e4daaae389b1013f5344acd3 to your computer and use it in GitHub Desktop.
_b0 |
# Generated by brzo | |
S ./** | |
B /Users/dbuenzli/tmp/pqueue.mli/_b0/brzo/ocaml-doc/** | |
B /Users/dbuenzli/.opam/4.14.2+ocamlnat/lib/ocaml/** |
(**/**) | |
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 |
#!/bin/sh | |
rsync -a _b0/brzo/ocaml-doc/ erratique:erratique.ch/html-tmp/pqueue |
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 haveElt
suffixing andPoly
prefixing andElt
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:
- 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.
- 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.
- 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.
- 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.
- 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. - 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:
Make{Min,Max}Elt
Make{Min,Max}Priority
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:
Make{Min,Max}
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 forstring
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.
@dbuenzli can we maybe iterate on your proposal here?
I would suggest the following changes for your consideration:
module type Base := sig .. end
, so thatBase
is not exported in the resulting signature. Same with other modules that are not meant to be shown to users.Poly
prefix to name signatures that use a parametrized type of elements: BasePoly, BasePolyMin, BasePolyMax'a elt = priority * 'a
instance as a typical example.