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.

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

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

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].

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

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.

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.

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.

create has the same type as in Gen, but adding it here prevents a type-checker issue with nongeneralizable type variables.

Checks whether the provided element is there, using equality on elts.

iter must allow exceptions raised in f to escape, terminating the iteration cleanly. The same holds for all functions below taking an f.

fold t ~init ~f returns f (... f (f (f init e1) e2) e3 ...) en, where e1..en are the elements of t.

fold_result t ~init ~f is a short-circuiting version of fold that runs in the Result monad. If f returns an Error _, that value is returned without any additional invocations of f.

fold_until t ~init ~f ~finish is a short-circuiting version of fold. If f returns Stop _ the computation ceases and results in that value. If f returns Continue _, the fold will proceed. If f never returns Stop _, the final result is computed by finish.

Example:

  type maybe_negative =
    | Found_negative of int
    | All_nonnegative of { sum : int }

  (** [first_neg_or_sum list] returns the first negative number in [list], if any,
      otherwise returns the sum of the list. *)
  let first_neg_or_sum =
    List.fold_until ~init:0
      ~f:(fun sum x ->
        if x < 0
        then Stop (Found_negative x)
        else Continue (sum + x))
      ~finish:(fun sum -> All_nonnegative { sum })
  ;;

  let x = first_neg_or_sum [1; 2; 3; 4; 5]
  val x : maybe_negative = All_nonnegative {sum = 15}

  let y = first_neg_or_sum [1; 2; -3; 4; 5]
  val y : maybe_negative = Found_negative -3

Returns true if and only if there exists an element for which the provided function evaluates to true. This is a short-circuiting operation.

Returns true if and only if the provided function evaluates to true for all elements. This is a short-circuiting operation.

Returns the number of elements for which the provided function evaluates to true.

Returns the sum of f i for all i in the container.

Returns as an option the first element for which f evaluates to true.

Returns the first evaluation of f that returns Some, and returns None if there is no such element.

Returns a min (resp. max) element from the collection using the provided compare function. In case of a tie, the first element encountered while traversing the collection is returned. The implementation uses fold so it has the same complexity as fold. Returns None iff the collection is empty.

See Binary_search.binary_search in binary_search.ml

See Binary_search.binary_search_segmented in binary_search.ml