-
-
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 |
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.
I find the result much harder to use.
Elt
) and separate priorities with and polymorphic elements (Priority
). Some mental gymnastics is needed to get to this.Int
,Float
, etc.).The problem is that the
Poly
signature does not really solve the problem, what if my task type is:We have now shown it wouldn't be in this case.
Personally not convinced :-) Am I going to create a priority queue for
int
tasks and another forstring
tasks ? No. Either you will use an'a
with a closed typed or an existential like: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 useElt
again.I want to see a real use case, not an abstract one :-)
If
OrderedPolyType
really has to go in. That would be a good idea.