Module Core.Interval

Module for simple closed intervals over arbitrary types. Used by calling the Make functor with a type that satisfies Base.Comparable (for correctly ordering elements).

Note that the actual interface for intervals is in Interval_intf.Gen, following a Core pattern of defining an interface once in a Gen module, then reusing it across monomorphic (S) and polymorphic (S1, S2, ... SN) variants, where SN denotes a signature of N parameters. Here, S1 is included in this module because the signature of one 'a parameter is the default.

See the documentation of Interval.Make for a more detailed usage example.

Intervals using polymorphic compare

This part of the interface is for polymorphic intervals, which are well ordered by polymorphic compare. Using this with types that are not (like sets) will lead to crazy results.

type 'a t

This type t supports bin-io and sexp conversion by way of the [@@deriving bin_io, sexp] extensions, which inline the relevant function signatures (like bin_read_t and t_of_sexp).

include sig ... end
val bin_read_t : 'a Bin_prot.Read.reader ‑> 'a t Bin_prot.Read.reader
val __bin_read_t__ : 'a Bin_prot.Read.reader ‑> (int ‑> 'a t) Bin_prot.Read.reader
val bin_size_t : 'a Bin_prot.Size.sizer ‑> 'a t Bin_prot.Size.sizer
val bin_write_t : 'a Bin_prot.Write.writer ‑> 'a t Bin_prot.Write.writer
val bin_shape_t : Bin_prot.Shape.t ‑> Bin_prot.Shape.t
val t_of_sexp : (Sexplib.Sexp.t ‑> 'a) ‑> Sexplib.Sexp.t ‑> 'a t
val sexp_of_t : ('a ‑> Sexplib.Sexp.t) ‑> 'a t ‑> Sexplib.Sexp.t
type 'a bound_ = 'a
type 'a t
type 'a bound

bound is the type of points in the interval (and therefore of the bounds). bound is instantiated in two different ways below: in module type S as a monotype and in module type S1 as 'a.

val create : 'a bound ‑> 'a bound ‑> 'a t

create l u returns the interval with lower bound l and upper bound u, unless l > u, in which case it returns the empty interval.

val empty : 'a t
val intersect : 'a t ‑> 'a t ‑> 'a t
val is_empty : 'a t ‑> bool
val is_empty_or_singleton : 'a t ‑> bool
val bounds : 'a t ‑> ('a bound * 'a bound) option
val lbound : 'a t ‑> 'a bound option
val ubound : 'a t ‑> 'a bound option
val bounds_exn : 'a t ‑> 'a bound * 'a bound
val lbound_exn : 'a t ‑> 'a bound
val ubound_exn : 'a t ‑> 'a bound
val convex_hull : 'a t list ‑> 'a t

convex_hull ts returns an interval whose upper bound is the greatest upper bound of the intervals in the list, and whose lower bound is the least lower bound of the list.

Suppose you had three intervals a, b, and c:

             a:  (   )
             b:    (     )
             c:            ( )

          hull:  (           )

In this case the hull goes from lbound_exn a to ubound_exn c.

val contains : 'a t ‑> 'a bound ‑> bool
val compare_value : 'a t ‑> 'a bound ‑> [ `Below | `Within | `Above | `Interval_is_empty ]
val bound : 'a t ‑> 'a bound ‑> 'a bound option

bound t x returns None iff is_empty t. If bounds t = Some (a, b), then bound returns Some y where y is the element of t closest to x. I.e.:

        y = a  if x < a
        y = x  if a <= x <= b
        y = b  if x > b
val is_superset : 'a t ‑> of_:'a t ‑> bool

is_superset i1 of_:i2 is whether i1 contains i2. The empty interval is contained in every interval.

val is_subset : 'a t ‑> of_:'a t ‑> bool
val map : 'a t ‑> f:('a bound ‑> 'b bound) ‑> 'b t

map t ~f returns create (f l) (f u) if bounds t = Some (l, u), and empty if t is empty. Note that if f l > f u, the result of map is empty, by the definition of create.

If you think of an interval as a set of points, rather than a pair of its bounds, then map is not the same as the usual mathematical notion of mapping f over that set. For example, map ~f:(fun x -> x * x) maps the interval [-1,1] to [1,1], not to [0,1].

val are_disjoint : 'a t list ‑> bool

are_disjoint ts returns true iff the intervals in ts are pairwise disjoint.

val are_disjoint_as_open_intervals : 'a t list ‑> bool

Returns true iff a given set of intervals would be disjoint if considered as open intervals, e.g., (3,4) and (4,5) would count as disjoint according to this function.

val list_intersect : 'a t list ‑> 'a t list ‑> 'a t list

Assuming that ilist1 and ilist2 are lists of disjoint intervals, list_intersect ilist1 ilist2 considers the intersection (intersect i1 i2) of every pair of intervals (i1, i2), with i1 drawn from ilist1 and i2 from ilist2, returning just the non-empty intersections. By construction these intervals will be disjoint, too. For example:

        let i = Interval.create;;
        list_intersect [i 4 7; i 9 15] [i 2 4; i 5 10; i 14 20];;
        [(4, 4), (5, 7), (9, 10), (14, 15)]

Raises an exception if either input list is non-disjoint.

val half_open_intervals_are_a_partition : 'a t list ‑> bool

Returns true if the intervals, when considered as half-open intervals, nestle up cleanly one to the next. I.e., if you sort the intervals by the lower bound, then the upper bound of the nth interval is equal to the lower bound of the n+1th interval. The intervals do not need to partition the entire space, they just need to partition their union.

module Set : sig ... end with type a bound := a bound_ with type a interval := a t

Type-specialized intervals

The module type S is used to define signatures for intervals over a specific type, like Interval.Ofday (whose bounds are Time.Ofday.t) or Interval.Float, whose bounds are floats.

Note the heavy use of destructive substitution, which removes the redefined type or module from the signature. This allows for clean type constraints in codebases, like Core's, where there are lots of types going by the same name (e.g., "t").

Signatures

The following signatures are used for specifying the types of the type-specialized intervals.

module type S1 = Interval_intf.S1
module type S : Interval_intf.S with type a poly_t := a t with type a poly_set := a Set.t
module type S_time : Interval_intf.S_time with type a poly_t := a t with type a poly_set := a Set.t

S_time is a signature that's used below to define the interfaces for Time and Time_ns without duplication.

Specialized interval types

module Ofday : S with type bound = Core__.Import.Time.Ofday.t
module Ofday_ns : S with type bound = Interval_intf.Time_ns.Ofday.t
module Time : S_time with module Time := Core__.Import.Time and type t = Core__.Import.Time.t t
module Time_ns : S_time with module Time := Interval_intf.Time_ns and type t = Interval_intf.Time_ns.t t
module Float : S with type bound = Core__.Import.Float.t
module Int : sig ... end
module Make : functor (Bound : sig ... end) -> S with type bound = Bound.t

Interval.Make is a functor that takes a type that you'd like to create intervals for and returns a module with functions over intervals of that type.

module Stable : sig ... end

Stable is used to build stable protocols. It ensures backwards compatibility by checking the sexp and bin-io representations of a given module. Here it's applied to the Float, Int, Time, Time_ns, and Ofday intervals.