Same as `Parsing symbol_start[28.41]` and `Parsing symbol_end[28.41]`, but return the offset of the string matching the nth item on the right-hand side of the rule, where n is the integer parameter to `rhs_start` and `rhs_end`. n is 1 for the leftmost item.

`val rhs_end : int -> int`

See `Parsing.rhs_start[28.41]`.

`val symbol_start_pos : unit -> Lexing_position`

Same as `symbol_start`, but return a `position` instead of an offset.

`val symbol_end_pos : unit -> Lexing_position`

Same as `symbol_end`, but return a `position` instead of an offset.

`val rhs_start_pos : int -> Lexing_position`

Same as `rhs_start`, but return a `position` instead of an offset.

`val rhs_end_pos : int -> Lexing_position`

Same as `rhs_end`, but return a `position` instead of an offset.

`val clear_parser : unit -> unit`

Empty the parser stack. Call it just after a parsing function has returned, to remove all pointers from the parser stack to structures that were built by semantic actions during parsing. This is optional, but lowers the memory requirements of the programs.

`exception Parse_error`

Raised when a parser encounters a syntax error. Can also be raised from the action part of a grammar rule, to initiate error recovery.

`val set_trace : bool -> bool`

Control debugging support for `ocamlyacc-generated` parsers. After `Parsing.set_trace true`, the pushdown automaton that executes the parsers prints a trace of its actions (reading a token, shifting a state, reducing by a rule) on standard output. `Parsing.set_trace false` turns this debugging trace off. The boolean returned is the previous state of the trace flag.

**Since: 3.11**

## 28.42 Module Printexc: Facilities for printing exceptions and inspecting current call stack.

`type t = exn = ..`

The type of exception values.

`val to_string : exn -> string`
List reversal.

val init : int -> (int -> 'a) -> 'a list
    init len f is [f 0; f 1; ...; f (len-1)], evaluated left to right.

Since: 4.06

Raises Invalid_argument if len < 0.

val append : 'a list -> 'a list -> 'a list
    append 10 11 appends 11 to 10. Same function as the infix operator @.

Since: 5.1 this function is tail-recursive.

val rev_append : 'a list -> 'a list -> 'a list
    rev_append 11 12 reverses 11 and concatenates it with 12. This is equivalent to
    (List.rev[29.33] 11) @ 12.

val concat : 'a list list -> 'a list
    Concatenate a list of lists. The elements of the argument are all concatenated together (in the
    same order) to give the result. Not tail-recursive (length of the argument + length of the
    longest sub-list).

val flatten : 'a list list -> 'a list
    Same as List.concat[29.33]. Not tail-recursive (length of the argument + length of the
    longest sub-list).

Comparison

val equal : ('a -> 'a -> bool) -> 'a list -> 'a list -> bool
    equal eq [a1; ...; an] [b1; ...; bm] holds when the two input lists have the same
    length, and for each pair of elements ai, bi at the same position we have eq ai bi.

Note: the eq function may be called even if the lists have different length. If you know your
equality function is costly, you may want to check List compares lengths[29.33] first.

Since: 4.12

val compare : ('a -> 'a -> int) -> 'a list -> 'a list -> int
    compare cmp [a1; ...; an] [b1; ...; bm] performs a lexicographic comparison of the
two input lists, using the same 'a -> 'a -> int interface as compare[28.2]:

* a1 :: 11 is smaller than a2 :: 12 (negative result) if a1 is smaller than a2, or if they
are equal (0 result) and 11 is smaller than 12

* the empty list [] is strictly smaller than non-empty lists

Note: the cmp function will be called even if the lists have different lengths.

Since: 4.12
`Printexc.to_string` `e` returns a string representation of the exception `e`.

`val to_string_default: exn -> string`

`Printexc.to_string_default` `e` returns a string representation of the exception `e`, ignoring all registered exception printers.

**Since:** 4.09

`val print: ('a -> 'b) -> 'a -> 'b`

`Printexc.print` `fn x` applies `fn` to `x` and returns the result. If the evaluation of `fn x` raises any exception, the name of the exception is printed on standard error output, and the exception is raised again. The typical use is to catch and report exceptions that escape a function application.

`val catch: ('a -> 'b) -> 'a -> 'b`

*Deprecated.* This function is no longer needed. `Printexc-catching` `fn x` is similar to `Printexc.print` [28.42], but aborts the program with exit code 2 after printing the uncaught exception. This function is deprecated: the runtime system is now able to print uncaught exceptions as precisely as `Printexc-catching` does. Moreover, calling `Printexc-catching` makes it harder to track the location of the exception using the debugger or the stack backtrace facility. So, do not use `Printexc-catching` in new code.

`val print_backtrace: out_channel -> unit`

`Printexc.print_backtrace` `oc` prints an exception backtrace on the output channel `oc`. The backtrace lists the program locations where the most-recently raised exception was raised and where it was propagated through function calls.

If the call is not inside an exception handler, the returned backtrace is unspecified. If the call is after some exception-catching code (before in the handler, or in a when-guard during the matching of the exception handler), the backtrace may correspond to a later exception than the handled one.

**Since:** 3.11

`val get_backtrace: unit -> string`

`Printexc.get_backtrace()` returns a string containing the same exception backtrace that `Printexc.print_backtrace` would print. Same restriction usage than `Printexc.print_backtrace` [28.42].

**Since:** 3.11

`val record_backtrace: bool -> unit`

`Printexc.record_backtrace` `b` turns recording of exception backtraces on (if `b = true`) or off (if `b = false`). Initially, backtraces are not recorded, unless the `b` flag is given to the program through the `OCAMLRUNPARAM` variable.

**Since:** 3.11

`val backtrace_status: unit -> bool`
Iterators

val iter : ('a -> unit) -> 'a list -> unit
iter f [a1; ...; an] applies function f in turn to [a1; ...; an]. It is equivalent to f
a1; f a2; ...; f an.

val iteri : (int -> 'a -> unit) -> 'a list -> unit
Same as List.iter[29.33], but the function is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

Since: 4.00

val map : ('a -> 'b) -> 'a list -> 'b list
map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...;
f an] with the results returned by f.

val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
Same as List.map[29.33], but the function is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

Since: 4.00

val rev_map : ('a -> 'b) -> 'a list -> 'b list
rev_map f l gives the same result as List.rev[29.33] (List.map[29.33] f l), but is more
efficient.

val filter_map : ('a -> 'b option) -> 'a list -> 'b list
filter_map f l applies f to every element of l, filters out the None elements and returns
the list of the arguments of the Some elements.

Since: 4.08

val concat_map : ('a -> 'b list) -> 'a list -> 'b list
concat_map f l gives the same result as List.concat[29.33] (List.map[29.33] f l).
Tail-recursive.

Since: 4.10

val fold_left_map :
('acc -> 'a -> 'acc * 'b) -> 'acc -> 'a list -> 'acc * 'b list
fold_left_map is a combination of fold_left and map that threads an accumulator through
calls to f.

Since: 4.11

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc
fold_left f init [b1; ...; bn] is f (... (f (f init b1) b2) ...) bn.

val fold_right : ('a -> 'acc -> 'acc) -> 'a list -> 'acc -> 'acc
fold_right f [a1; ...; an] init is f a1 (f a2 (... (f an init) ...)). Not
tail-recursive.
`Printexc.backtrace_status()` returns `true` if exception backtraces are currently recorded, `false` if not.

**Since: 3.11**

`val register_printers : (exn -> string option) -> unit`

`Printexc.register_printers fn` registers `fn` as an exception printer. The printer should return `None` or raise an exception if it does not know how to convert the passed exception, and `Some s` with `s` the resulting string if it can convert the passed exception. Exceptions raised by the printer are ignored.

When converting an exception into a string, the printers will be invoked in the reverse order of their registrations, until a printer returns a `Some s` value (if no such printer exists, the runtime will use a generic printer).

When using this mechanism, one should be aware that an exception backtrace is attached to the thread that saw it raised, rather than to the exception itself. Practically, it means that the code related to `fn` should not use the backtrace if it has itself raised an exception before.

**Since: 3.11.2**

`val use_printers : exn -> string option`

`Printexc.use_printers e` returns `None` if there are no registered printers and `Some s` with else as the resulting string otherwise.

**Since: 4.09**

## Raw backtraces

`type raw_backtrace`

The type `raw_backtrace` stores a backtrace in a low-level format, which can be converted to usable form using `raw_backtrace_entries` and `backtrace_slots_of_raw_entry` below.

Converting backtraces to `backtrace_slots` is slower than capturing the backtraces. If an application processes many backtraces, it can be useful to use `raw_backtrace` to avoid or delay conversion.

Raw backtraces cannot be marshalled. If you need marshalling, you should use the array returned by the `backtrace_slots` function of the next section.

**Since: 4.01**

`type raw_backtrace_entry = private int`

A `raw_backtrace_entry` is an element of a `raw_backtrace`.

Each `raw_backtrace_entry` is an opaque integer, whose value is not stable between different programs, or even between different runs of the same binary.

A `raw_backtrace_entry` can be converted to a usable form using `backtrace_slots_of_raw_entry` below. Note that, due to inlining, a single `raw_backtrace_entry` may convert to several `backtrace_slots`. Since the values of a
## Iterators on two lists

val iter2: ('a -> 'b -> unit) -> 'a list -> 'b list -> unit
  iter2 f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an bn.
  Raises Invalid_argument if the two lists are determined to have different lengths.

val map2: ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
  map2 f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn].
  Raises Invalid_argument if the two lists are determined to have different lengths.

val rev_map2: ('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
  rev_map2 f 11 12 gives the same result as List.rev[29.33] (List.map2[29.33] f 11 12),
  but is more efficient.

val fold_left2:
  ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a list -> 'b list -> 'acc
  fold_left2 f init [a1; ...; an] [b1; ...; bn] is f (... (f (f init a1 b1) a2
  b2) ...) an bn.
  Raises Invalid_argument if the two lists are determined to have different lengths.

val fold_right2:
  ('a -> 'b -> 'acc -> 'acc) -> 'a list -> 'b list -> 'acc -> 'acc
  fold_right2 f [a1; ...; an] [b1; ...; bn] init is f a1 b1 (f a2 b2 (... (f an
  bn init) ...)).
  Raises Invalid_argument if the two lists are determined to have different lengths. Not
  tail-recursive.

## List scanning

val for_all: ('a -> bool) -> 'a list -> bool
  for_all f [a1; ...; an] checks if all elements of the list satisfy the predicate f. That is,
  it returns (f a1) && (f a2) && ... && (f an) for a non-empty list and true if the list is
  empty.

val exists: ('a -> bool) -> 'a list -> bool
  exists f [a1; ...; an] checks if at least one element of the list satisfies the predicate f.
  That is, it returns (f a1) || (f a2) || ... || (f an) for a non-empty list and false if
  the list is empty.

val for_all2: ('a -> 'b -> bool) -> 'a list -> 'b list -> bool
  Same as List.for_all[29.33], but for a two-argument predicate.
  Raises Invalid_argument if the two lists are determined to have different lengths.
`raw_backtrace_entry` are not stable, they cannot be marshalled. If they are to be converted, the conversion must be done by the process that generated them.

Again due to inlining, there may be multiple distinct `raw_backtrace_entry` values that convert to equal `backtrace_slots`. However, if two `raw_backtrace_entries` are equal as integers, then they represent the same `backtrace_slots`.

**Since: 4.12**

`val raw_backtrace_entries : raw_backtrace -> raw_backtrace_entry array`

**Since: 4.12**

`val get_raw_backtrace : unit -> raw_backtrace`

`Printexc.get_raw_backtrace()` returns the same exception backtrace that `Printexc.print_backtrace` would print, but in a raw format. Same restriction usage than `Printexc.print_backtrace[28.42]`.

**Since: 4.01**

`val print_raw_backtrace : out_channel -> raw_backtrace -> unit`

Print a raw backtrace in the same format `Printexc.print_backtrace` uses.

**Since: 4.01**

`val raw_backtrace_to_string : raw_backtrace -> string`

Return a string from a raw backtrace, in the same format `Printexc.get_backtrace` uses.

**Since: 4.01**

`val raise_with_backtrace : exn -> raw_backtrace -> 'a`

Reraise the exception using the given `raw_backtrace` for the origin of the exception

**Since: 4.05**

## Current call stack

`val get_callstack : int -> raw_backtrace`

`Printexc.get_callstack` n returns a description of the top of the call stack on the current program point (for the current thread), with at most n entries. (Note: this function is not related to exceptions at all, despite being part of the `Printexc` module.)

**Since: 4.01**

## Uncaught exceptions

`val default_uncaught_exception_handler : exn -> raw_backtrace -> unit`

`Printexc.default_uncaught_exception_handler` prints the exception and backtrace on standard error output.

**Since: 4.11**
val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool

Same as `List.exists[29.33]`, but for a two-argument predicate.

**Raises** `Invalid_argument` if the two lists are determined to have different lengths.

val mem : 'a -> 'a list -> bool

`mem` a set is true if and only if `a` is equal to an element of `set`.

val memq : 'a -> 'a list -> bool

Same as `List.mem[29.33]`, but uses physical equality instead of structural equality to compare list elements.

## List searching

val find : ('a -> bool) -> 'a list -> 'a

`find` f 1 returns the first element of the list 1 that satisfies the predicate `f`.

**Raises** `Not_found` if there is no value that satisfies `f` in the list 1.

val find_opt : ('a -> bool) -> 'a list -> 'a option

`find` f 1 returns the first element of the list 1 that satisfies the predicate `f`. Returns `None` if there is no value that satisfies `f` in the list 1.

**Since:** 4.05

val find_index : ('a -> bool) -> 'a list -> int option

`find_index` f `xs` returns `Some i`, where `i` is the index of the first element of the list `xs` that satisfies `f x`, if there is such an element.

It returns `None` if there is no such element.

**Since:** 5.1

val find_map : ('a -> 'b option) -> 'a list -> 'b option

`find_map` f 1 applies `f` to the elements of 1 in order, and returns the first result of the form `Some v`, or `None` if none exist.

**Since:** 4.10

val find_mapi : (int -> 'a -> 'b option) -> 'a list -> 'b option

Same as `find_map`, but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

**Since:** 5.1

val filter : ('a -> bool) -> 'a list -> 'a list

`filter` f 1 returns all the elements of the list 1 that satisfy the predicate `f`. The order of the elements in the input list is preserved.
```hkl
val set_uncaught_exception_handler : (exn -> raw_backtrace -> unit) -> unit
```

`Printexc.set_uncaught_exception_handler fn` registers `fn` as the handler for uncaught exceptions. The default handler is `Printexc.default_uncaught_exception_handler[28.42]`.

Note that when `fn` is called all the functions registered with `at_exit[27.2]` have already been called. Because of this you must make sure any output channel `fn` writes on is flushed.

Also note that exceptions raised by user code in the interactive toplevel are not passed to this function as they are caught by the toplevel itself.

If `fn` raises an exception, both the exceptions passed to `fn` and raised by `fn` will be printed with their respective backtrace.

**Since: 4.02**

## Manipulation of backtrace information

These functions are used to traverse the slots of a raw backtrace and extract information from them in a programmer-friendly format.

### `type backtrace_slots`

The abstract type `backtrace_slots` represents a single slot of a backtrace.

**Since: 4.02**

### `val backtrace_slots: raw_backtrace -> backtrace_slots` array option

Returns the slots of a raw backtrace, or `None` if none of them contain useful information.

In the return array, the slot at index 0 corresponds to the most recent function call, raise, or primitive `get_backtrace` call in the trace.

Some possible reasons for returning `None` are as follows:

* none of the slots in the trace come from modules compiled with debug information (`-g`)

* the program is a bytecode program that has not been linked with debug information enabled (`ocamlc -g`)

**Since: 4.02**

### `val backtrace_slots_of_raw_entry` :

`raw_backtrace_entry -> backtrace_slots` array option

Returns the slots of a single raw backtrace entry, or `None` if this entry lacks debug information.

Slots are returned in the same order as `backtrace_slots`: the slot at index 0 is the most recent call, raise, or primitive, and subsequent slots represent callers.

**Since: 4.12**

```hkl
type location =
  { filename : string ;
    line_number : int ;
```
val find_all : ('a -> bool) -> 'a list -> 'a list
find_all is another name for List.filter[29.33].

val filteri : (int -> 'a -> bool) -> 'a list -> 'a list
Same as List.filter[29.33], but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

Since: 4.11

List manipulation

val take : int -> 'a list -> 'a list

take n l returns the prefix of l of length n, or a copy of l if n > length l. This is the
empty list if n is negative.

**Warning.** In version 5.3 only, this function raises Invalid_argument for negative n values.

Since: 5.3

val drop : int -> 'a list -> 'a list

drop n l returns the suffix of l after n elements, or [] if n > length l. This is l if n is
negative.

**Warning.** In version 5.3 only, this function raises Invalid_argument for negative n values.

Since: 5.3

val takewhile : ('a -> bool) -> 'a list -> 'a list

takewhile p l is the longest (possibly empty) prefix of l containing only elements that
satisfy p.

Since: 5.3

val dropwhile : ('a -> bool) -> 'a list -> 'a list

dropwhile p l is the longest (possibly empty) suffix of l starting at the first element that
does not satisfy p.

Since: 5.3

val partition : ('a -> bool) -> 'a list -> 'a list * 'a list

partition f l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l
that satisfy the predicate f, and l2 is the list of all the elements of l that do not satisfy f.
The order of the elements in the input list is preserved.

val partition_map : ('a -> ('b, 'c) Either.t) -> 'a list -> 'b list * 'c list
partition_map f l returns a pair of lists (l1, l2) such that, for each element x of the
input list l:

* if f x is Left y1, then y1 is in l1, and
```fortran
start_char : int ;
end_char : int ;
}
```

The type of location information found in backtraces. `start_char` and `end_char` are positions relative to the beginning of the line.

**Since: 4.02**

```fortran
module Slot :
```

```fortran
sig
```

```fortran
type t = Printexc.backtrace�om
```

```fortran
val is_Raise : t -+ bool
```

`is_Raise slot` is true when `slot` refers to a raising point in the code, and false when it comes from a simple function call.

**Since: 4.02**

```fortran
val is inline : t -+ bool
```

`is inline slot` is true when `slot` refers to a call that got inlined by the compiler, and false when it comes from any other context.

**Since: 4.04**

```fortran
val location : t -+ Printexc.location option
```

`location slot` returns the location information of the slot, if available, and `None` otherwise.

Some possible reasons for failing to return a location are as follow:

* the slot corresponds to a compiler-inserted raise

* the slot corresponds to a part of the program that has not been compiled with debug information (`-g`)

**Since: 4.02**

```fortran
val name : t -+ string option
```

`name slot` returns the name of the function or definition enclosing the location referred to by the slot.

`name slot` returns `None` if the name is unavailable, which may happen for the same reasons as `location` returning `None`.

**Since: 4.11**

```fortran
val format : int -> t -> string option
```

`format pos slot` returns the string representation of `slot` as `raw_backtrace_to_string` would format it, assuming it is the `pos`-th element of the backtrace: the 0-th element is pretty-printed differently than the others.

Whole-backtrace printing functions also skip some uninformative slots; in that case, `format pos slot` returns `None`.

**Since: 4.02**
* if `f x` is Right `y2`, then `y2` is in `12`.

The output elements are included in `11` and `12` in the same relative order as the corresponding input elements in `1`.

In particular, `partition_map` (`fun x -> if f x then Left x else Right x) 1` is equivalent to `partition f 1`.

**Since:** 4.12

## Association lists

`val assoc : 'a -> ('a * 'b) list -> 'b`

`assoc a 1` returns the value associated with key `a` in the list of pairs `1`. That is, `assoc a [ ... ; (a,b) ; ... ] = b` if `(a,b)` is the leftmost binding of `a` in list `1`.

**Raises:** `Not_found` if there is no value associated with `a` in the list `1`.

`val assoc_opt : 'a -> ('a * 'b) list -> 'b option`

`assoc_opt a 1` returns the value associated with key `a` in the list of pairs `1`. That is, `assoc_opt a [ ... ; (a,b) ; ... ] = Some b` if `(a,b)` is the leftmost binding of `a` in list `1`. Returns `None` if there is no value associated with `a` in the list `1`.

**Since:** 4.05

`val assq : 'a -> ('a * 'b) list -> 'b`

Same as `List.assoc[29.33]`, but uses physical equality instead of structural equality to compare keys.

`val assq_opt : 'a -> ('a * 'b) list -> 'b option`

Same as `List.assoc_opt[29.33]`, but uses physical equality instead of structural equality to compare keys.

**Since:** 4.05

`val mem assoc : 'a -> ('a * 'b) list -> bool`

Same as `List.assoc[29.33]`, but simply return `true` if a binding exists, and `false` if no bindings exist for the given key.

`val mem_assq : 'a -> ('a * 'b) list -> bool`

Same as `List.mem assoc[29.33]`, but uses physical equality instead of structural equality to compare keys.

`val remove assoc : 'a -> ('a * 'b) list -> ('a * 'b) list`

`remove assoc a 1` returns the list of pairs `1` without the first pair with key `a`, if any. Not tail-recursive.

`val remove_assq : 'a -> ('a * 'b) list -> ('a * 'b) list`

Same as `List.remove assoc[29.33]`, but uses physical equality instead of structural equality to compare keys. Not tail-recursive.
end

Since: 4.02

## Raw backtrace slots

type raw_backtrace_slots

This type is used to iterate over the slots of a `raw_backtrace`. For most purposes, `backtrace_slots_of_raw_entry` is easier to use.

Like `raw_backtrace_entry`, values of this type are process-specific and must absolutely not be marshalled, and are unsafe to use for this reason (marshalling them may not fail, but un-marshalling and using the result will result in undefined behavior).

Elements of this type can still be compared and hashed: when two elements are equal, then they represent the same source location (the converse is not necessarily true in presence of inlining, for example).

Since: 4.02

val raw_backtrace_length : raw_backtrace -> int

`raw_backtrace_length` bckt returns the number of slots in the backtrace bckt.

Since: 4.02

val get_raw_backtrace_slots : raw_backtrace -> int -> raw_backtrace_slots

`get_raw_backtrace_slots` bckt pos returns the slot in position pos in the backtrace bckt.

Since: 4.02

val convert_raw_backtrace_slots : raw_backtrace_slots -> backtrace_slots

Extracts the user-friendly `backtrace_slots` from a low-level `raw_backtrace_slots`.

Since: 4.02

val get_raw_backtrace_next_slots :  
    raw_backtrace_slots -> raw_backtrace_slots option  
    get_raw_backtrace_next_slots slot returns the next slot inlined, if any.

Sample code to iterate over all frames (inlined and non-inlined):

(* Iterate over inlined frames *)
let rec iter_raw_backtrace_slots f slot =
    f slot;
match get_raw_backtrace_next_slots slot with
| None -> ()
| Some slot' -> iter_raw_backtrace_slots f slot'

(* Iterate over stack frames *)
## Lists of pairs

`val split : ('a * 'b) list -> 'a list * 'b list`

Transform a list of pairs into a pair of lists: `split [(a1,b1); ...; (an,bn)]` is `[ [a1; ...; an], [b1; ...; bn] ]`. Not tail-recursive.

`val combine : 'a list -> 'b list -> ('a * 'b) list`

Transform a pair of lists into a list of pairs: `combine [a1; ...; an] [b1; ...; bn]` is `[ (a1,b1); ...; (an,bn) ]`.

**Raises** `Invalid_argument` if the two lists have different lengths. Not tail-recursive.

## Sorting

`val sort : ('a -> 'a -> int) -> 'a list -> 'a list`

Sort a list in increasing order according to a comparison function. The comparison function must return 0 if its arguments compare as equal, a positive integer if the first is greater, and a negative integer if the first is smaller (see Array.sort for a complete specification). For example, `compare[28.2]` is a suitable comparison function. The resulting list is sorted in increasing order. `List.sort[29.33]` is guaranteed to run in constant heap space (in addition to the size of the result list) and logarithmic stack space.

The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.

`val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list`

Same as `List.sort[29.33]`, but the sorting algorithm is guaranteed to be stable (i.e. elements that compare equal are kept in their original order).

The current implementation uses Merge Sort. It runs in constant heap space and logarithmic stack space.

`val fast_sort : ('a -> 'a -> int) -> 'a list -> 'a list`

Same as `List.sort[29.33]` or `List.stable_sort[29.33]`, whichever is faster on typical input.

`val sort_uniq : ('a -> 'a -> int) -> 'a list -> 'a list`

Same as `List.sort[29.33]`, but also remove duplicates: if multiple elements compare equal, keep only the first.

**Before 5.4** the element kept was not necessarily the first one.

**Since:** 4.02 (4.03 in `ListLabels`)

`val merge : ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list`

Merge two lists: Assuming that 11 and 12 are sorted according to the comparison function `cmp`, `merge cmp 11 12` will return a sorted list containing all the elements of 11 and 12. If several elements compare equal, the elements of 11 will be before the elements of 12. Not tail-recursive (sum of the lengths of the arguments).
```h
let iter_raw_backtrace f bt =
    for i = 0 to raw_backtrace_length bt - 1 do
        iter_raw_backtrace�_slots f (get_raw_backtrace_slots bt i)
    done
```

**Since: 4.04**

## Exception slots

`val exn_slots_id: exn -> int`

`Printexc.exn_slots_id` returns an integer which uniquely identifies the constructor used to create the exception value `exn` (in the current runtime).

**Since: 4.02**

`val exn_slots_name: exn -> string`

`Printexc.exn_slots_name` exn returns the internal name of the constructor used to create the exception value `exn`.

**Since: 4.02**

## 28.43 Module fprintf: Formatted output functions.

`val fprintf: out_channel -> ('a, out_channel, unit) format -> 'a`

`fprintf outchan format arg1 ... argN` formats the arguments `arg1` to `argN` according to the format string `format`, and outputs the resulting string on the channel `outchan`.

The format string is a character string which contains two types of objects: plain characters, which are simply copied to the output channel, and conversion specifications, each of which causes conversion and printing of arguments.

Conversion specifications have the following form:

`% [flags] [width] [.precision] type`

In short, a conversion specification consists in the `%` character, followed by optional modifiers and a type which is made of one or two characters.

The types and their meanings are:

* `d`, `i`: convert an integer argument to signed decimal. The flag `#` adds underscores to large values for readability.

* `u`, `n`, `l`, `L`, or `N`: convert an integer argument to unsigned decimal. Warning: `n`, `l`, `L`, and `N` are used for `scanf`, and should not be used for `printf`. The flag `#` adds underscores to large values for readability.
## Lists and Sequences

val to_seq : 'a list -> 'a Seq.t
Iterate on the list.

**Since:** 4.07

val of_seq : 'a Seq.t -> 'a list
Create a list from a sequence.

**Since:** 4.07

# 29.34 Module ListLabels : List operations.

Some functions are flagged as not tail-recursive. A tail-recursive function uses constant stack space, while a non-tail-recursive function uses stack space proportional to the length of its list argument, which can be a problem with very long lists. When the function takes several list arguments, an approximate formula giving stack usage (in some unspecified constant unit) is shown in parentheses.

The above considerations can usually be ignored if your lists are not longer than about 10000 elements.

The labeled version of this module can be used as described in the StdLabels[29.57] module.

type 'a t = 'a list =
| []
| (:) of 'a * 'a list
An alias for the type of lists.

val length : 'a list -> int
Return the length (number of elements) of the given list.

val compare_lengths : 'a list -> 'b list -> int
Compare the lengths of two lists. compare_lengths 11 12 is equivalent to compare (length 11) (length 12), except that the computation stops after reaching the end of the shortest list.

**Since:** 4.05

val compare_length_with : 'a list -> len:int -> int
Compare the length of a list to an integer. compare_length_with 1 len is equivalent to compare (length 1) len, except that the computation stops after at most len iterations on the list.

**Since:** 4.05

val is_empty : 'a list -> bool
* x: convert an integer argument to unsigned hexadecimal, using lowercase letters. The flag # adds a 0x prefix to non zero values.

* X: convert an integer argument to unsigned hexadecimal, using uppercase letters. The flag # adds a 0X prefix to non zero values.

* o: convert an integer argument to unsigned octal. The flag # adds a 0 prefix to non zero values.

* s: insert a string argument.

* S: convert a string argument to OCaml syntax (double quotes, escapes).

* c: insert a character argument.

* C: convert a character argument to OCaml syntax (single quotes, escapes).

* f: convert a floating-point argument to decimal notation, in the style dddd.ddd.

* F: convert a floating-point argument to OCaml syntax (dddd. or dddd.ddd or d.ddd e+-dd). Converts to hexadecimal with the # flag (see h).

* e or E: convert a floating-point argument to decimal notation, in the style d.ddd e+-dd (mantissa and exponent).

* g or G: convert a floating-point argument to decimal notation, in style f or e, E (whichever is more compact). Moreover, any trailing zeros are removed from the fractional part of the result and the decimal-point character is removed if there is no fractional part remaining.

* h or H: convert a floating-point argument to hexadecimal notation, in the style 0x.hhhh p+-dd (hexadecimal mantissa, exponent in decimal and denotes a power of 2).

* B: convert a boolean argument to the string true or false

* b: convert a boolean argument (deprecated; do not use in new programs).

* ld, li, lu, lx, lX, lo: convert an int32 argument to the format specified by the second letter (decimal, hexadecimal, etc).

* nd, ni, nu, nx, nX, no: convert a nativeint argument to the format specified by the second letter.

* Ld, Li, Lu, Lx, LX, Lo: convert an int64 argument to the format specified by the second letter.

* a: user-defined printer. Take two arguments and apply the first one to outchan (the current output channel) and to the second argument. The first argument must therefore have type out_channel -> 'b -> unit and the second 'b. The output produced by the function is inserted in the output of fprintf at the current point.

* t: same as %a, but take only one argument (with type out_channel -> unit) and apply it to outchan.

* { fmt %}: convert a format string argument to its type digest. The argument must have the same type as the internal format string fmt.

* ( fmt %): format string substitution. Take a format string argument and substitute it to the internal format string fmt to print following arguments. The argument must have the same type as the internal format string fmt.
`is_empty` 1 is true if and only if 1 has no elements. It is equivalent to
`compare_length_with 1 0 = 0`.

Since: 5.1

val cons : 'a -> 'a list -> 'a list

cons x xs is x :: xs

Since: 4.05

val singleton : 'a -> 'a list
singleton x returns the one-element list [x].

Since: 5.4

val hd : 'a list -> 'a

Return the first element of the given list.

Raises Failure if the list is empty.

val tl : 'a list -> 'a list

Return the given list without its first element.

Raises Failure if the list is empty.

val nth : 'a list -> int -> 'a

Return the n-th element of the given list. The first element (head of the list) is at position 0.

Raises

* Failure if the list is too short.

* Invalid_argument if n is negative.

val nth_opt : 'a list -> int -> 'a option

Return the n-th element of the given list. The first element (head of the list) is at position 0.
Return None if the list is too short.

Since: 4.05

Raises Invalid_argument if n is negative.

val rev : 'a list -> 'a list

List reversal.

val init : len:int -> f:(int -> 'a) -> 'a list

init ~len ~f is [f 0; f 1; ...; f (len-1)], evaluated left to right.

Since: 4.06

Raises Invalid_argument if len < 0.
* `!`: take no argument and flush the output.

* `%`: take no argument and output one `%` character.

* `@`: take no argument and output one `@` character.

* `,`: take no argument and output nothing: a no-op delimiter for conversion specifications.

The optional `flags` are:

* `-`: left-justify the output (default is right justification).

* `0`: for numerical conversions, pad with zeroes instead of spaces.

* `+`: for signed numerical conversions, prefix number with a `+` sign if positive.

* `space`: for signed numerical conversions, prefix number with a space if positive.

* `#`: request an alternate formatting style for the integer types and the floating-point type `F`.

The optional `width` is an integer indicating the minimal width of the result. For instance, `%6d` prints an integer, prefixing it with spaces to fill at least 6 characters.

The optional `precision` is a dot `.` followed by an integer indicating how many digits follow the decimal point in the `%f`, `%e`, `%E`, `%h`, and `%H` conversions or the maximum number of significant digits to appear for the `%F`, `%g` and `%G` conversions. For instance, `%.4f` prints a `float` with 4 fractional digits.

The integer in a `width` or `precision` can also be specified as `*`, in which case an extra integer argument is taken to specify the corresponding `width` or `precision`. This integer argument precedes immediately the argument to print. For instance, `%.*f` prints a `float` with as many fractional digits as the value of the argument given before the float.

`val printf`: (`'a, out_channel, unit`), `format -> 'a'`
Same as `Format.fprintf[28.43]`, but output on `stdout`.

`val eprintf`: (`'a, out_channel, unit`), `format -> 'a'`
Same as `Format.fprintf[28.43]`, but output on `stderr`.

`val sprintf`: (`'a, unit, string'`), `format -> 'a'`
Same as `Format.fprintf[28.43]`, but instead of printing on an output channel, return a string containing the result of formatting the arguments.

`val bprintf`: `Buffer.t -> ('a, Buffer.t, unit)`), `format -> 'a'`
Same as `Format.fprintf[28.43]`, but instead of printing on an output channel, append the formatted arguments to the given extensible buffer (see module `Buffer` [28.7]).

`val ifprintf`: `'b -> ('a, 'b, 'c, unit)`), `format4 -> 'a'`
Same as `Format.fprintf[28.43]`, but does not print anything. Useful to ignore some material when conditionally printing.

**Since: 3.10**
val append : 'a list -> 'a list -> 'a list
append 10 11 appends 11 to 10. Same function as the infix operator @.

Since: 5.1 this function is tail-recursive.

val rev_append : 'a list -> 'a list -> 'a list
rev_append 11 12 reverses 11 and concatenates it with 12. This is equivalent to
(ListLabels.rev[29.34] 11) @ 12.

val concat : 'a list list -> 'a list
Concatenate a list of lists. The elements of the argument are all concatenated together (in the
same order) to give the result. Not tail-recursive (length of the argument + length of the
longest sub-list).

val flatten : 'a list list -> 'a list
Same as ListLabels.concat[29.34]. Not tail-recursive (length of the argument + length of
the longest sub-list).

Comparison

val equal : eq:('a -> 'a -> bool) -> 'a list -> 'a list -> bool
equal eq [a1; ...; an] [b1; ..; bm] holds when the two input lists have the same
length, and for each pair of elements ai, bi at the same position we have eq ai bi.

Note: the eq function may be called even if the lists have different length. If you know your
equality function is costly, you may want to check ListLabels compares lengths[29.34] first.

Since: 4.12

val compare : cmp:('a -> 'a -> int) -> 'a list -> 'a list -> int
compare cmp [a1; ...; an] [b1; ...; bm] performs a lexicographic comparison of the
two input lists, using the same 'a -> 'a -> int interface as compare[28.2]:

* a1 :: 11 is smaller than a2 :: 12 (negative result) if a1 is smaller than a2, or if they are equal (0 result) and 11 is smaller than 12

* the empty list [] is strictly smaller than non-empty lists

Note: the cmp function will be called even if the lists have different lengths.

Since: 4.12
`val ibprintf: Buffer.t -> ('a, Buffer.t, unit) format -> 'a`

Same as `Formatf.bprintf[28.43]`, but does not print anything. Useful to ignore some material when conditionally printing.

**Since: 4.11**

Formatted output functions with continuations.

`val kfprintf: (out_channel -> 'd) ->`

`out_channel -> ('a, out_channel, unit, 'd) format4 -> 'a`

Same as `fprintf`, but instead of returning immediately, passes the out channel to its first argument at the end of printing.

**Since: 3.09**

`val ikfprintf: ('b -> 'd) -> 'b -> ('a, 'b, 'c, 'd) format4 -> 'a`

Same as `kfprintf` above, but does not print anything. Useful to ignore some material when conditionally printing.

**Since: 4.01**

`val ksprintf: (string -> 'd) -> ('a, unit, string, 'd) format4 -> 'a`

Same as `sprintf` above, but instead of returning the string, passes it to the first argument.

**Since: 3.09**

`val kbprintf: (Buffer.t -> 'd) ->`

`Buffer.t -> ('a, Buffer.t, unit, 'd) format4 -> 'a`

Same as `bprintf`, but instead of returning immediately, passes the buffer to its first argument at the end of printing.

**Since: 3.10**

`val ikbprintf: (Buffer.t -> 'd) ->`

`Buffer.t -> ('a, Buffer.t, unit, 'd) format4 -> 'a`

Same as `kbprintf` above, but does not print anything. Useful to ignore some material when conditionally printing.

**Since: 4.11**

Deprecated

`val kprintf: (string -> 'b) -> ('a, unit, string, 'b) format4 -> 'a`

*Deprecated.* Use `Formatf.ksprintf` instead. A deprecated synonym for `ksprintf`.
Iterators

val iter : f:('a -> unit) -> 'a list -> unit
iter ~f [a1; ...; an] applies function f in turn to [a1; ...; an]. It is equivalent to f
a1; f a2; ...; f an.

val iteri : f:(int -> 'a -> unit) -> 'a list -> unit
Same as ListLabels.iter[29.34], but the function is applied to the index of the element as
first argument (counting from 0), and the element itself as second argument.

Since: 4.00

val map : f:('a -> 'b) -> 'a list -> 'b list
map ~f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...;
f an] with the results returned by f.

val mapi : f:(int -> 'a -> 'b) -> 'a list -> 'b list
Same as ListLabels.map[29.34], but the function is applied to the index of the element as
first argument (counting from 0), and the element itself as second argument.

Since: 4.00

val rev_map : f:('a -> 'b) -> 'a list -> 'b list
rev_map ~f l gives the same result as ListLabels.rev[29.34] (ListLabels.map[29.34] f
l), but is more efficient.

val filter_map : f:('a -> 'b option) -> 'a list -> 'b list
filter_map ~f l applies f to every element of l, filters out the None elements and returns
the list of the arguments of the Some elements.

Since: 4.08

val concat_map : f:('a -> 'b list) -> 'a list -> 'b list
concat_map ~f l gives the same result as ListLabels.concat[29.34]
(ListLabels.map[29.34] f l). Tail-recursive.

Since: 4.10

val fold_left_map :
f:('acc -> 'a -> 'acc * 'b) -> init:'acc -> 'a list -> 'acc * 'b list
fold_left_map is a combination of fold_left and map that threads an accumulator through
calls to f.

Since: 4.11

val fold_left : f:('acc -> 'a -> 'acc) -> init:'acc -> 'a list -> 'acc
fold_left ~f ~init [b1; ...; bn] is f (... (f (init b1) b2) ...) bn.

val fold_right : f:('a -> 'acc -> 'acc) -> 'a list -> init:'acc -> 'acc
fold_right ~f [a1; ...; an] ~init is f a1 (f a2 (... (f an init) ...)). Not
tail-recursive.
## 28.44 Module Queue: First-in first-out queues.

This module implements queues (FIFOs), with in-place modification. See the example section [28.44] below.

**Alert unsynchronized_access.** Unsynchronized accesses to queues are a programming error.

### Unsynchronized accesses

Unsynchronized accesses to a queue may lead to an invalid queue state. Thus, concurrent accesses to queues must be synchronized (for instance with a `Mutex.t[28.36]`).

```hndoc
type !'a t
```

The type of queues containing elements of type `'a`.

**exception Empty**

Raised when `Queue.take[28.44]` or `Queue peek[28.44]` is applied to an empty queue.

```hndoc
val create : unit -> 'a t
```

Return a new queue, initially empty.

```hndoc
val add : 'a -> 'a t -> unit
```

`add x q` adds the element `x` at the end of the queue `q`.

```hndoc
val push : 'a -> 'a t -> unit
```

`push` is a synonym for `add`.

```hndoc
val take : 'a t -> 'a
```

`take q` removes and returns the first element in queue `q`, or raises `Queue.Empty[28.44]` if the queue is empty.

```hndoc
val take_opt : 'a t -> 'a option
```

`take_opt q` removes and returns the first element in queue `q`, or returns `None` if the queue is empty.

**Since: 4.08**

```hndoc
val pop : 'a t -> 'a
```

`pop` is a synonym for `take`.

```hndoc
val peek : 'a t -> 'a
```

`peek q` returns the first element in queue `q`, without removing it from the queue, or raises `Queue.Empty[28.44]` if the queue is empty.

```hndoc
val peek_opt : 'a t -> 'a option
```

`peek_opt q` returns the first element in queue `q`, without removing it from the queue, or returns `None` if the queue is empty.

**Since: 4.08**
## Iterators on two lists

val iter2 : f:('a -> 'b -> unit) -> 'a list -> 'b list -> unit
iter2 ~f [a1; ...; an] [b1; ...; bn] calls in turn f a1 b1; ...; f an bn.
**Raises** Invalid_argument if the two lists are determined to have different lengths.

val map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
map2 ~f [a1; ...; an] [b1; ...; bn] is [f a1 b1; ...; f an bn].
**Raises** Invalid_argument if the two lists are determined to have different lengths.

val rev_map2 : f:('a -> 'b -> 'c) -> 'a list -> 'b list -> 'c list
rev_map2 ~f 11 12 gives the same result as ListLabels.rev[29.34]
(ListLabels.map2[29.34] f 11 12), but is more efficient.

val fold_left2 :
f:('acc -> 'a -> 'b -> 'acc) -> init:'acc -> 'a list -> 'b list -> 'acc
fold_left2 ~f ~init [a1; ...; an] [b1; ...; bn] is f (... (f (f init a1 b1) a2
b2) ...) an bn.
**Raises** Invalid_argument if the two lists are determined to have different lengths.

val fold_right2 :
f:('a -> 'b -> 'acc -> 'acc) -> 'a list -> 'b list -> init:'acc -> 'acc
fold_right2 ~f [a1; ...; an] [b1; ...; bn] ~init is f a1 b1 (f a2 b2 (... (f
an bn init) ...)).
**Raises** Invalid_argument if the two lists are determined to have different lengths. Not
tail-recursive.

## List scanning

val for_all : f:('a -> bool) -> 'a list -> bool
for_all ~f [a1; ...; an] checks if all elements of the list satisfy the predicate f. That is,
it returns (f a1) && (f a2) && ... && (f an) for a non-empty list and true if the list is
empty.

val exists : f:('a -> bool) -> 'a list -> bool
exists ~f [a1; ...; an] checks if at least one element of the list satisfies the predicate f.
That is, it returns (f a1) || (f a2) || ... || (f an) for a non-empty list and false if
the list is empty.

val for_all2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool
Same as ListLabels.for_all[29.34], but for a two-argument predicate.
**Raises** Invalid_argument if the two lists are determined to have different lengths.
val top : 'a t -> 'a
top is a synonym for peek.

val clear : 'a t -> unit
Discard all elements from a queue.

val copy : 'a t -> 'a t
Return a copy of the given queue.

val is_empty : 'a t -> bool
Return true if the given queue is empty, false otherwise.

val length : 'a t -> int
Return the number of elements in a queue.

val iter : ('a -> unit) -> 'a t -> unit
iter f q applies f in turn to all elements of q, from the least recently entered to the most
recently entered. The queue itself is unchanged.

val fold : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc
fold f accu q is equivalent to List.fold_left f accu l, where l is the list of q's
elements. The queue remains unchanged.

val transfer : 'a t -> 'a t -> unit
transfer q1 q2 adds all of q1's elements at the end of the queue q2, then clears q1. It is
equivalent to the sequence iter (fun x -> add x q2) q1; clear q1, but runs in constant
time.

Iterators

val to_seq : 'a t -> 'a Seq.t
Iterate on the queue, in front-to-back order. The behavior is not specified if the queue is
modified during the iteration.

Since: 4.07

val add_seq : 'a t -> 'a Seq.t -> unit
Add the elements from a sequence to the end of the queue.

Since: 4.07

val of_seq : 'a Seq.t -> 'a t
Create a queue from a sequence.

Since: 4.07
val exists2 : f:('a -> 'b -> bool) -> 'a list -> 'b list -> bool

Same as ListLabels.exists[29.34], but for a two-argument predicate.

Raises Invalid_argument if the two lists are determined to have different lengths.

val mem : 'a -> set:'a list -> bool

mem a ~set is true if and only if a is equal to an element of set.

val memq : 'a -> set:'a list -> bool

Same as ListLabels.mem[29.34], but uses physical equality instead of structural equality to
compare list elements.

List searching

val find : f:('a -> bool) -> 'a list -> 'a

find ~f l returns the first element of the list l that satisfies the predicate f.

Raises Not_found if there is no value that satisfies f in the list l.

val find_opt : f:('a -> bool) -> 'a list -> 'a option

find ~f l returns the first element of the list l that satisfies the predicate f. Returns None if there is no value that satisfies f in the list l.

Since: 4.05

val find_index : f:('a -> bool) -> 'a list -> int option

find_index ~f xs returns Some i, where i is the index of the first element of the list xs
that satisfies f x, if there is such an element.

It returns None if there is no such element.

Since: 5.1

val find_map : f:('a -> 'b option) -> 'a list -> 'b option

find_map ~f l applies f to the elements of l in order, and returns the first result of the
form Some v, or None if none exist.

Since: 4.10

val find_mapi : f:(int -> 'a -> 'b option) -> 'a list -> 'b option

Same as find_map, but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

Since: 5.1

val filter : f:('a -> bool) -> 'a list -> 'a list

filter ~f l returns all the elements of the list l that satisfy the predicate f. The order of the elements in the input list is preserved.
Examples

Basic Example

A basic example:

```pascal
# let q = Queue.create ()
val q : '_weak1 Queue.t = <abstr>

# Queue.push 1 q; Queue.push 2 q; Queue.push 3 q
- : unit = ()

# Queue.length q
- : int = 3

# Queue.pop q
- : int = 1

# Queue.pop q
- : int = 2

# Queue.pop q
- : int = 3

# Queue.pop q
Exception: Stdlib.Queue.Empty.
```

Search Through a Graph

For a more elaborate example, a classic algorithmic use of queues is to implement a BFS (breadth-first search) through a graph.

```pascal
type graph = {
    edges: (int, int list) Hashtbl.t
}

(* Search in graph [g] using BFS, starting from node [start].
   It returns the first node that satisfies [p], or [None] if
   no node reachable from [start] satisfies [p].
)
let search_for ~ (g:graph) ~ (start:int) (p:int -> bool) : int option =
    let to_explore = Queue.create() in
    let explored = Hashtbl.create 16 in
```
val find_all : f:('a -> bool) -> 'a list -> 'a list
find_all is another name for ListLabels.filter[29.34].

val filteri : f:(int -> 'a -> bool) -> 'a list -> 'a list
Same as ListLabels.filter[29.34], but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

Since: 4.11

List manipulation

val take : int -> 'a list -> 'a list

take n l returns the prefix of l of length n, or a copy of l if n > length l. This is the
empty list if n is negative.

**Warning.** In version 5.3 only, this function raises Invalid_argument for negative n values.

Since: 5.3

val drop : int -> 'a list -> 'a list

drop n l returns the suffix of l after n elements, or [] if n > length l. This is l if n is
negative.

**Warning.** In version 5.3 only, this function raises Invalid_argument for negative n values.

Since: 5.3

val takewhile : f:('a -> bool) -> 'a list -> 'a list

takewhile p l is the longest (possibly empty) prefix of l containing only elements that
satisfy p.

Since: 5.3

val dropwhile : f:('a -> bool) -> 'a list -> 'a list

dropwhile p l is the longest (possibly empty) suffix of l starting at the first element that
does not satisfy p.

Since: 5.3

val partition : f:('a -> bool) -> 'a list -> 'a list * 'a list

partition ~f l returns a pair of lists (l1, l2), where l1 is the list of all the elements of l
that satisfy the predicate f, and l2 is the list of all the elements of l that do not satisfy f.
The order of the elements in the input list is preserved.

val partition_map :
f:('a -> ('b, 'c) Either.t) -> 'a list -> 'b list * 'c list

partition_map f l returns a pair of lists (l1, l2) such that, for each element x of the
input list l:
Queue.push start to_explore;
let rec loop () =
  if Queue.is_empty to_explore then None
else
  (* node to explore *)
  let node = Queue.pop to_explore in
  explore_node node

and explore_node node =
  if not (Hashtbl.mem explored node) then (
    if p node then Some node (* found *)
    else (
      Hashtbl.add explored node ();
      let children =
        Hashtbl.find_opt g_edges node
      |> Option.value ~default:[]
      in
      List.iter (fun child -> Queue.push child to_explore) children;
      loop()
    )
  ) else loop()
in
loop()

(* a sample graph *)
let my_graph: graph =
  let edges =
    List.to_seq [
      1, [2;3];
      2, [10; 11];
      3, [4;5];
      5, [100];
      11, [0; 20];
    ]
  |> Hashtbl.of_seq
in {edges}

# search_for ~g:my_graph ~start:1 (fun x -> x = 30)
- : int option = None

# search_for ~g:my_graph ~start:1 (fun x -> x >= 15)
- : int option = Some 20

# search_for ~g:my_graph ~start:1 (fun x -> x >= 50)
- : int option = Some 100
* if `f x` is Left y1, then y1 is in `l1`, and

* if `f x` is Right y2, then y2 is in `l2`.

The output elements are included in `l1` and `l2` in the same relative order as the
corresponding input elements in `l`.

In particular, `partition_map` (`fun x -> if f x then Left x else Right x`) `l` is
equivalent to `partition f l`.

**Since:** 4.12

## Association lists

`val assoc : 'a -> ('a * 'b) list -> 'b`

`assoc a l` returns the value associated with key `a` in the list of pairs `l`. That is, `assoc a [ ... ; (a,b); ... ] = b` if `(a,b)` is the leftmost binding of `a` in list `l`.

**Raises:** `Not_found` if there is no value associated with `a` in the list `l`.

`val assoc_opt : 'a -> ('a * 'b) list -> 'b option`

`assoc_opt a l` returns the value associated with key `a` in the list of pairs `l`. That is, `assoc_opt a [ ... ; (a,b); ... ] = Some b` if `(a,b)` is the leftmost binding of `a` in list `l`. Returns `None` if there is no value associated with `a` in the list `l`.

**Since:** 4.05

`val assq : 'a -> ('a * 'b) list -> 'b`

Same as `ListLabels.assoc[29.34]`, but uses physical equality instead of structural equality to compare keys.

`val assq_opt : 'a -> ('a * 'b) list -> 'b option`

Same as `ListLabels.assoc_opt[29.34]`, but uses physical equality instead of structural
equality to compare keys.

**Since:** 4.05

`val mem assoc : 'a -> map:('a * 'b) list -> bool`

Same as `ListLabels.assoc[29.34]`, but simply return `true` if a binding exists, and `false` if no bindings exist for the given key.

`val mem Assq : 'a -> map:('a * 'b) list -> bool`

Same as `ListLabels.mem assoc[29.34]`, but uses physical equality instead of structural
equality to compare keys.

`val remove assoc : 'a -> ('a * 'b) list -> ('a * 'b) list`

`remove assoc a l` returns the list of pairs `l` without the first pair with key `a`, if any. Not tail-recursive.
## 28.45 Module Random : Pseudo-random number generators (PRNG).

With multiple domains, each domain has its own generator that evolves independently of the generators of other domains. When a domain is created, its generator is initialized by splitting the state of the generator associated with the parent domain.

In contrast, all threads within a domain share the same domain-local generator. Independent generators can be created with the `Random.split` [28.45] function and used with the functions from the `Random.State` [28.45] module.

### Basic functions

**val init : int -> unit**

Initialize the domain-local generator, using the argument as a seed. The same seed will always yield the same sequence of numbers.

**val full_init : int array -> unit**

Same as `Random.init` [28.45] but takes more data as seed.

**val self_init : unit -> unit**

Initialize the domain-local generator with a random seed chosen in a system-dependent way. If `/dev/urandom` is available on the host machine, it is used to provide a highly random initial seed. Otherwise, a less random seed is computed from system parameters (current time, process IDs, domain-local state).

**val bits : unit -> int**

Return 30 random bits in a nonnegative integer.

**Before 5.0** used a different algorithm (affects all the following functions)

**val int : int -> int**

`Random.int bound` returns a random integer between 0 (inclusive) and `bound` (exclusive). `bound` must be greater than 0 and less than $2^{30}$.

**val full_int : int -> int**

`Random.full_int bound` returns a random integer between 0 (inclusive) and `bound` (exclusive). `bound` may be any positive integer.

If `bound` is less than $2^{30}$, `Random.full_int bound` is equal to `Random.int` [28.45] `bound`. If `bound` is greater than $2^{30}$ (on 64-bit systems or non-standard environments, such as JavaScript), `Random.full_int` returns a value, where `Random.int` [28.45] raises `Invalid_argument` [27.2].

**Since: 4.13**
val remove : 'a -> ('a * 'b) list -> ('a * 'b) list

Same as ListLabels.removeيسر[29.34], but uses physical equality instead of structural
equality to compare keys. Not tail-recursive.

Lists of pairs

val split : ('a * 'b) list -> 'a list * 'b list

Transform a list of pairs into a pair of lists: split [(a1,b1); ...; (an,bn)] is ([a1;
...; an], [b1; ...; bn]). Not tail-recursive.

val combine : 'a list -> 'b list -> ('a * 'b) list

Transform a pair of lists into a list of pairs: combine [a1; ...; an] [b1; ...; bn] is
[(a1,b1); ...; (an,bn)].

Raises Invalid_argument if the two lists have different lengths. Not tail-recursive.

Sorting

val sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list

Sort a list in increasing order according to a comparison function. The comparison function
must return 0 if its arguments compare as equal, a positive integer if the first is greater, and a
negative integer if the first is smaller (see Array.sort for a complete specification). For
example, compare[28.2] is a suitable comparison function. The resulting list is sorted in
increasing order. ListLabels.sort[29.34] is guaranteed to run in constant heap space (in
addition to the size of the result list) and logarithmic stack space.

The current implementation uses Merge Sort. It runs in constant heap space and logarithmic
stack space.

val stable_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list

Same as ListLabels.sort[29.34], but the sorting algorithm is guaranteed to be stable (i.e.
elements that compare equal are kept in their original order).

The current implementation uses Merge Sort. It runs in constant heap space and logarithmic
stack space.

val fast_sort : cmp:('a -> 'a -> int) -> 'a list -> 'a list

Same as ListLabels.sort[29.34] or ListLabels.stable_sort[29.34], whichever is faster on
typical input.

val sort_uniq : cmp:('a -> 'a -> int) -> 'a list -> 'a list

Same as ListLabels.sort[29.34], but also remove duplicates: if multiple elements compare
equal, keep only the first.

Before 5.4 the element kept was not necessarily the first one.

Since: 4.03
val int32: Int32.t -> Int32.t

Random.int32 bound returns a random integer between 0 (inclusive) and bound (exclusive).
bound must be greater than 0.

val nativeint: Nativeint.t -> Nativeint.t

Random.nativeint bound returns a random integer between 0 (inclusive) and bound
(exclusive). bound must be greater than 0.

val int64: Int64.t -> Int64.t

Random.int64 bound returns a random integer between 0 (inclusive) and bound (exclusive).
bound must be greater than 0.

val float: float -> float

Random.float bound returns a random floating-point number between 0 and bound
(inclusive). If bound is negative, the result is negative or zero. If bound is 0, the result is 0.

val bool: unit -> bool

Randombool () returns true or false with probability 0.5 each.

val bits32: unit -> Int32.t

Random.bits32 () returns 32 random bits as an integer between Int32.min_int[28.27] and
Int32.max_int[28.27].

Since: 4.14

val bits64: unit -> Int64.t

Random.bits64 () returns 64 random bits as an integer between Int64.min_int[28.28] and
Int64.max_int[28.28].

Since: 4.14

val nativebits: unit -> Nativeint.t

Random.nativebits () returns 32 or 64 random bits (depending on the bit width of the
platform) as an integer between Nativeint.min_int[28.37] and Nativeint.max_int[28.37].

Since: 4.14

Advanced functions

The functions from module Random.State[28.45] manipulate the current state of the random
generator explicitly. This allows using one or several deterministic PRNGs, even in a multi-threaded
program, without interference from other parts of the program.

module State :

sig

type t
```h
val merge : cmp: ('a -> 'a -> int) -> 'a list -> 'a list -> 'a list
```

Merge two lists: Assuming that 11 and 12 are sorted according to the comparison function `cmp`, `merge ~cmp 11 12` will return a sorted list containing all the elements of 11 and 12. If several elements compare equal, the elements of 11 will be before the elements of 12. Not tail-recursive (sum of the lengths of the arguments).

## Lists and Sequences

```h
val to_seq : 'a list -> 'a Seq.t
```

Iterate on the list.

**Since: 4.07**

```h
val of_seq : 'a Seq.t -> 'a list
```

Create a list from a sequence.

**Since: 4.07**

## 29.35 Module Map : Association tables over ordered types.

This module implements applicative association tables, also known as finite maps or dictionaries, given a total ordering function over the keys. All operations over maps are purely applicative (no side-effects). The implementation uses balanced binary trees, and therefore searching and insertion take time logarithmic in the size of the map.

For instance:

```h
module IntPairs =
  struct
    type t = int * int
    let compare (x0,y0) (x1,y1) =
      match Stdlib comparisons
        0 -> Stdlib compare y0 y1
      | c -> c
  end

module PairsMap = Map.Make(IntPairs)

let m = PairsMap.(empty |> add (0,1) "hello" |> add (1,0) "world")
```

This creates a new module `PairsMap`, with a new type `'a PairsMap.t` of maps from `int * int` to `'a`. In this example, `m` contains string values so its type is `string PairsMap.t`.

```h
module type OrderedType =
  sig
```
The type of PRNG states.

val make : int array -> t

Create a new state and initialize it with the given seed.

val make self init : unit -> t

Create a new state and initialize it with a random seed chosen in a system-dependent
way. The seed is obtained as described in Random. self_init [28.45].

val copy : t -> t

Return a copy of the given state.

val bits : t -> int

val int : t -> int -> int

val full_int : t -> int -> int

val int32 : t -> Int32.t -> Int32.t

val nativeint : t -> Nativeint.t -> Nativeint.t

val int64 : t -> Int64.t -> Int64.t

val float : t -> float -> float

val bool : t -> bool

val bits32 : t -> Int32.t

val bits64 : t -> Int64.t

val nativebits : t -> Nativeint.t

These functions are the same as the basic functions, except that they use (and update)
the given PRNG state instead of the default one.

val split : t -> t

Draw a fresh PRNG state from the given PRNG state. (The given PRNG state is
modified.) The new PRNG is statistically independent from the given PRNG. Data can
be drawn from both PRNGs, in any order, without risk of correlation. Both PRNGs can
be split later, arbitrarily many times.

Since: 5.0

val to_binary_string : t -> string

Serializes the PRNG state into an immutable sequence of bytes. See
Random.State.of_binary_string [28.45] for deserialization.

The `string` type is intended here for serialization only, the encoding is not
human-readable and may not be printable.

Note that the serialization format may differ across OCaml versions.

Since: 5.1
type t

The type of the map keys.

val compare : t -> t -> int

A total ordering function over the keys. This is a two-argument function f such that f
e1 e2 is zero if the keys e1 and e2 are equal, f e1 e2 is strictly negative if e1 is smaller
than e2, and f e1 e2 is strictly positive if e1 is greater than e2. Example: a suitable
ordering function is the generic structural comparison function compare[28.2].

end

Input signature of the functor Map.Make[29.35].

module type S =
sig

Maps

type key

The type of the map keys.

type !+'a t

The type of maps from type key to type 'a.

val empty : 'a t

The empty map.

val add : key -> 'a -> 'a t -> 'a t

add key data m returns a map containing the same bindings as m, plus a binding of key
to data. If key was already bound in m to a value that is physically equal to data, m is
returned unchanged (the result of the function is then physically equal to m). Otherwise,
the previous binding of key in m disappears.

Before 4.03 Physical equality was not ensured.

val add_to_list : key -> 'a -> 'a list t -> 'a list t

add_to_list key data m is m with key mapped to l such that l is data :: Map.find
key m if key was bound in m and [data] otherwise.

Since: 5.1

val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
`val of_binary_string : string -> t`

Deserializes a byte sequence obtained by calling

`Random.State.to_binary_string[28.45]`. The resulting PRNG state will produce the
same random numbers as the state that was passed as input to

`Random.State.to_binary_string[28.45]`.

Since: 5.1

Raises `Failure` if the input is not in the expected format.

Note that the serialization format may differ across OCaml versions.

Unlike the functions provided by the ` Marshal`[28.34] module, this function either
produces a valid state or fails cleanly with a ` Failure` exception. It can be safely used on
user-provided, untrusted inputs.

end

`val get_state : unit -> State.t`

`get_state()` returns a fresh copy of the current state of the domain-local generator (which is
used by the basic functions).

`val set_state : State.t -> unit`

`set_state s` updates the current state of the domain-local generator (which is used by the
basic functions) by copying the state `s` into it.

`val split : unit -> State.t`

Draw a fresh PRNG state from the current state of the domain-local generator used by the
default functions. (The state of the domain-local generator is modified.) See

`Random.State.split[28.45]`.

Since: 5.0

## 28.46 Module Result : Result values.

Result values handle computation results and errors in an explicit and declarative manner without resorting to exceptions.

Since: 4.08

### Results

```hml
type ('a, 'e) t = ('a, 'e) result =
| Ok of 'a
| Error of 'e
```

The type for result values. Either a value `Ok v` or an error `Error e`.

`val ok : 'a -> ('a, 'e) result`
update key f m returns a map containing the same bindings as m, except for the
binding of key. Depending on the value of y where y is f (find_opt key m), the
binding of key is added, removed or updated. If y is None, the binding is removed if it
exists; otherwise, if y is Some z then key is associated to z in the resulting map. If key
was already bound in m to a value that is physically equal to z, m is returned unchanged
(the result of the function is then physically equal to m).

Since: 4.06

val singleton : key -> 'a -> 'a t

singleton x y returns the one-element map that contains a binding y for x.

Since: 3.12

val remove : key -> 'a t -> 'a t

remove x m returns a map containing the same bindings as m, except for x which is
unbound in the returned map. If x was not in m, m is returned unchanged (the result of
the function is then physically equal to m).

Before 4.03 Physical equality was not ensured.

val merge :
(key -> 'a option -> 'b option -> 'c option) ->
'a t -> 'b t -> 'c t

merge f m1 m2 computes a map whose keys are a subset of the keys of m1 and of m2.
The presence of each such binding, and the corresponding value, is determined with the
function f. In terms of the find_opt operation, we have find_opt x (merge f m1 m2)
= f x (find_opt x m1) (find_opt x m2) for any key x, provided that f x None
None = None.

Since: 3.12

val union : (key -> 'a -> 'a -> 'a option) ->
'a t -> 'a t -> 'a t

union f m1 m2 computes a map whose keys are a subset of the keys of m1 and of m2.
When the same binding is defined in both arguments, the function f is used to combine
them. This is a special case of merge: union f m1 m2 is equivalent to merge f' m1 m2,
where

* f' _key None None = None

* f' _key (Some v) None = Some v

* f' _key None (Some v) = Some v

* f' key (Some v1) (Some v2) = f key v1 v2

Since: 4.03

val cardinal : 'a t -> int

Return the number of bindings of a map.

Since: 3.12
```
ok v is Ok v.
```

```
val error : 'e -> ('a, 'e) result
         error e is Error e.
```

```
val value : ('a, 'e) result -> default:'a -> 'a
         value r ~default is v if r is Ok v and default otherwise.
```

```
val get_ok : ('a, 'e) result -> 'a
           get_ok r is v if r is Ok v and raise otherwise.
           Raises Invalid_argument if r is Error _.
```

```
val get_error : ('a, 'e) result -> 'e
               get_error r is e if r is Error e and raise otherwise.
               Raises Invalid_argument if r is Ok _.
```

```
val bind : ('a, 'e) result ->
          ('a -> ('b, 'e) result) -> ('b, 'e) result
          bind r f is f v if r is Ok v and r if r is Error _.
```

```
val join : ((('a, 'e) result, 'e) result -> ('a, 'e) result
           join rr is r if rr is Ok r and rr if rr is Error _.
```

```
val map : ('a -> 'b) -> ('a, 'e) result -> ('b, 'e) result
         map f r is Ok (f v) if r is Ok v and r if r is Error _.
```

```
val map_error : ('e -> 'f) -> ('a, 'e) result -> ('a, 'f) result
               map_error f r is Error (f e) if r is Error e and r if r is Ok _.
```

```
val fold : ok:('a -> 'c) -> error:('e -> 'c) -> ('a, 'e) result -> 'c
          fold ~ok ~error r is ok v if r is Ok v and error e if r is Error e.
```

```
val iter : ('a -> unit) -> ('a, 'e) result -> unit
          iter f r is f v if r is Ok v and () otherwise.
```

```
val iter_error : ('e -> unit) -> ('a, 'e) result -> unit
               iter_error f r is f e if r is Error e and () otherwise.
```
## Bindings

**val bindings :** `'a t -> (key * 'a) list`

Return the list of all bindings of the given map. The returned list is sorted in increasing order of keys with respect to the ordering `Ord compares`, where `Ord` is the argument given to `Map.Make[29.35]`.

**Since:** 3.12

**val min_bindig :** `'a t -> key * 'a`

Return the binding with the smallest key in a given map (with respect to the `Ord compares` ordering), or raise `Not_found` if the map is empty.

**Since:** 3.12

**val min_bindig_opt :** `'a t -> (key * 'a) option`

Return the binding with the smallest key in the given map (with respect to the `Ord compares` ordering), or `None` if the map is empty.

**Since:** 4.05

**val max_bindig :** `'a t -> key * 'a`

Same as `Map.S.min_bindig[29.35]`, but returns the binding with the largest key in the given map.

**Since:** 3.12

**val max_bindig_opt :** `'a t -> (key * 'a) option`

Same as `Map.S.min_bindig_opt[29.35]`, but returns the binding with the largest key in the given map.

**Since:** 4.05

**val choose :** `'a t -> key * 'a`

Return one binding of the given map, or raise `Not_found` if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

**Since:** 3.12

**val choose_opt :** `'a t -> (key * 'a) option`

Return one binding of the given map, or `None` if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

**Since:** 4.05
## Predicates and comparisons

val is_ok : ('a, 'e) result -> bool
is_ok r is true if and only if r is Ok _.

val is_error : ('a, 'e) result -> bool
is_error r is true if and only if r is Error _.

val equal :
ok:('a -> 'a -> bool) ->
error:('e -> 'e -> bool) ->
('a, 'e) result -> ('a, 'e) result -> bool

equal ~ok ~error r0 r1 tests equality of r0 and r1 using ok and error to respectively
compare values wrapped by Ok _ and Error _.

val compare :
ok:('a -> 'a -> int) ->
error:('e -> 'e -> int) ->
('a, 'e) result -> ('a, 'e) result -> int

compare ~ok ~error r0 r1 totally orders r0 and r1 using ok and error to respectively
compare values wrapped by Ok _ and Error _ . Ok _ values are smaller than Error
 _ values.

## Converting

val to_option : ('a, 'e) result -> 'a option

to_option r is r as an option, mapping Ok v to Some v and Error _ to None.

val to_list : ('a, 'e) result -> 'a list

to_list r is [v] if r is Ok v and [] otherwise.

val to_seq : ('a, 'e) result -> 'a Seq.t

to_seq r is r as a sequence. Ok v is the singleton sequence containing v and Error _ is the
empty sequence.

## 28.47 Module Scnf : Formatted input functions.

**Alert unsynchronized_access.** Unsynchronized accesses to Scanning.in_channel are a programming error.
## Searching

```hkl
val find : key -> 'a t -> 'a
```

`find` `x m` returns the current value of `x` in `m`, or raises `Not_found` if no binding for `x` exists.

```hkl
val find_opt : key -> 'a t -> 'a option
```

`find_opt` `x m` returns `Some v` if the current value of `x` in `m` is `v`, or `None` if no binding for `x` exists.

**Since:** 4.05

```hkl
val find_first : (key -> bool) -> 'a t -> key * 'a
```

`find_first` `f m`, where `f` is a monotonically increasing function, returns the binding of `m` with the lowest key `k` such that `f k`, or raises `Not_found` if no such key exists.

For example, `find_first (fun k -> Ord comparisons k x >= 0) m` will return the first binding `k`, `v` of `m` where `Ord comparisons k x >= 0` (intuitively: `k >= x`), or raise `Not_found` if `x` is greater than any element of `m`.

**Since:** 4.05

```hkl
val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
```

`find_first_opt` `f m`, where `f` is a monotonically increasing function, returns an option containing the binding of `m` with the lowest key `k` such that `f k`, or `None` if no such key exists.

**Since:** 4.05

```hkl
val find_last : (key -> bool) -> 'a t -> key * 'a
```

`find_last` `f m`, where `f` is a monotonically decreasing function, returns the binding of `m` with the highest key `k` such that `f k`, or raises `Not_found` if no such key exists.

**Since:** 4.05

```hkl
val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
```

`find_last_opt` `f m`, where `f` is a monotonically decreasing function, returns an option containing the binding of `m` with the highest key `k` such that `f k`, or `None` if no such key exists.

**Since:** 4.05

## Traversing

```hkl
val iter : (key -> 'a -> unit) -> 'a t -> unit
```

`iter` `f m` applies `f` to all bindings in `map m`. `f` receives the key as first argument, and the associated value as second argument. The bindings are passed to `f` in increasing order with respect to the ordering over the type of the keys.
## Introduction

### Functional input with format strings

The module `Scanf` [28.47] provides formatted input functions or scanners.

The formatted input functions can read from any kind of input, including strings, files, or anything that can return characters. The more general source of characters is named a *formatted input channel* (or *scanning buffer*) and has type `Scanf.Scanning.in_channel` [28.47]. The more general formatted input function reads from any scanning buffer and is named `bscanf`.

Generally speaking, the formatted input functions have 3 arguments:

* the first argument is a source of characters for the input,

* the second argument is a format string that specifies the values to read,

* the third argument is a *receiver function* that is applied to the values read.

Hence, a typical call to the formatted input function `Scanf.bscanf` [28.47] is `bscanf ic fmt f`, where:

* `ic` is a source of characters (typically a *formatted input channel* with type `Scanf.Scanning.in_channel` [28.47]),

* `fmt` is a format string (the same format strings as those used to print material with module `Format` [28.43] or `Format` [28.21]),

* `f` is a function that has as many arguments as the number of values to read in the input according to `fmt`.

### A simple example

As suggested above, the expression `bscanf ic "%d" f` reads a decimal integer `n` from the source of characters `ic` and returns `f n`.

For instance,

* if we use `stdin` as the source of characters (`Scanf.Scanning.stdin` [28.47] is the predefined formatted input channel that reads from standard input),

* if we define the receiver `f` as `let f x = x + 1`,

then `bscanf Scanning.stdin "%d" f` reads an integer `n` from the standard input and returns `f n` (that is, `n + 1`). Thus, if we evaluate `bscanf stdin "%d" f`, and then enter `41` at the keyboard, the result we get is `42`.
```hkl
val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc
```

fold f m init computes (f kN dN ... (f k1 d1 init) ...), where k1 ... kN are the keys of all bindings in m (in increasing order), and d1 ... dN are the associated data.

Transforming

```hkl
val map : ('a -> 'b) -> 'a t -> 'b t
```

map f m returns a map with same domain as m, where the associated value a of all bindings of m has been replaced by the result of the application of f to a. The bindings are passed to f in increasing order with respect to the ordering over the type of the keys.

```hkl
val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
```

Same as Map.S.map[29.35], but the function receives as arguments both the key and the associated value for each binding of the map.

```hkl
val filter : (key -> 'a -> bool) -> 'a t -> 'a t
```

filter f m returns the map with all the bindings in m that satisfy predicate p. If every binding in m satisfies f, m is returned unchanged (the result of the function is then physically equal to m)

**Before 4.03** Physical equality was not ensured.

**Since:** 3.12

```hkl
val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
```

filter_map f m applies the function f to every binding of m, and builds a map from the results. For each binding (k, v) in the input map:

* if f k v is None then k is not in the result,

* if f k v is Some v' then the binding (k, v') is in the output map.

For example, the following function on maps whose values are lists

```hkl
filter_map
    (fun _k li -> match li with [] -> None | _::tl -> Some tl)
m
```

drops all bindings of m whose value is an empty list, and pops the first element of each value that is non-empty.

**Since:** 4.11

```hkl
val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
```
## Formatted input as a functional feature

The OCaml scanning facility is reminiscent of the corresponding C feature. However, it is also largely different, simpler, and yet more powerful: the formatted input functions are higher-order functionals and the parameter passing mechanism is just the regular function application not the variable assignment based mechanism which is typical for formatted input in imperative languages; the OCaml format strings also feature useful additions to easily define complex tokens; as expected within a functional programming language, the formatted input functions also support polymorphism, in particular arbitrary interaction with polymorphic user-defined scanners. Furthermore, the OCaml formatted input facility is fully type-checked at compile time.

### Unsynchronized accesses

Unsynchronized accesses to a `Scanf.Scanning.in_channel[28.47]` may lead to an invalid `Scanf.Scanning.in_channel[28.47]` state. Thus, concurrent accesses to `Scanf.Scanning.in_channel[28.47]`s must be synchronized (for instance with a `Mutex.t[28.36]`).

## Formatted input channel

module Scanning :

sig

type in_channel

The notion of input channel for the `Scanf[28.47]` module: those channels provide all the machinery necessary to read from any source of characters, including a `in_channel[27.2]` value. A `Scanf.Scanning.in_channel` value is also called a *formatted input channel* or *equivalently a scanning buffer*. The type `Scanf.Scanning.scanbuf[28.47]` below is an alias for `Scanning.in_channel`. Note that a `Scanning.in_channel` is not *concurrency-safe*: concurrent use may produce arbitrary values or exceptions.

**Since: 3.12**

type scanbuf = in_channel

The type of scanning buffers. A scanning buffer is the source from which a formatted input function gets characters. The scanning buffer holds the current state of the scan, plus a function to get the next char from the input, and a token buffer to store the string matched so far.

**Note:** a scanning action may often require to examine one character in advance; when this 'lookahead' character does not belong to the token read, it is stored back in the scanning buffer and becomes the next character yet to be read.

val stdin : in_channel

The standard input notion for the `Scanf[28.47]` module. `Scanning.stdin` is the `Scanf.Scanning.in_channel[28.47]` formatted input channel attached to `stdin[27.2]`.

**Note:** in the interactive system, when input is read from `stdin[27.2]`, the newline character that triggers evaluation is part of the input; thus, the scanning specifications must properly skip this additional newline character (for instance, simply add a `'\n'` as the last character of the format string).
`partition f m` returns a pair of maps (`m1`, `m2`), where `m1` contains all the bindings of `m` that satisfy the predicate `f`, and `m2` is the map with all the bindings of `m` that do not satisfy `f.

**Since:** 3.12

`val split : key -> 'a t -> 'a t * 'a option * 'a t`

`split x m` returns a triple (`l`, `data`, `r`), where `l` is the map with all the bindings of `m` whose key is strictly less than `x`; `r` is the map with all the bindings of `m` whose key is strictly greater than `x`; `data` is `None` if `m` contains no binding for `x`, or `Some v` if `m` binds `v` to `x.

**Since:** 3.12

## Predicates and comparisons

`val is_empty : 'a t -> bool`

Test whether a map is empty or not.

`val mem : key -> 'a t -> bool`

`mem x m` returns `true` if `m` contains a binding for `x`, and `false` otherwise.

`val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool`

`equal cmp m1 m2` tests whether the maps `m1` and `m2` are equal, that is, contain equal keys and associate them with equal data. `cmp` is the equality predicate used to compare the data associated with the keys.

`val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int`

Total ordering between maps. The first argument is a total ordering used to compare data associated with equal keys in the two maps.

`val for_all : (key -> 'a -> bool) -> 'a t -> bool`

`for_all f m` checks if all the bindings of the map satisfy the predicate `f`.

**Since:** 3.12

`val exists : (key -> 'a -> bool) -> 'a t -> bool`

`exists f m` checks if at least one binding of the map satisfies the predicate `f`.

**Since:** 3.12
**Since: 3.12**

```perl
type file_name = string
```

A convenient alias to designate a file name.

**Since: 4.00**

```perl
val open_in : file_name -> in_channel
```

`Scanning.open_in fname` returns a `Scanf.Scanning.in_channel[28.47]` formatted input channel for bufferized reading in text mode from file `fname`.

Note: `open_in` returns a formatted input channel that efficiently reads characters in large chunks; in contrast, `from_channel` below returns formatted input channels that must read one character at a time, leading to a much slower scanning rate.

**Since: 3.12**

```perl
val open_in_bin : file_name -> in_channel
```

`Scanning.open_in_bin fname` returns a `Scanf.Scanning.in_channel[28.47]` formatted input channel for bufferized reading in binary mode from file `fname`.

**Since: 3.12**

```perl
val close_in : in_channel -> unit
```

Closes the `in_channel[27.2]` associated with the given `Scanf.Scanning.in_channel[28.47]` formatted input channel.

**Since: 3.12**

```perl
val from_file : file_name -> in_channel
```

An alias for `Scanf.Scanning.open_in[28.47]` above.

```perl
val from_file_bin : string -> in_channel
```

An alias for `Scanf.Scanning.open_in_bin[28.47]` above.

```perl
val from_string : string -> in_channel
```

`Scanning.from_string s` returns a `Scanf.Scanning.in_channel[28.47]` formatted input channel which reads from the given string. Reading starts from the first character in the string. The end-of-input condition is set when the end of the string is reached.

```perl
val from_function : (unit -> char) -> in_channel
```

`Scanning.from_function f` returns a `Scanf.Scanning.in_channel[28.47]` formatted input channel with the given function as its reading method.

When scanning needs one more character, the given function is called.

When the function has no more character to provide, it *must* signal an end-of-input condition by raising the exception `End_of_file`.
Converting

val to_list : 'a t -> (key * 'a) list

to_list m is Map.S.bindings[29.35] m.

Since: 5.1

val of_list : (key * 'a) list -> 'a t

of_list bs adds the bindings of bs to the empty map, in list order (if a key is bound twice in bs the last one takes over).

Since: 5.1

val to_seq : 'a t -> (key * 'a) Seq.t

Iterate on the whole map, in ascending order of keys

Since: 4.07

val to_rev_seq : 'a t -> (key * 'a) Seq.t

Iterate on the whole map, in descending order of keys

Since: 4.12

val to_seq_from : key -> 'a t -> (key * 'a) Seq.t

to_seq_from k m iterates on a subset of the bindings of m, in ascending order of keys, from key k or above.

Since: 4.07

val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t

Add the given bindings to the map, in order.

Since: 4.07

val of_seq : (key * 'a) Seq.t -> 'a t

Build a map from the given bindings

Since: 4.07

end

Output signature of the functor Map.Make[29.35].

module Make :
functor (Ord : OrderedType) -> S with type key = Ord.t

Functor building an implementation of the map structure given a totally ordered type.
`val from_channel : in_channel -> in_channel`

`Scanning.from_channel` `ic` returns a `Scanf.Scanning.in_channel`[28.47] formatted input channel which reads from the regular `in_channel`[27.2] input channel `ic` argument. Reading starts at current reading position of `ic`.

`val end_of_input : in_channel -> bool`

`Scanning.end_of_input` `ic` tests the end-of-input condition of the given `Scanf.Scanning.in_channel`[28.47] formatted input channel.

`val beginning_of_input : in_channel -> bool`

`Scanning-beginning_of_input` `ic` tests the beginning of input condition of the given `Scanf.Scanning.in_channel`[28.47] formatted input channel.

`val name_of_input : in_channel -> string`

`Scanning.name_of_input` `ic` returns the name of the character source for the given `Scanf.Scanning.in_channel`[28.47] formatted input channel.

**Since:** 3.09

end

## Type of formatted input functions

`type ('a, 'b, 'c, 'd) scanner = ('a, Scanning.in_channel, 'b, 'c, 'a -> 'd, 'd) format6 -> 'c`

The type of formatted input scanners: `('a, 'b, 'c, 'd) scanner` is the type of a formatted input function that reads from some formatted input channel according to some format string; more precisely, if `scan` is some formatted input function, then `scan ic fmt f` applies `f` to all the arguments specified by format string `fmt`, when `scan` has read those arguments from the `Scanf.Scanning.in_channel`[28.47] formatted input channel `ic`.

For instance, the `Scanf.scanf`[28.47] function below has type `('a, 'b, 'c, 'd) scanner`, since it is a formatted input function that reads from `Scanf.Scanning.stdin`[28.47]: `scanf fmt f` applies `f` to the arguments specified by `fmt`, reading those arguments from `stdin`[27.2] as expected.

If the format `fmt` has some `%r` indications, the corresponding formatted input functions must be provided *before* receiver function `f`. For instance, if `read_elem` is an input function for values of type `t`, then `bscnf ic "%r;" read_elem f` reads a value `v` of type `t` followed by a `';'` character, and returns `f v`.

**Since:** 3.10

`type ('a, 'b, 'c, 'd) scanner_opt = ('a, Scanning.in_channel, 'b, 'c, 'a -> 'd option, 'd) format`

### exception Scan_failure of string

When the input can not be read according to the format string specification, formatted input functions typically raise exception `Scan_failure`.
## 29.36 Module Marshal: Marshaling of data structures.

This module provides functions to encode arbitrary data structures as sequences of bytes, which can then be written on a file or sent over a pipe or network connection. The bytes can then be read back later, possibly in another process, and decoded back into a data structure. The format for the byte sequences is compatible across all machines for a given version of OCaml.

Warning: marshaling is currently not type-safe. The type of marshaled data is not transmitted along the value of the data, making it impossible to check that the data read back possesses the type expected by the context. In particular, the result type of the ` Marshal.from_* ` functions is given as `'a`, but this is misleading: the returned OCaml value does not possess type `'a` for all `'a`; it has one, unique type which cannot be determined at compile-time. The programmer should explicitly give the expected type of the returned value, using the following syntax:

* (` Marshal.from_channel chan : type `). Anything can happen at run-time if the object in the file does not belong to the given type.

Values of extensible variant types, for example exceptions (of extensible type `exn`), returned by the unmarshaller should not be pattern-matched over through `match ... with` or `try ... with`, because unmarshalling does not preserve the information required for matching their constructors. Structural equalities with other extensible variant values does not work either. Most other uses such as `Printexc.to_string`, will still work as expected.

The representation of marshaled values is not human-readable, and uses bytes that are not printable characters. Therefore, input and output channels used in conjunction with ` Marshal.to_channel ` and ` Marshal.from_channel ` must be opened in binary mode, using e.g. ` open_out_bin ` or ` open_in_bin`; channels opened in text mode will cause unmarshaling errors on platforms where text channels behave differently than binary channels, e.g. Windows.

```hml
type extern_flags =
  | No_sharing
    Don't preserve sharing
```

```hml
  | Closures
    Send function closures
```

```hml
  | Compat_32
    Ensure 32-bit compatibility
```

The flags to the ` Marshal.to_* ` functions below.

```hml
val to_channel : out_channel -> 'a -> extern_flags list -> unit

 Marshal.to_channel chan v flags writes the representation of v on channel chan. The flags argument is a possibly empty list of flags that governs the marshaling behavior with respect to sharing, functional values, and compatibility between 32- and 64-bit platforms.
```

If `flags` does not contain ` Marshal.No_sharing `, circularities and sharing inside the value `v` are detected and preserved in the sequence of bytes produced. In particular, this guarantees that marshaling always terminates. Sharing between values marshaled by successive calls to ` Marshal.to_channel ` is neither detected nor preserved, though. If `flags` contains
## The general formatted input function

`val bscanf : Scanning.in_channel -> ('a, 'b, 'c, 'd) scanner`

`bscanf ic fmt r1 ... rN f` reads characters from the `Scanf.Scanning.in_channel` [28.47] formatted input channel `ic` and converts them to values according to format string `fmt`. As a final step, receiver function `f` is applied to the values read and gives the result of the `bscanf` call.

For instance, if `f` is the function `fun s i -> i + 1`, then `Scanf.sscnf "x = 1" "%s = %i"` `f` returns 2.

Arguments `r1` to `rN` are user-defined input functions that read the argument corresponding to the `%r` conversions specified in the format string.

`val bscanf_opt : Scanning.in_channel -> ('a, 'b, 'c, 'd) scanner_opt`

Same as `Scanf.bscanf` [28.47], but returns `None` in case of scanning failure.

Since: 5.0

## Format string description

The format string is a character string which contains three types of objects:

* plain characters, which are simply matched with the characters of the input (with a special case for space and line feed, see [28.47]),

* conversion specifications, each of which causes reading and conversion of one argument for the function `f` (see [28.47]),

* scanning indications to specify boundaries of tokens (see scanning [28.47]).

## The space character in format strings

As mentioned above, a plain character in the format string is just matched with the next character of the input; however, two characters are special exceptions to this rule: the space character (`' '`) or ASCII code 32) and the line feed character (`'
'`) or ASCII code 10). A space does not match a single space character, but any amount of 'whitespace' in the input. More precisely, a space inside the format string matches *any number* of tab, space, line feed and carriage return characters. Similarly, a line feed character in the format string matches either a single line feed or a carriage return followed by a line feed.

Matching *any* amount of whitespace, a space in the format string also matches no amount of whitespace at all; hence, the call `bscanf ib "Price = %d $"` (`fun p -> p`) succeeds and returns 1 when reading an input with various whitespace in it, such as `Price = 1 $`, `Price = 1 $`, or even `Price=1$`.

## Conversion specifications in format strings

Conversion specifications consist in the `%` character, followed by an optional flag, an optional field width, and followed by one or two conversion characters.

The conversion characters and their meanings are:
` Marshal.No_sharing ` , sharing is ignored. This results in faster marshaling if ` v ` contains no shared substructures, but may cause slower marshaling and larger byte representations if ` v ` actually contains sharing, or even non-termination if ` v ` contains cycles.

If `flags` does not contain ` Marshal.Closures `, marshaling fails when it encounters a functional value inside `v`: only 'pure' data structures, containing neither functions nor objects, can safely be transmitted between different programs. If `flags` contains ` Marshal.Closures `, functional values will be marshaled as a the position in the code of the program together with the values corresponding to the free variables captured in the closure. In this case, the output of marshaling can only be read back in processes that run exactly the same program, with exactly the same compiled code. (This is checked at un-marshaling time, using an MD5 digest of the code transmitted along with the code position.)

The exact definition of which free variables are captured in a closure is not specified and can vary between bytecode and native code (and according to optimization flags). In particular, a function value accessing a global reference may or may not include the reference in its closure. If it does, unmarshaling the corresponding closure will create a new reference, different from the global one.

If `flags` contains ` Marshal.Compat_32 `, marshaling fails when it encounters an integer value outside the range `-2³⁰`, `2³⁰-1` of integers that are representable on a 32-bit platform. This ensures that marshaled data generated on a 64-bit platform can be safely read back on a 32-bit platform. If `flags` does not contain ` Marshal.Compat_32 `, integer values outside the range `-2³⁰`, `2³⁰-1` are marshaled, and can be read back on a 64-bit platform, but will cause an error at un-marshaling time when read back on a 32-bit platform. The ` Mashal.Compat_32 ` flag only matters when marshaling is performed on a 64-bit platform; it has no effect if marshaling is performed on a 32-bit platform.

**Raises** `Failure` if `chan` is not in binary mode.

val to_bytes : 'a -> extern_flags list -> bytes

` Marshal.to_bytes v flags ` returns a byte sequence containing the representation of `v`. The `flags` argument has the same meaning as for ` Marshal.to_channel [29.36] `.

**Since:** 4.02

val to_string : 'a -> extern_flags list -> string

Same as `to_bytes` but return the result as a string instead of a byte sequence.

val to_buffer : bytes -> int -> int -> 'a -> extern_flags list -> int

` Marshal.to_buffer buff ofs len v flags ` marshals the value `v`, storing its byte representation in the sequence `buff`, starting at index `ofs`, and writing at most `len` bytes. It returns the number of bytes actually written to the sequence. If the byte representation of `v` does not fit in `len` characters, the exception `Failure` is raised.

val from_channel : in_channel -> 'a

` Marshal.from_channel chan ` reads from channel `chan` the byte representation of a structured value, as produced by one of the ` Marshal.to_* ` functions, and reconstructs and returns the corresponding value.
* `d`: reads an optionally signed decimal integer `(0-9+)`.

* `i`: reads an optionally signed integer (usual input conventions for decimal `(0-9+)`, hexadecimal `(0x[0-9a-f]+` and `0X[0-9A-F]+`), octal `(0o[0-7]+`), and binary `(0b[0-1]+`) notations are understood).

* `u`: reads an unsigned decimal integer.

* `x` or `X`: reads an unsigned hexadecimal integer (`[0-9a-fA-F]+`).

* `o`: reads an unsigned octal integer (`[0-7]+`).

* `s`: reads a string argument that spreads as much as possible, until the following bounding condition holds:

- a whitespace has been found (see [28.47]),

- a scanning indication (see scanning [28.47]) has been encountered,

- the end-of-input has been reached.

Hence, this conversion always succeeds: it returns an empty string if the bounding condition holds when the scan begins.

* `S`: reads a delimited string argument (delimiters and special escaped characters follow the lexical conventions of OCaml).

* `c`: reads a single character. To test the current input character without reading it, specify a null field width, i.e. use specification `%0c`. Raise `Invalid_argument`, if the field width specification is greater than 1.

* `C`: reads a single delimited character (delimiters and special escaped characters follow the lexical conventions of OCaml).

* `f`, `e`, `E`, `g`, `G`: reads an optionally signed floating-point number in decimal notation, in the style `dddd.ddd e/E+-dd`.

* `h`, `H`: reads an optionally signed floating-point number in hexadecimal notation.

* `F`: reads a floating point number according to the lexical conventions of OCaml (hence the decimal point is mandatory if the exponent part is not mentioned).

* `B`: reads a boolean argument (`true` or `false`).

* `b`: reads a boolean argument (for backward compatibility; do not use in new programs).

* `ld`, `li`, `lu`, `lx`, `lX`, `lo`: reads an `int32` argument to the format specified by the second letter for regular integers.

* `nd`, `ni`, `nu`, `nx`, `nX`, `no`: reads a `nativeint` argument to the format specified by the second letter for regular integers.
## Raises

* `End_of_file` if `chan` is already at the end of the file.

* `Failure` if the end of the file is reached during unmarshalling itself or if `chan` is not in binary mode.

`val from_bytes: bytes -> int -> 'a`

` Marshal.from_bytes buff ofs ` unmarshals a structured value like

` Marshal.from_channel[29.36] ` does, except that the byte representation is not read from a channel, but taken from the byte sequence ` buff ` , starting at position ` ofs ` . The byte sequence is not mutated.

`Since: 4.02`

`val from_string: string -> int -> 'a`

Same as `from_bytes` but take a string as argument instead of a byte sequence.

`val header_size: int`

The bytes representing a marshaled value are composed of a fixed-size header and a variable-sized data part, whose size can be determined from the header.

` Marshal header_size [29.36] ` is the size, in bytes, of the header. ` Marshal.data_size [29.36] ` ` buff ` ` ofs ` is the size, in bytes, of the data part, assuming a valid header is stored in ` buff ` starting at position ` ofs ` . Finally, ` Marshal.total_size [29.36] ` ` buff ` ` ofs ` is the total size, in bytes, of the marshaled value. Both ` Marshal.data_size [29.36] ` and ` Marshal.total_size [29.36] ` raise ` Failure ` if ` buff ` , ` ofs ` does not contain a valid header.

To read the byte representation of a marshaled value into a byte sequence, the program needs to read first ` Marshal header_size [29.36] ` bytes into the sequence, then determine the length of the remainder of the representation using ` Marshal.data_size [29.36] ` , make sure the sequence is large enough to hold the remaining data, then read it, and finally call ` Marshal.from_bytes [29.36] ` to unmarshal the value.

`val data_size: bytes -> int -> int`

See ` Marshal header_size [29.36] ` .

`val total_size: bytes -> int -> int`

See ` Marshal header_size [29.36] ` .

## Marshal and domain safety

Care must be taken when marshaling a mutable value that may be modified by a different domain. Mutating a value that is being marshaled (i.e., turned into a sequence of bytes) is a programming error and might result in surprising values (when unmarshaling) due to tearing, since marshaling involves byte-per-byte copy.
* `Ld`, `Li`, `Lu`, `Lx`, `LX`, `Lo`: reads an `int64` argument to the format specified by the second letter for regular integers.

* `[ range ]`: reads characters that matches one of the characters mentioned in the range of characters `range` (or not mentioned in it, if the range starts with `^`). Reads a string that can be empty, if the next input character does not match the range. The set of characters from `c1` to `c2` (inclusively) is denoted by `c1-c2`. Hence, `%[0-9]` returns a string representing a decimal number or an empty string if no decimal digit is found; similarly, `%[0-9a-f]` returns a string of hexadecimal digits. If a closing bracket appears in a range, it must occur as the first character of the range (or just after the `^` in case of range negation); hence `[]` matches a `]` character and `[^]` matches any character that is not ]. Use `%%` and `@` to include a `%` or a `@` in a range.

* `r`: user-defined reader. Takes the next `ri` formatted input function and applies it to the scanning buffer `ib` to read the next argument. The input function `ri` must therefore have type `Scanning.in_channel -> 'a` and the argument read has type `'a`.

* `{ fmt %}`: reads a format string argument. The format string read must have the same type as the format string specification `fmt`. For instance, `"%{ %i %}"` reads any format string that can read a value of type `int`; hence, if `s` is the string `"fmt:\"number is %u\""`, then `Scanf.sссанf s "fmt: %{%i%}"` succeeds and returns the format string `"number is %u"`.

* `( fmt %)`: scanning sub-format substitution. Reads a format string `rf` in the input, then goes on scanning with `rf` instead of scanning with `fmt`. The format string `rf` must have the same type as the format string specification `fmt` that it replaces. For instance, `"%( %i %)"` reads any format string that can read a value of type `int`. The conversion returns the format string read `rf`, and then a value read using `rf`. Hence, if `s` is the string `"\"%4d\"1234.00", then `Scanf.sссанf s "%(%i%)"` (`fun fmt i -> fmt, i`) evaluates to (`"%4d", 1234`). This behaviour is not mere format substitution, since the conversion returns the format string read as additional argument. If you need pure format substitution, use special flag `_` to discard the extraneous argument: conversion `%_`( `fmt %`) reads a format string `rf` and then behaves the same as format string `rf`. Hence, if `s` is the string `"\"%4d\"1234.00", then `Scanf.sссанf s "%_%( %i %)"` is simply equivalent to `Scanf.sссанf "1234.00" "%4d"`.

* `l`: returns the number of lines read so far.

* `n`: returns the number of characters read so far.

* `N` or `L`: returns the number of tokens read so far.

* `!`: matches the end of input condition.

* `%`: matches one `%` character in the input.

* `@`: matches one `@` character in the input.

* `;`: does nothing.
## 29.37 Module MoreLabels : Extra labeled libraries.

This meta-module provides labeled versions of the `MoreLabels.Hashtbl[29.37]`, `MoreLabels.Map[29.37]` and `MoreLabels.Set[29.37]` modules.

This module is intended to be used through `open MoreLabels` which replaces `MoreLabels.Hashtbl[29.37]`, `MoreLabels.Map[29.37]`, and `MoreLabels.Set[29.37]` with their labeled counterparts.

For example:

```python
open MoreLabels
```

```python
Hashtbl.iter ~f:(fun ~key ~data -> g key data) table
```

### module Hashtbl :

```python
sig
```

Hash tables and hash functions.

Hash tables are hashed association tables, with in-place modification. Because most operations on a hash table modify their input, they're more commonly used in imperative code. The lookup of the value associated with a key (see `MoreLabels.Hashtbl.find[29.37]`, `MoreLabels.Hashtbl.find_opt[29.37]`) is normally very fast, often faster than the equivalent lookup in `MoreLabels.Map[29.37]`.

The functors `MoreLabels.Hashtbl.Make[29.37]` and `MoreLabels.Hashtbl.MakeSeeded[29.37]` can be used when performance or flexibility are key. The user provides custom equality and hash functions for the key type, and obtains a custom hash table type for this particular type of key.

**Warning** a hash table is only as good as the hash function. A bad hash function will turn the table into a degenerate association list, with linear time lookup instead of constant time lookup.

The polymorphic `MoreLabels.Hashtbl.t[29.37]` hash table is useful in simpler cases or in interactive environments. It uses the polymorphic `MoreLabels.Hashtbl.hash[29.37]` function defined in the OCaml runtime (at the time of writing, it's SipHash), as well as the polymorphic equality (`=`).

See the examples section [29.48].

### Unsynchronized accesses

Unsynchronized accesses to a hash table may lead to an invalid hash table state. Thus, concurrent accesses to a hash tables must be synchronized (for instance with a `Mutex.t[29.38]`).

### Generic interface

```python
type ('a, 'b) t = ('a, 'b) Hashtbl.t
```
Following the `%` character that introduces a conversion, there may be the special flag `?:` the conversion that follows occurs as usual, but the resulting value is discarded. For instance, if `f` is the function `fun i -> i + 1`, and `s` is the string `"x = 1"`, then `Scanf.sссанf s "%_s = %i" f` returns 2.

The field width is composed of an optional integer literal indicating the maximal width of the token to read. For instance, `%6d` reads an integer, having at most 6 decimal digits; `%4f` reads a float with at most 4 characters; and `%8[\000-\255]` returns the next 8 characters (or all the characters still available, if fewer than 8 characters are available in the input).

Notes:

* as mentioned above, a `%s` conversion always succeeds, even if there is nothing to read in the input: in this case, it simply returns `""`.

* in addition to the relevant digits, `'-'` characters may appear inside numbers (this is reminiscent to the usual OCaml lexical conventions). If stricter scanning is desired, use the range conversion facility instead of the number conversions.

* the `scanf` facility is not intended for heavy duty lexical analysis and parsing. If it appears not expressive enough for your needs, several alternative exists: regular expressions (module `Str[31.1]`), stream parsers, `ocamllex`-generated lexers, `ocamlyacc`-generated parsers.

## Scanning indications in format strings

Scanning indications appear just after the string conversions `%s` and `%[ range ]` to delimit the end of the token. A scanning indication is introduced by a `@` character, followed by some plain character `c`. It means that the string token should end just before the next matching `c` (which is skipped). If no `c` character is encountered, the string token spreads as much as possible. For instance, `"%s@\t"` reads a string up to the next tab character or to the end of input. If a `@` character appears anywhere else in the format string, it is treated as a plain character.

Note:

* As usual in format strings, `%` and `@` characters must be escaped using `%%` and `%%@`; this rule still holds within range specifications and scanning indications. For instance, format `"%s@%%"` reads a string up to the next `%` character, and format `"%s@%%@"` reads a string up to the next `@`.

* The scanning indications introduce slight differences in the syntax of `Scanf[28.47]` format strings, compared to those used for the `AMENTF[28.43]` module. However, the scanning indications are similar to those used in the `Format[28.21]` module; hence, when producing formatted text to be scanned by `Scanf.bscanf[28.47]`, it is wise to use printing functions from the `Format[28.21]` module (or, if you need to use functions from `AMENTF[28.43]`, banish or carefully double check the format strings that contain `'@'` characters).

## Exceptions during scanning

Scanners may raise the following exceptions when the input cannot be read according to the format string:
The type of hash tables from type `'a` to type `'b`.

```rust
val create : ?random:bool -> int -> ('a, 'b) t
```

`Hashtbl.create` n creates a new, empty hash table, with initial size greater or equal to the suggested size n. For best results, n should be on the order of the expected number of elements that will be in the table. The table grows as needed, so n is just an initial guess. If n is very small or negative then it is disregarded and a small default size is used. The optional `~random` parameter (a boolean) controls whether the internal organization of the hash table is randomized at each execution of `Hashtbl.create` or deterministic over all executions.

A hash table that is created with `~random` set to `false` uses a fixed hash function (`MoreLabels.Hasttbl.hash[29.37]`) to distribute keys among buckets. As a consequence, collisions between keys happen deterministically. In Web-facing applications or other security-sensitive applications, the deterministic collision patterns can be exploited by a malicious user to create a denial-of-service attack: the attacker sends input crafted to create many collisions in the table, slowing the application down.

A hash table that is created with `~random` set to `true` uses the seeded hash function `MoreLabels.Hasttbl.seeded_hash[29.37]` with a seed that is randomly chosen at hash table creation time. In effect, the hash function used is randomly selected among $2^{30}$ different hash functions. All these hash functions have different collision patterns, rendering ineffective the denial-of-service attack described above. However, because of randomization, enumerating all elements of the hash table using `MoreLabels.Hasttbl.fold[29.37]` or `MoreLabels.Hasttbl.iter[29.37]` is no longer deterministic: elements are enumerated in different orders at different runs of the program.

If no `~random` parameter is given, hash tables are created in non-random mode by default. This default can be changed either programmatically by calling `MoreLabels.Hasttbl.randomize[29.37]` or by setting the R flag in the `OCAMLRUNPARAM` environment variable.

**Before 4.00** the `~random` parameter was not present and all hash tables were created in non-randomized mode.

```rust
val clear : ('a, 'b) t -> unit
```

Empty a hash table. Use `reset` instead of `clear` to shrink the size of the bucket table to its initial size.

```rust
val reset : ('a, 'b) t -> unit
```

Empty a hash table and shrink the size of the bucket table to its initial size.

**Since: 4.00**

```rust
val copy : ('a, 'b) t -> ('a, 'b) t
```

Return a copy of the given hashtable.
* Raise `ScanfScan_failure[28.47]` if the input does not match the format.

* Raise `Failure` if a conversion to a number is not possible.

* Raise `End_of_file` if the end of input is encountered while some more characters are needed to read the current conversion specification.

* Raise `Invalid_argument` if the format string is invalid.

**Note:**

* as a consequence, scanning a `%s` conversion never raises exception `End_of_file`: if the end of input is reached the conversion succeeds and simply returns the characters read so far, or `""` if none were ever read.

## Specialised formatted input functions

**val sscnf :** `string -> ('a, 'b, 'c, 'd) scanner`

Same as `Scanf.bscanf[28.47]`, but reads from the given string.

**val sscnf_opt :** `string -> ('a, 'b, 'c, 'd) scanner_opt`

Same as `Scanf.sscnf[28.47]`, but returns `None` in case of scanning failure.

**Since:** 5.0

**val scanf :** `('a, 'b, 'c, 'd) scanner`

Same as `Scanf.bscanf[28.47]`, but reads from the predefined formatted input channel

`Scanf.Scanning.stdin[28.47]` that is connected to `stdin[27.2]`.

**val scanf_opt :** `('a, 'b, 'c, 'd) scanner_opt`

Same as `Scanf.sprintf[28.47]`, but returns `None` in case of scanning failure.

**Since:** 5.0

**val kscnf :**

`Scanning.in_channel ->`

`(Scanning.in_channel -> exn -> 'd) -> ('a, 'b, 'c, 'd) scanner`

Same as `Scanf.bscanf[28.47]`, but takes an additional function argument `ef` that is called in case of error: if the scanning process or some conversion fails, the scanning function aborts and calls the error handling function `ef` with the formatted input channel and the exception that aborted the scanning process as arguments.

**val ksscnf :**

`string ->`

`(Scanning.in_channel -> exn -> 'd) -> ('a, 'b, 'c, 'd) scanner`

Same as `Scanf.kscnf[28.47]` but reads from the given string.

**Since:** 4.02
```hkl
val add : ('a, 'b) t -> key:'a -> data:'b -> unit
```

`Hashtbl.add tbl ~key ~data` adds a binding of `key` to `data` in table `tbl`.

**Warning:** Previous bindings for `key` are not removed, but simply hidden. That is, after performing `MoreLabels.Hashtbl.remove[29.37] tbl key`, the previous binding for `key`, if any, is restored. (Same behavior as with association lists.)

If you desire the classic behavior of replacing elements, see `MoreLabels.Hashtbl.replace[29.37]`.

```hkl
val find : ('a, 'b) t -> 'a -> 'b
```

`Hashtbl.find tbl x` returns the current binding of `x` in `tbl`, or raises `Not_found` if no such binding exists.

```hkl
val find_opt : ('a, 'b) t -> 'a -> 'b option
```

`Hashtbl.find_opt tbl x` returns the current binding of `x` in `tbl`, or `None` if no such binding exists.

**Since: 4.05**

```hkl
val find_all : ('a, 'b) t -> 'a -> 'b list
```

`Hashtbl.find_all tbl x` returns the list of all data associated with `x` in `tbl`. The current binding is returned first, then the previous bindings, in reverse order of introduction in the table.

```hkl
val mem : ('a, 'b) t -> 'a -> bool
```

`Hashtbl.mem tbl x` checks if `x` is bound in `tbl`.

```hkl
val remove : ('a, 'b) t -> 'a -> unit
```

`Hashtbl.remove tbl x` removes the current binding of `x` in `tbl`, restoring the previous binding if it exists. It does nothing if `x` is not bound in `tbl`.

```hkl
val replace : ('a, 'b) t -> key:'a -> data:'b -> unit
```

`Hashtbl.replace tbl ~key ~data` replaces the current binding of `key` in `tbl` by a binding of `key` to `data`. If `key` is unbound in `tbl`, a binding of `key` to `data` is added to `tbl`. This is functionally equivalent to `MoreLabels.Hashtbl.remove[29.37] tbl key` followed by `MoreLabels.Hashtbl.add[29.37] tbl key` data.

```hkl
val iter : f:(key:'a -> data:'b -> unit) -> ('a, 'b) t -> unit
```

`Hashtbl.iter ~f tbl` applies `f` to all bindings in table `tbl`. `f` receives the `key` as first argument, and the associated value as second argument. Each binding is presented exactly once to `f`.

The order in which the bindings are passed to `f` is unspecified. However, if the table contains several bindings for the same key, they are passed to `f` in reverse order of introduction, that is, the most recent binding is passed first.
Reading format strings from input

val bscnf_format :
    Scanning.in_channel ->
    ('a, 'b, 'c, 'd, 'e, 'f) format6 ->
    ((('a, 'b, 'c, 'd, 'e, 'f) format6 -> 'g) -> 'g

bscnf_format ic fmt f reads a format string token from the formatted input channel ic,
according to the given format string fmt, and applies f to the resulting format string value.

Since: 3.09

Raises Scan_failure if the format string value read does not have the same type as fmt.

val sscnf_format :
    string ->
    ('a, 'b, 'c, 'd, 'e, 'f) format6 ->
    ((('a, 'b, 'c, 'd, 'e, 'f) format6 -> 'g) -> 'g

Same as Scanf.bscnf_format[28.47], but reads from the given string.

Since: 3.09

val format_from_string :
    string ->
    ('a, 'b, 'c, 'd, 'e, 'f) format6 ->
    ('a, 'b, 'c, 'd, 'e, 'f) format6

format_from_string s fmt converts a string argument to a format string, according to the
given format string fmt.

Since: 3.10

Raises Scan_failure if s, considered as a format string, does not have the same type as fmt.

val unescaped : string -> string

unescaped s return a copy of s with escape sequences (according to the lexical conventions of OCaml) replaced by their corresponding special characters. More precisely, Scanf.unescaped has the following property: for all string s, Scanf.unescaped (String.escaped s) = s.

Always return a copy of the argument, even if there is no escape sequence in the argument.

Since: 4.00

Raises Scan_failure if s is not properly escaped (i.e. s has invalid escape sequences or
special characters that are not properly escaped). For instance, Scanf.unescaped "\"" will
fail.

28.48 Module Seq : Sequences.

A sequence of type 'a Seq.t can be thought of as a **delayed list**, that is, a list whose elements are computed only when they are demanded by a consumer. This allows sequences to be produced and
If the hash table was created in non-randomized mode, the order in which the bindings
are enumerated is reproducible between successive runs of the program, and even
between minor versions of OCaml. For randomized hash tables, the order of enumeration
is entirely random.

The behavior is not specified if the hash table is modified by *f* during the iteration.

val filter_map_inplace :

f: (key:'a -> data:'b -> 'b option) -> ('a, 'b) t -> unit

Hashtbl.filter_map_inplace ~f tbl applies f to all bindings in table tbl and
update each binding depending on the result of f. If f returns None, the binding is
discarded. If it returns Some new_val, the binding is update to associate the key to
new_val.

Other comments for `MoreLabels.Hasttbl.iter`[29.37] apply as well.

Since: 4.03

val fold :

f: (key:'a -> data:'b -> 'acc -> 'acc) ->
('a, 'b) t -> init:'acc -> 'acc

Hashtbl.fold ~f tbl ~init computes (f kN dN ... (f k1 d1 init) ...), where
k1 ... kN are the keys of all bindings in tbl, and d1 ... dN are the associated values.
Each binding is presented exactly once to f.

The order in which the bindings are passed to *f* is unspecified. However, if the table
contains several bindings for the same key, they are passed to *f* in reverse order of
introduction, that is, the most recent binding is passed first.

If the hash table was created in non-randomized mode, the order in which the bindings
are enumerated is reproducible between successive runs of the program, and even
between minor versions of OCaml. For randomized hash tables, the order of enumeration
is entirely random.

The behavior is not specified if the hash table is modified by *f* during the iteration.

val length : ('a, 'b) t -> int

Hashtbl.length tbl returns the number of bindings in tbl. It takes constant time.
Multiple bindings are counted once each, so Hashtbl.length gives the number of times
Hashtbl.iter calls its first argument.

val randomize : unit -> unit

After a call to `Hashtbl.randomize()`, hash tables are created in randomized mode by default: `MoreLabels.Hasttbl.create`[29.37] returns randomized hash tables, unless the `~random:false` optional parameter is given. The same effect can be achieved by setting the `R` parameter in the `OCAMLRUNPARAM` environment variable.

It is recommended that applications or Web frameworks that need to protect themselves
against the denial-of-service attack described in `MoreLabels.Hasttbl.create`[29.37]
call `Hashtbl.randomize()` at initialization time before any domains are created.
transformed lazily (one element at a time) rather than eagerly (all elements at once). This also
allows constructing conceptually infinite sequences.

The type `'a Seq.t` is defined as a synonym for `unit -> 'a Seq.node`. This is a function type: therefore, it is opaque. The consumer can **query** a sequence in order to request the next element (if there is one), but cannot otherwise inspect the sequence in any way.

Because it is opaque, the type `'a Seq.t` does *not* reveal whether a sequence is:

* **persistent**, which means that the sequence can be used as many times as desired, producing the same elements every time, just like an immutable list; or

* **ephemeral**, which means that the sequence is not persistent. Querying an ephemeral sequence might have an observable side effect, such as incrementing a mutable counter. As a common special case, an ephemeral sequence can be **affine**, which means that it must be queried at most once.

It also does *not* reveal whether the elements of the sequence are:

* **pre-computed and stored** in memory, which means that querying the sequence is cheap;

* **computed when first demanded and then stored** in memory, which means that querying the sequence once can be expensive, but querying the same sequence again is cheap; or

* **re-computed every time they are demanded**, which may or may not be cheap.

It is up to the programmer to keep these distinctions in mind so as to understand the time and space requirements of sequences.

For the sake of simplicity, most of the documentation that follows is written under the implicit assumption that the sequences at hand are persistent. We normally do not point out *when* or *how many times* each function is invoked, because that would be too verbose. For instance, in the description of `map`, we write: "if `xs` is the sequence `x0; x1; ...` then `map f xs` is the sequence `f x0; f x1; ...`. If we wished to be more explicit, we could point out that the transformation takes place on demand: that is, the elements of `map f xs` are computed only when they are demanded. In other words, the definition `let ys = map f xs` terminates immediately and does not invoke `f`. The function call `f x0` takes place only when the first element of `ys` is demanded, via the function call `ys()`. Furthermore, calling `ys()` twice causes `f x0` to be called twice as well. If one wishes for `f` to be applied at most once to each element of `xs`, even in scenarios where `ys` is queried more than once, then one should use `let ys = memoize (map f xs)`.

As a general rule, the functions that build sequences, such as `map`, `filter`, `scan`, `take`, etc., produce sequences whose elements are computed only on demand. The functions that eagerly consume sequences, such as `is_empty`, `find`, `length`, `iter`, `fold_left`, etc., are the functions that force computation to take place.

When possible, we recommend using sequences rather than dispensers (functions of type `unit -> 'a option` that produce elements upon demand). Whereas sequences can be persistent or ephemeral, dispensers are always ephemeral, and are typically more difficult to work with than sequences. Two conversion functions, `Seq.to_dispenser[28.48]` and `Seq.of_dispenser[28.48]`, are provided.

Since: 4.07

type 'a t = unit -> 'a node
Note that once `Hashtbl.randomize()` was called, there is no way to revert to the non-randomized default behavior of `MoreLabels.Hashtbl.create[29.37]`. This is intentional. Non-randomized hash tables can still be created using `Hashtbl.create ~random:false`.

**Since:** 4.00

`val is_randomized : unit -> bool`

Return `true` if the tables are currently created in randomized mode by default, `false` otherwise.

**Since:** 4.03

`val rebuild : ?random:bool -> ('a, 'b) t -> ('a, 'b) t`

Return a copy of the given hashtable. Unlike `MoreLabels.Hashtbl.copy[29.37]`, `MoreLabels.Hashtbl.rebuild[29.37]` re-hashes all the (key, value) entries of the original table `h`. The returned hash table is randomized if `h` was randomized, or the optional `random` parameter is `true`, or if the default is to create randomized hash tables; see `MoreLabels.Hashtbl.create[29.37]` for more information.

`MoreLabels.Hashtbl.rebuild[29.37]` can safely be used to import a hash table built by an old version of the `MoreLabels.Hashtbl[29.37]` module, then marshaled to persistent storage. After unmarshaling, apply `MoreLabels.Hashtbl.rebuild[29.37]` to produce a hash table for the current version of the `MoreLabels.Hashtbl[29.37]` module.

**Since:** 4.12

```hkl
type statistics = Hashtbl.statistics =
{
    num bindings : int;
```

Number of bindings present in the table. Same value as returned by
`MoreLabels.Hashtbl.length[29.37]`.

`num buckets : int;`

Number of buckets in the table.

`max bucket length : int;`

Maximal number of bindings per bucket.

`bucket_histogram : int array;`

Histogram of bucket sizes. This array `histo` has length `max bucket length + 1`. The value of `histo.(i)` is the number of buckets whose size is `i`.

}

**Since:** 4.00

`val stats : ('a, 'b) t -> statistics`
A sequence `xs` of type `'a t` is a delayed list of elements of type `'a`. Such a sequence is queried by performing a function application `xs()`. This function application returns a node, allowing the caller to determine whether the sequence is empty or nonempty, and in the latter case, to obtain its head and tail.

```hkl
type 'a node =
| Nil
| Cons of 'a * 'a t
```

A node is either `Nil`, which means that the sequence is empty, or `Cons (x, xs)`, which means that `x` is the first element of the sequence and that `xs` is the remainder of the sequence.

## Consuming sequences

The functions in this section consume their argument, a sequence, either partially or completely:

* `is_empty` and `uncons` consume the sequence down to depth 1. That is, they demand the first argument of the sequence, if there is one.

* `iter`, `fold_left`, `length`, etc., consume the sequence all the way to its end. They terminate only if the sequence is finite.

* `for_all`, `exists`, `find`, etc. consume the sequence down to a certain depth, which is a priori unpredictable.

Similarly, among the functions that consume two sequences, one can distinguish two groups:

* `iter2` and `fold_left2` consume both sequences all the way to the end, provided the sequences have the same length.

* `for_all2`, `exists2`, `equal`, `compare` consume the sequences down to a certain depth, which is a priori unpredictable.

The functions that consume two sequences can be applied to two sequences of distinct lengths: in that case, the excess elements in the longer sequence are ignored. (It may be the case that one excess element is demanded, even though this element is not used.)

None of the functions in this section is lazy. These functions are consumers: they force some computation to take place.

```hkl
val is_empty : 'a t -> bool
```

`is_empty xs` determines whether the sequence `xs` is empty.

It is recommended that the sequence `xs` be persistent. Indeed, `is_empty xs` demands the head of the sequence `xs`, so, if `xs` is ephemeral, it may be the case that `xs` cannot be used any more after this call has taken place.

**Since:** 4.14

```hkl
val uncons : 'a t -> ('a * 'a t) option
```
`Hashtbl.stats tbl` returns statistics about the table `tbl`: number of buckets, size of the biggest bucket, distribution of buckets by size.

**Since: 4.00**

## Hash tables and Sequences

`val to_seq : ('a, 'b) t -> ('a * 'b) Seq.t`

Iterate on the whole table. The order in which the bindings appear in the sequence is unspecified. However, if the table contains several bindings for the same key, they appear in reversed order of introduction, that is, the most recent binding appears first. The behavior is not specified if the hash table is modified during the iteration.

**Since: 4.07**

`val to_seq_keys : ('a, 'b) t -> 'a Seq.t`

Same as `Seq.map fst (to_seq m)`

**Since: 4.07**

`val to_seq_values : ('a, 'b) t -> 'b Seq.t`

Same as `Seq.map snd (to_seq m)`

**Since: 4.07**

`val add_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit`

Add the given bindings to the table, using `MoreLabels.Hashtbl.add[29.37]`

**Since: 4.07**

`val replace_seq : ('a, 'b) t -> ('a * 'b) Seq.t -> unit`

Add the given bindings to the table, using `MoreLabels.Hashtbl.replace[29.37]`

**Since: 4.07**

`val of_seq : ('a * 'b) Seq.t -> ('a, 'b) t`

Build a table from the given bindings. The bindings are added in the same order they appear in the sequence, using `MoreLabels.Hashtbl.replace_seq[29.37]`, which means that if two pairs have the same key, only the latest one will appear in the table.

**Since: 4.07**
If `xs` is empty, then `uncons xs` is `None`.

If `xs` is nonempty, then `uncons xs` is `Some (x, ys)` where `x` is the head of the sequence and `ys` its tail.

**Since:** 4.14

`val length : 'a t -> int`

`length xs` is the length of the sequence `xs`.

The sequence `xs` must be finite.

**Since:** 4.14

`val iter : ('a -> unit) -> 'a t -> unit`

`iter f xs` invokes `f x` successively for every element `x` of the sequence `xs`, from left to right.

It terminates only if the sequence `xs` is finite.

`val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc`

`fold_left f _ xs` invokes `f _ x` successively for every element `x` of the sequence `xs`, from left to right.

An accumulator of type `'a` is threaded through the calls to `f`.

It terminates only if the sequence `xs` is finite.

`val iteri : (int -> 'a -> unit) -> 'a t -> unit`

`iteri f xs` invokes `f i x` successively for every element `x` located at index `i` in the sequence `xs`.

It terminates only if the sequence `xs` is finite.

`iteri f xs` is equivalent to `iter (fun (i, x) -> f i x) (zip (ints 0) xs)`.

**Since:** 4.14

`val fold_lefti : ('acc -> int -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc`

`fold_lefti f _ xs` invokes `f _ i x` successively for every element `x` located at index `i` of the sequence `xs`.

An accumulator of type `'b` is threaded through the calls to `f`.

It terminates only if the sequence `xs` is finite.

`fold_lefti f accu xs` is equivalent to `fold_left (fun accu (i, x) -> f accu i x) accu (zip (ints 0) xs)`.

**Since:** 4.14

`val for_all : ('a -> bool) -> 'a t -> bool`

`for_all p xs` determines whether all elements `x` of the sequence `xs` satisfy `p x`.

The sequence `xs` must be finite.

**Since:** 4.14
## Functorial interface

The functorial interface allows the use of specific comparison and hash functions, either for performance/security concerns, or because keys are not hashable/comparable with the polymorphic builtins.

For instance, one might want to specialize a table for integer keys:

```python
module IntHash =
    struct
        type t = int
        let equal i j = i=j
        let hash i = i land max_int
    end

module IntHashtbl = Hashtbl.Make(IntHash)

let h = IntHashtbl.create 17 in
    IntHashtbl.add h 12 "hello"
```

This creates a new module `IntHashtbl`, with a new type `'a IntHashtbl.t` of tables from `int` to `'a`. In this example, `h` contains `string` values so its type is `string IntHashtbl.t`.

Note that the new type `'a IntHashtbl.t` is not compatible with the type (`'a, 'b) `Hashtbl.t` of the generic interface. For example, `Hashtbl.length h` would not type-check, you must use `IntHashtbl.length`.

```python
module type HashedType =
    sig
        type t
        The type of the hashtable keys.
```

```python
val equal : t -> t -> bool
    The equality predicate used to compare keys.
```

```python
val hash : t -> int
    A hashing function on keys. It must be such that if two keys are equal according to `equal`, then they have identical hash values as computed by `hash`. Examples: suitable (`equal`, `hash`) pairs for arbitrary key types include

* `((=), MoreLabels.Hashtbl.HashedType.hash[29.37])` for comparing objects by structure (provided objects do not contain floats)

* `((fun x y -> compare x y = 0), MoreLabels.Hashtbl.HashedType.hash[29.37])` for comparing objects by structure and handling `nan[28.2]` correctly

* `((==), MoreLabels.Hashtbl.HashedType.hash[29.37])` for comparing objects by physical equality (e.g. for mutable or cyclic objects).
val exists : ('a -> bool) -> 'a t -> bool

exists xs p determines whether at least one element x of the sequence xs satisfies p x.

The sequence `xs` must be finite.

Since: 4.14

val find : ('a -> bool) -> 'a t -> 'a option

find p xs returns Some x, where x is the first element of the sequence xs that satisfies p x, if there is such an element.

It returns `None` if there is no such element.

The sequence `xs` must be finite.

Since: 4.14

val find_index : ('a -> bool) -> 'a t -> int option

find_index p xs returns Some i, where i is the index of the first element of the sequence xs that satisfies p x, if there is such an element.

It returns `None` if there is no such element.

The sequence `xs` must be finite.

Since: 5.1

val find_map : ('a -> 'b option) -> 'a t -> 'b option

find_map f xs returns Some y, where x is the first element of the sequence xs such that f x = Some _ , if there is such an element, and where y is defined by f x = Some y.

It returns `None` if there is no such element.

The sequence `xs` must be finite.

Since: 4.14

val find_mapi : (int -> 'a -> 'b option) -> 'a t -> 'b option

Same as `find_map`, but the predicate is applied to the index of the element as first argument (counting from 0), and the element itself as second argument.

The sequence `xs` must be finite.

Since: 5.1

val iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

iter2 f xs ys invokes f x y successively for every pair (x, y) of elements drawn synchronously from the sequences `xs` and `ys`.

If the sequences `xs` and `ys` have different lengths, then iteration stops as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

Iteration terminates only if at least one of the sequences `xs` and `ys` is finite.

`iter2 f xs ys` is equivalent to `iter (fun (x, y) -> f x y) (zip xs ys)`.

Since: 4.14
end

The input signature of the functor `MoreLabels.Hashtbl.Make[29.37]`.

module type S =

sig

type key

type !'a t

val create : int -> 'a t

val clear : 'a t -> unit

val reset : 'a t -> unit

Since: 4.00

val copy : 'a t -> 'a t

val add : 'a t -> key:key -> data:'a -> unit

val remove : 'a t -> key -> unit

val find : 'a t -> key -> 'a

val find_opt : 'a t -> key -> 'a option

Since: 4.05

val find_all : 'a t -> key -> 'a list

val replace : 'a t -> key:key -> data:'a -> unit

val mem : 'a t -> key -> bool

val iter : f:(key:key -> data:'a -> unit) ->
'a t -> unit

val filter_map_inplace :

f:(key:key -> data:'a -> 'a option) ->
'a t -> unit

Since: 4.03

val fold :

f:(key:key -> data:'a -> 'acc -> 'acc) ->
'a t -> init:'acc -> 'acc

val length : 'a t -> int

val stats : 'a t -> MoreLabels.Hashtbl.statistics

Since: 4.00

val to_seq : 'a t -> (key * 'a) Seq.t

Since: 4.07

val to_seq_keys : 'a t -> key Seq.t

Since: 4.07
```hkl
val fold_left2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc
```

`fold_left2 f _ xs ys` invokes `f _ x y` successively for every pair `(x, y)` of elements drawn synchronously from the sequences `xs` and `ys`.

An accumulator of type `'a` is threaded through the calls to `f`.

If the sequences `xs` and `ys` have different lengths, then iteration stops as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

Iteration terminates only if at least one of the sequences `xs` and `ys` is finite.

`fold_left2 f accu xs ys` is equivalent to `fold_left (fun accu (x, y) -> f accu x y) (zip xs ys)`.

**Since:** 4.14

```hkl
val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
```

`for_all2 p xs ys` determines whether all pairs `(x, y)` of elements drawn synchronously from the sequences `xs` and `ys` satisfy `p x y`.

If the sequences `xs` and `ys` have different lengths, then iteration stops as soon as one sequence is exhausted; the excess elements in the other sequence are ignored. In particular, if `xs` or `ys` is empty, then `for_all2 p xs ys` is true. This is where `for_all2` and `equal` differ: `equal eq xs ys` can be true only if `xs` and `ys` have the same length.

At least one of the sequences `xs` and `ys` must be finite.

`for_all2 p xs ys` is equivalent to `for_all (fun b -> b) (map2 p xs ys)`.

**Since:** 4.14

```hkl
val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
```

`exists2 p xs ys` determines whether some pair `(x, y)` of elements drawn synchronously from the sequences `xs` and `ys` satisfies `p x y`.

If the sequences `xs` and `ys` have different lengths, then iteration must stop as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

At least one of the sequences `xs` and `ys` must be finite.

`exists2 p xs ys` is equivalent to `exists (fun b -> b) (map2 p xs ys)`.

**Since:** 4.14

```hkl
val equal : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
```

Provided the function `eq` defines an equality on elements, `equal eq xs ys` determines whether the sequences `xs` and `ys` are pointwise equal.

At least one of the sequences `xs` and `ys` must be finite.

**Since:** 4.14

```hkl
val compare : ('a -> 'b -> int) -> 'a t -> 'b t -> int
```
```hkl
val to_seq_values : 'a t -> 'a Seq.t
```

Since: 4.07

```hkl
val add_seq : 'a t ->
```

(key * 'a) Seq.t -> unit

Since: 4.07

```hkl
val replace_seq : 'a t ->
```

(key * 'a) Seq.t -> unit

Since: 4.07

```hkl
val of_seq : (key * 'a) Seq.t -> 'a t
```

Since: 4.07

end

The output signature of the functor `MoreLabels.Hashtbl.Make[29.37]`.

```hkl
module Make :
```

functor (H : HashedType) -> S with type key = H.t and type 'a t = 'a
`Hashtbl.Make(H).t`

Functor building an implementation of the hashtable structure. The functor `Hashtbl.Make` returns a structure containing a type `key` of keys and a type `'a t` of hash tables associating data of type `'a` to keys of type `key`. The operations perform similarly to those of the generic interface, but use the hashing and equality functions specified in the functor argument `H` instead of generic equality and hashing. Since the hash function is not seeded, the `create` operation of the result structure always returns non-randomized hash tables.

```hkl
module type SeededHashedType =
```

sig

```hkl
type t
```

The type of the hashtable keys.

```hkl
val equal : t ->
```

t -> bool

The equality predicate used to compare keys.

```hkl
val seeded_hash : int -> t -> int
```

A seeded hashing function on keys. The first argument is the seed. It must be the case that if `equal x y` is true, then `seeded_hash seed x = seedHash seed y` for any value of `seed`. A suitable choice for `seeded_hash` is the function `MoreLabels.Hashtbl.seeded_hash[29.37]` below.
end

The input signature of the functor `MoreLabels.Hashtbl.MakeSeeded[29.37]`.

**Since: 4.00**

```python
module type SeededS =
    sig
```

```python
type key

type !'a t

val create : ?random:bool -> int -> 'a t

val clear : 'a t -> unit

val reset : 'a t -> unit

val copy : 'a t -> 'a t

val add : 'a t ->
    key:key -> data:'a -> unit

val remove : 'a t -> key -> unit

val find : 'a t -> key -> 'a

val find_opt : 'a t ->
    key -> 'a option
```

**Since: 4.05**

```python
val find_all : 'a t -> key -> 'a list

val replace : 'a t ->
    key:key -> data:'a -> unit

val mem : 'a t -> key -> bool

val iter : f:(key:key -> data:'a -> unit) ->
    'a t -> unit

val filter_map_inplace :
    f:(key:key -> data:'a -> 'a option) ->
    'a t -> unit
```

**Since: 4.03**

```python
val fold :
    f:(key:key -> data:'a -> 'acc -> 'acc) ->
    'a t -> init:'acc -> 'acc

val length : 'a t -> int

val stats : 'a t -> MoreLabels.Hashtbl.statistics

val to_seq : 'a t ->
    (key * 'a) Seq.t
```

**Since: 4.07**
`repeat x` is the infinite sequence where the element `x` is repeated indefinitely.

`repeat x` is equivalent to `cycle (return x)`.

**Since: 4.14**

`val forever : (unit -> 'a) -> 'a t`

`forever f` is an infinite sequence where every element is produced (on demand) by the function call `f()`.

For instance, `forever Random bool` is an infinite sequence of random bits.

`forever f` is equivalent to `map f (repeat())`.

**Since: 4.14**

`val cycle : 'a t -> 'a t`

`cycle xs` is the infinite sequence that consists of an infinite number of repetitions of the sequence `xs`.

If `xs` is an empty sequence, then `cycle xs` is empty as well.

Consuming (a prefix of) the sequence `cycle xs` once can cause the sequence `xs` to be consumed more than once. Therefore, `xs` must be persistent.

**Since: 4.14**

`val iterate : ('a -> 'a) -> 'a -> 'a t`

`iterate f x` is the infinite sequence whose elements are `x`, `f x`, `f (f x)`, and so on.

In other words, it is the orbit of the function `f`, starting at `x`.

**Since: 4.14**

Transforming sequences

The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.

`val map : ('a -> 'b) -> 'a t -> 'b t`

`map f xs` is the image of the sequence `xs` through the transformation `f`.

If `xs` is the sequence `x0; x1; ...` then `map f xs` is the sequence `f x0; f x1; ...`.

`val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t`

`mapi` is analogous to `map`, but applies the function `f` to an index and an element.

`mapi f xs` is equivalent to `map2 f (ints 0) xs`.

**Since: 4.14**

`val filter : ('a -> bool) -> 'a t -> 'a t`
```hkl
val to_seq_keys : 'a t ->
key Seq.t

Since: 4.07

val to_seq_values : 'a t -> 'a Seq.t

Since: 4.07

val add_seq : 'a t ->
(key * 'a) Seq.t -> unit

Since: 4.07

val replace_seq : 'a t ->
(key * 'a) Seq.t -> unit

Since: 4.07

val of_seq : (key * 'a) Seq.t ->
'a t

Since: 4.07

end
```

The output signature of the functor `MoreLabels.Hashtbl.MakeSeeded[29.37]`.

Since: 4.00

```hkl
module MakeSeeded :
functor (H : SeededHashedType) -> SeededS with type key = H.t and type 'a t
= 'a Hashtbl.MakeSeeded(H) . t
```

Functor building an implementation of the hashtable structure. The functor `Hashtbl.MakeSeeded` returns a structure containing a type `key` of keys and a type `'a t` of hash tables associating data of type `'a` to keys of type `key`. The operations perform similarly to those of the generic interface, but use the seeded hashing and equality functions specified in the functor argument `H` instead of generic equality and hashing. The `create` operation of the result structure supports the `~random` optional parameter and returns randomized hash tables if `~random:true` is passed or if randomization is globally on (see `MoreLabels.Hashtbl.randomize[29.37]`).

Since: 4.00

## The polymorphic hash functions

```hkl
val hash : 'a -> int
```

`Hashtbl.hash` `x` associates a nonnegative integer to any value of any type. It is guaranteed that if `x = y` or `Stdlib comparisons` `x y = 0`, then `hash x = hash y`. Moreover, `hash` always terminates, even on cyclic structures.
`filter` `p xs` is the sequence of the elements `x` of `xs` that satisfy `p x`.

In other words, `filter p xs` is the sequence `xs`, deprived of the elements `x` such that `p x` is false.

`val filter_map : ('a -> 'b option) -> 'a t -> 'b t`

`filter_map` `f xs` is the sequence of the elements `y` such that `f x = Some y`, where `x` ranges over `xs`.

`filter_map` `f xs` is equivalent to `map Option.get (filter Option.is_some (map f xs))`.

`val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t`

If `xs` is a sequence `[x0; x1; x2; ...]`, then `scan f a0 xs` is a sequence of accumulators `[a0; a1; a2; ...]` where `a1` is `f a0 x0`, `a2` is `f a1 x1`, and so on.

Thus, `scan f a0 xs` is conceptually related to `fold_left f a0 xs`. However, instead of performing an eager iteration and immediately returning the final accumulator, it returns a sequence of accumulators.

For instance, `scan (+) 0` transforms a sequence of integers into the sequence of its partial sums.

If `xs` has length `n` then `scan f a0 xs` has length `n+1`.

**Since:** 4.14

`val take : int -> 'a t -> 'a t`

`take` `n xs` is the sequence of the first `n` elements of `xs`.

If `xs` has fewer than `n` elements, then `take n xs` is equivalent to `xs`.

`n` must be nonnegative.

**Since:** 4.14

**Raises:** `Invalid_argument` if `n` is negative.

`val drop : int -> 'a t -> 'a t`

`drop` `n xs` is the sequence `xs`, deprived of its first `n` elements.

If `xs` has fewer than `n` elements, then `drop n xs` is empty.

`n` must be nonnegative.

`drop` is lazy: the first `n+1` elements of the sequence `xs` are demanded only when the first element of `drop n xs` is demanded. For this reason, `drop 1 xs` is not equivalent to `tail xs`, which queries `xs` immediately.

**Since:** 4.14

**Raises:** `Invalid_argument` if `n` is negative.

`val takewhile : ('a -> bool) -> 'a t -> 'a t`
```kotlin
val seeded_hash : int -> 'a -> int
```

A variant of `MoreLabels.Hashtbl.hash` [29.37] that is further parameterized by an integer seed.

**Since:** 4.00

```kotlin
val hash_param : int -> int -> 'a -> int
```

`Hashtbl.hash_param` meaningful `total x` computes a hash value for `x`, with the same properties as for `hash`. The two extra integer parameters `meaningful` and `total` give more precise control over hashing. Hashing performs a breadth-first, left-to-right traversal of the structure `x`, stopping after `meaningful` meaningful nodes were encountered, or `total` nodes (meaningful or not) were encountered. If `total` as specified by the user exceeds a certain value, currently 256, then it is capped to that value. Meaningful nodes are: integers; floating-point numbers; strings; characters; booleans; and constant constructors. Larger values of `meaningful` and `total` means that more nodes are taken into account to compute the final hash value, and therefore collisions are less likely to happen. However, hashing takes longer. The parameters `meaningful` and `total` govern the tradeoff between accuracy and speed. As default choices, `MoreLabels.Hashtbl.hash` [29.37] and `MoreLabels.Hashtbl.seeded_hash` [29.37] take `meaningful = 10` and `total = 100`.

```kotlin
val seeded_hash_param : int -> int -> int -> 'a -> int
```

A variant of `MoreLabels.Hashtbl.hash_param` [29.37] that is further parameterized by an integer seed. Usage: `Hashtbl.seeded_hash_param meaningful total seed x`.

**Since:** 4.00

## Examples

### Basic Example

```kotlin
(* 0...99 *)
let seq = Seq.ints 0 |> Seq.take 100

(* build from Seq.t *)
# let tbl =
    seq
  |> Seq.map (fun x -> x, string_of_int x)
  |> Hashtbl.of_seq
val tbl : (int, string) Hashtbl.t = <abstr>

# Hashtbl.length tbl
- : int = 100
```
`takewhile` `p xs` is the longest prefix of the sequence `xs` where every element `x` satisfies `p x`.

**Since:** 4.14

`val dropwhile : ('a -> bool) -> 'a t -> 'a t`

`dropwhile` `p xs` is the sequence `xs`, deprived of the prefix `takewhile p xs`.

**Since:** 4.14

`val group : ('a -> 'a -> bool) -> 'a t -> 'a t t`

Provided the function `eq` defines an equality on elements, `group eq xs` is the sequence of the maximal runs of adjacent duplicate elements of the sequence `xs`.

Every element of `group eq xs` is a nonempty sequence of equal elements.

The concatenation `concat` (`group eq xs`) is equal to `xs`.

Consuming `group eq xs`, and consuming the sequences that it contains, can cause `xs` to be consumed more than once. Therefore, `xs` must be persistent.

**Since:** 4.14

`val memoize : 'a t -> 'a t`

The sequence `memoize xs` has the same elements as the sequence `xs`.

Regardless of whether `xs` is ephemeral or persistent, `memoize xs` is persistent: even if it is queried several times, `xs` is queried at most once.

The construction of the sequence `memoize xs` internally relies on suspensions provided by the module `Lazy`[28.29]. These suspensions are *not* thread-safe. Therefore, the sequence `memoize xs` must *not* be queried by multiple threads concurrently.

**Since:** 4.14

### exception Forced_twice

This exception is raised when a sequence returned by `Seq once`[28.48] (or a suffix of it) is queried more than once.

**Since:** 4.14

`val once : 'a t -> 'a t`

The sequence `once xs` has the same elements as the sequence `xs`.

Regardless of whether `xs` is ephemeral or persistent, `once xs` is an ephemeral sequence: it can be queried at most once. If it (or a suffix of it) is queried more than once, then the exception `Forced_twice` is raised. This can be useful, while debugging or testing, to ensure that a sequence is consumed at most once.

**Since:** 4.14

**Raises** `Forced_twice` if `once xs`, or a suffix of it, is queried more than once.

`val transpose : 'a t t -> 'a t t`
# Hashtbl.find_opt tbl 32
- : string option = Some "32"

# Hashtbl.find_opt tbl 166
- : string option = None

# Hashtbl.replace tbl 166 "one six six"
- : unit = ()

# Hashtbl.find_opt tbl 166
- : string option = Some "one six six"

# Hashtbl.length tbl
- : int = 101

## Counting Elements

Given a sequence of elements (here, a `Seq.t[29.53]`), we want to count how many times each distinct element occurs in the sequence. A simple way to do this, assuming the elements are comparable and hashable, is to use a hash table that maps elements to their number of occurrences.

Here we illustrate that principle using a sequence of (ascii) characters (type `char`). We use a custom `Char_tbl` specialized for `char`.

# module Char_tbl = Hashtbl.Make(struct
  type t = char
  let equal = Char equal
  let hash = Hashtbl.hash
end)

(* count distinct occurrences of chars in [seq] *)
# let count_chars (seq : char Seq.t) : _ list =
  let counts = Char_tbl.create 16 in
  Seq.iter
  (fun c ->
    let count_c =
      Char_tbl.find_opt counts c
    |> Option.value ~default:0
    in
      Char_tbl.replace counts c (count_c + 1))
  seq;
  (* turn into a list *)
  Char_tbl.fold (fun c n 1 -> (c,n) :: 1) counts []
If `xss` is a matrix (a sequence of rows), then `transpose xss` is the sequence of the columns of the matrix `xss`.

The rows of the matrix `xss` are not required to have the same length.

The matrix `xss` is not required to be finite (in either direction).

The matrix `xss` must be persistent.

**Since:** 4.14

## Combining sequences

`val append : 'a t -> 'a t -> 'a t`

`append xs ys` is the concatenation of the sequences `xs` and `ys`.

Its elements are the elements of `xs`, followed by the elements of `ys`.

**Since:** 4.11

`val concat : 'a t t -> 'a t`

If `xss` is a sequence of sequences, then `concat xss` is its concatenation.

If `xss` is the sequence `xs0; xs1; ...` then `concat xss` is the sequence `xs0 @ xs1 @ ...`.

**Since:** 4.13

`val flat_map : ('a -> 'b t) -> 'a t -> 'b t`

`flat_map f xs` is equivalent to `concat (map f xs)`.

`val concat_map : ('a -> 'b t) -> 'a t -> 'b t`

`concat_map f xs` is equivalent to `concat (map f xs)`.

`concat_map` is an alias for `flat_map`.

**Since:** 4.13

`val zip : 'a t -> 'b t -> ('a * 'b) t`

`zip xs ys` is the sequence of pairs `(x, y)` drawn synchronously from the sequences `xs` and `ys`.

If the sequences `xs` and `ys` have different lengths, then the sequence ends as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.

`zip xs ys` is equivalent to `map2 (fun a b -> (a, b)) xs ys`.

**Since:** 4.14

`val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t`

`map2 f xs ys` is the sequence of the elements `f x y`, where the pairs `(x, y)` are drawn synchronously from the sequences `xs` and `ys`.

If the sequences `xs` and `ys` have different lengths, then the sequence ends as soon as one sequence is exhausted; the excess elements in the other sequence are ignored.
|> List.sort (fun (c1,_) (c2,_) -> Char compares c1 c2)
val count_chars : Char_tbl.key Seq.t -> (Char.t * int) list = <fun>

(* basic seq from a string *)
# let seq = String.to_seq "hello world, and all the camels in it!"
val seq : char Seq.t = <fun>

# count_chars seq
- : (Char.t * int) list =
  [(', 7); ('!', 1); ('', 1); ('a', 3); ('c', 1); ('d', 2); ('e', 3);
   ('h', 2); ('i', 2); ('l', 6); ('m', 1); ('n', 2); ('o', 2); ('r', 1);
   ('s', 1); ('t', 2); ('w', 1)]

(* "abcabcabc..." *)
# let seq2 =
Seq Provided (String to_seq "abc") |> Seq.take 31
val seq2 : char Seq.t = <fun>

# String.of_seq seq2
- : String.t = "abcabcabcabcabcabcabcabcabca"

# count_chars seq2
- : (Char.t * int) list = [('a', 11); ('b', 10); ('c', 10)]

end

module Map :
sig

Association tables over ordered types.

This module implements applicative association tables, also known as finite maps or dictionaries,
given a total ordering function over the keys. All operations over maps are purely applicative
(no side-effects). The implementation uses balanced binary trees, and therefore searching and
insertion take time logarithmic in the size of the map.

For instance:

module IntPairs =
  struct
    type t = int * int
    let compare (x0,y0) (x1,y1) =
      match Stdlib compare x0 x1 with
        0 -> Stdlib compare y0 y1
      | c -> c
  end
`map2 f xs ys` is equivalent to `map (fun (x, y) -> f x y) (zip xs ys)`.

**Since:** 4.14

`val interleave : 'a t -> 'a t -> 'a t`

`interleave xs ys` is the sequence that begins with the first element of `xs`, continues with the first element of `ys`, and so on.

When one of the sequences `xs` and `ys` is exhausted, `interleave xs ys` continues with the rest of the other sequence.

**Since:** 4.14

`val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t`

If the sequences `xs` and `ys` are sorted according to the total preorder `cmp`, then `sorted_merge cmp xs ys` is the sorted sequence obtained by merging the sequences `xs` and `ys`.

For more details on comparison functions, see `Array.sort` [28.2].

**Since:** 4.14

`val product : 'a t -> 'b t -> ('a * 'b) t`

`product xs ys` is the Cartesian product of the sequences `xs` and `ys`.

For every element `x` of `xs` and for every element `y` of `ys`, the pair `(x, y)` appears once as an element of `product xs ys`.

The order in which the pairs appear is unspecified.

The sequences `xs` and `ys` are not required to be finite.

The sequences `xs` and `ys` must be persistent.

**Since:** 4.14

`val map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t`

The sequence `map_product f xs ys` is the image through `f` of the Cartesian product of the sequences `xs` and `ys`.

For every element `x` of `xs` and for every element `y` of `ys`, the element `f x y` appears once as an element of `map_product f xs ys`.

The order in which these elements appear is unspecified.

The sequences `xs` and `ys` are not required to be finite.

The sequences `xs` and `ys` must be persistent.

`map_product f xs ys` is equivalent to `map (fun (x, y) -> f x y) (product xs ys)`.

**Since:** 4.14
```k language
module PairsMap = Map.Make(IntPairs)

let m = PairsMap.(empty |> add (0,1) "hello" |> add (1,0) "world")
```

This creates a new module `PairsMap`, with a new type `'a PairsMap.t` of maps from `int * int` to `'a`. In this example, `m` contains `string` values so its type is `string PairsMap.t`.

```k language
module type OrderedType =
```

```k sig
```

```k type t
```

The type of the map keys.

```k val compare : t -> t -> int
```

A total ordering function over the keys. This is a two-argument function `f` such that `f e1 e2` is zero if the keys `e1` and `e2` are equal, `f e1 e2` is strictly negative if `e1` is smaller than `e2`, and `f e1 e2` is strictly positive if `e1` is greater than `e2`. Example: a suitable ordering function is the generic structural comparison function `compare[28.2]`.

```k end
```

Input signature of the functor `MoreLabels.Map.Make[29.37]`.

```k language
module type S =
```

```k sig
```

### Maps

```k type key
```

The type of the map keys.

```k type !+'a t
```

The type of maps from type `key` to type `'a`.

```k val empty : 'a t
```

The empty map.

```k val add : key:key ->
```

```k data:'a -> 'a t -> 'a t
```

`add ~key ~data m` returns a map containing the same bindings as `m`, plus a binding of `key` to `data`. If `key` was already bound in `m` to a value that is physically equal to `data`, `m` is returned unchanged (the result of the function is then physically equal to `m`). Otherwise, the previous binding of `key` in `m` disappears.

**Before 4.03** Physical equality was not ensured.
## Splitting a sequence into two sequences

`val unzip : ('a * 'b) t -> 'a t * 'b t`

`unzip` transforms a sequence of pairs into a pair of sequences.

`unzip xs` is equivalent to `(map fst xs, map snd xs)`.

Querying either of the sequences returned by `unzip xs` causes `xs` to be queried. Therefore, querying both of them causes `xs` to be queried twice. Thus, `xs` must be persistent and cheap. If that is not the case, use `unzip (memoize xs)`.

**Since:** 4.14

`val split : ('a * 'b) t -> 'a t * 'b t`

`split` is an alias for `unzip`.

**Since:** 4.14

`val partition_map : ('a -> ('b, 'c) Either.t) -> 'a t -> 'b t * 'c t`

`partition_map f xs` returns a pair of sequences `(ys, zs)`, where:

* `ys` is the sequence of the elements `y` such that `f x = Left y`, where `x` ranges over `xs`;

* `zs` is the sequence of the elements `z` such that `f x = Right z`, where `x` ranges over `xs`.

`partition_map f xs` is equivalent to a pair of `filter_map Either.find_left (map f xs)` and `filter_map Either.find_right (map f xs)`.

Querying either of the sequences returned by `partition_map f xs` causes `xs` to be queried. Therefore, querying both of them causes `xs` to be queried twice. Thus, `xs` must be persistent and cheap. If that is not the case, use `partition_map f (memoize xs)`.

**Since:** 4.14

`val partition : ('a -> bool) -> 'a t -> 'a t * 'a t`

`partition p xs` returns a pair of the subsequence of the elements of `xs` that satisfy `p` and the subsequence of the elements of `xs` that do not satisfy `p`.

`partition p xs` is equivalent to `filter p xs, filter (fun x -> not (p x)) xs`.

Consuming both of the sequences returned by `partition p xs` causes `xs` to be consumed twice and causes the function `f` to be applied twice to each element of the list. Therefore, `f` should be pure and cheap. Furthermore, `xs` should be persistent and cheap. If that is not the case, use `partition p (memoize xs)`.

**Since:** 4.14
```hkl
val add_to_list : key:key ->
  data:'a -> 'a list t -> 'a list t
```

```hkl
  add_to_list ~key ~data m is m with key mapped to l such that l is data ::
  Map.find key m if key was bound in m and [data] otherwise.
```

**Since: 5.1**

```hkl
val update : key:key ->
  f:('a option -> 'a option) -> 'a t -> 'a t
```

```hkl
  update ~key ~f m returns a map containing the same bindings as m, except for the
  binding of key. Depending on the value of y where y is f (find_opt key m), the
  binding of key is added, removed or updated. If y is None, the binding is removed if
  it exists; otherwise, if y is Some z then key is associated to z in the resulting map.
  If key was already bound in m to a value that is physically equal to z, m is returned
  unchanged (the result of the function is then physically equal to m).
```

**Since: 4.06**

```hkl
val singleton : key -> 'a -> 'a t
```

```hkl
  singleton x y returns the one-element map that contains a binding y for x.
```

**Since: 3.12**

```hkl
val remove : key -> 'a t -> 'a t
```

```hkl
  remove x m returns a map containing the same bindings as m, except for x which is
  unbound in the returned map. If x was not in m, m is returned unchanged (the result
  of the function is then physically equal to m).
  Before 4.03 Physical equality was not ensured.
```

```hkl
val merge :
  f: (key -> 'a option -> 'b option -> 'c option) ->
    'a t -> 'b t -> 'c t
```

```hkl
  merge ~f m1 m2 computes a map whose keys are a subset of the keys of m1 and of
  m2. The presence of each such binding, and the corresponding value, is determined
  with the function f. In terms of the find_opt operation, we have find_opt x
  (merge f m1 m2) = f x (find_opt x m1) (find_opt x m2) for any key x,
  provided that f x None None = None.
```

**Since: 3.12**

```hkl
val union : f:(key -> 'a -> 'a -> 'a option) ->
  'a t -> 'a t -> 'a t
```

```hkl
  union ~f m1 m2 computes a map whose keys are a subset of the keys of m1 and of
  m2. When the same binding is defined in both arguments, the function f is used to
  combine them. This is a special case of merge: union f m1 m2 is equivalent to
  merge f' m1 m2, where
  * f' _key None None = None
  * f' _key (Some v) None = Some v
  * f' _key None (Some v) = Some v
```
## Converting between sequences and dispensers

A dispenser is a representation of a sequence as a function of type `unit -> 'a option`. Every time this function is invoked, it returns the next element of the sequence. When there are no more elements, it returns `None`. A dispenser has mutable internal state, therefore is ephemeral: the sequence that it represents can be consumed at most once.

```hkl
val of_dis dispenser : (unit -> 'a option) -> 'a t
```

`of_dis dispenser` it is the sequence of the elements produced by the dispenser it. It is an ephemeral sequence: it can be consumed at most once. If a persistent sequence is needed, use `memoize (of_dis dispenser it)`.

**Since:** 4.14

```hkl
val to_dis dispenser : 'a t -> unit -> 'a option
```

`to_dis dispenser xs` is a fresh dispenser on the sequence `xs`.

This dispenser has mutable internal state, which is not protected by a lock; so, it must not be used by several threads concurrently.

**Since:** 4.14

## Sequences of integers

```hkl
val ints : int -> int t
```

`ints i` is the infinite sequence of the integers beginning at `i` and counting up.

**Since:** 4.14

## 28.49 Module Set : Sets over ordered types.

This module implements the set data structure, given a total ordering function over the set elements. All operations over sets are purely applicative (no side-effects). The implementation uses balanced binary trees, and is therefore reasonably efficient: insertion and membership take time logarithmic in the size of the set, for instance.

The `Set.Make[28.49]` functor constructs implementations for any type, given a `compare` function. For instance:

```hkl
module IntPairs =
  struct
    type t = int * int
    let compare (x0,y0) (x1,y1) =
      match Stdlib compare x0 x1 with
        0 -> Stdlib compare y0 y1
      | c -> c
  end
```
* `f` key (Some v1) (Some v2) = `f` key v1 v2

Since: 4.03

`val cardinal : 'a t -> int`

Return the number of bindings of a map.

Since: 3.12

## Bindings

`val bindings : 'a t -> (key * 'a) list`

Return the list of all bindings of the given map. The returned list is sorted in increasing order of keys with respect to the ordering `Ord compares`, where `Ord` is the argument given to `MoreLabels.Map.Make[29.37]`.

Since: 3.12

`val min_bind : 'a t -> key * 'a`

Return the binding with the smallest key in a given map (with respect to the `Ord compares` ordering), or raise `Not_found` if the map is empty.

Since: 3.12

`val min_bind_opt : 'a t -> (key * 'a) option`

Return the binding with the smallest key in the given map (with respect to the `Ord compares` ordering), or `None` if the map is empty.

Since: 4.05

`val max_bind : 'a t -> key * 'a`

Same as `MoreLabels.Map.S.min_bind[29.37]`, but returns the binding with the largest key in the given map.

Since: 3.12

`val max_bind_opt : 'a t -> (key * 'a) option`

Same as `MoreLabels.Map.S.min_bind_opt[29.37]`, but returns the binding with the largest key in the given map.

Since: 4.05

`val choose : 'a t -> key * 'a`

Return one binding of the given map, or raise `Not_found` if the map is empty.

Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

Since: 3.12

`val choose_opt : 'a t -> (key * 'a) option`

Return one binding of the given map, or `None` if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

Since: 4.05
```python
module PairsSet = Set.Make(IntPairs)

let m = PairsSet.(empty |> add (2,3) |> add (5,7) |> add (11,13))
```

This creates a new module `PairsSet`, with a new type `PairsSet.t` of sets of `int * int`.

```python
module type OrderedType =
    sig
        type t
```

The type of the set elements.

A total ordering function over the set elements. This is a two-argument function `f` such that `f e1 e2` is zero if the elements `e1` and `e2` are equal, `f e1 e2` is strictly negative if `e1` is smaller than `e2`, and `f e1 e2` is strictly positive if `e1` is greater than `e2`. Example: a suitable ordering function is the generic structural comparison function `compare[27.2]`.

```python
end

Input signature of the functor Set.Make[28.49].

module type S =
    sig
```

## Sets

### type elt

The type of the set elements.

### type t

The type of sets.

### val empty : t

The empty set.

### val add : elt -> t -> t

`add x s` returns a set containing all elements of `s`, plus `x`. If `x` was already in `s`, `s` is returned unchanged (the result of the function is then physically equal to `s`).

**Before 4.03** Physical equality was not ensured.

### val singleton : elt -> t

`singleton x` returns the one-element set containing only `x`.
## Searching

`val find : key -> 'a t -> 'a`

`find` `x` `m` returns the current value of `x` in `m`, or raises `Not_found` if no binding for `x` exists.

`val find_opt : key -> 'a t -> 'a option`

`find_opt` `x` `m` returns `Some v` if the current value of `x` in `m` is `v`, or `None` if no binding for `x` exists.

**Since:** 4.05

`val find_first : f:(key -> bool) ->`

`'a t -> key * 'a`

`find_first` ~`f m`, where `f` is a monotonically increasing function, returns the binding of `m` with the lowest key `k` such that `f k`, or raises `Not_found` if no such key exists.

For example, `find_first (fun k -> Ord comparisons k x >= 0) m` will return the first binding `k`, `v` of `m` where `Ord comparisons k x >= 0` (intuitively: `k >= x`), or raise `Not_found` if `x` is greater than any element of `m`.

**Since:** 4.05

`val find_first_opt : f:(key -> bool) ->`

`'a t -> (key * 'a) option`

`find_first_opt` ~`f m`, where `f` is a monotonically increasing function, returns an option containing the binding of `m` with the lowest key `k` such that `f k`, or `None` if no such key exists.

**Since:** 4.05

`val find_last : f:(key -> bool) ->`

`'a t -> key * 'a`

`find_last` ~`f m`, where `f` is a monotonically decreasing function, returns the binding of `m` with the highest key `k` such that `f k`, or raises `Not_found` if no such key exists.

**Since:** 4.05

`val find_last_opt : f:(key -> bool) ->`

`'a t -> (key * 'a) option`

`find_last_opt` ~`f m`, where `f` is a monotonically decreasing function, returns an option containing the binding of `m` with the highest key `k` such that `f k`, or `None` if no such key exists.

**Since:** 4.05

## Traversing

`val iter : f:(key:key -> data:'a -> unit) ->`

`'a t -> unit`
```hkl
val remove : elt -> t -> t
```

`remove x s` returns a set containing all elements of `s`, except `x`. If `x` was not in `s`, `s` is returned unchanged (the result of the function is then physically equal to `s`).

**Before 4.03** Physical equality was not ensured.

```hkl
val union : t -> t -> t
```

Set union.

```hkl
val inter : t -> t -> t
```

Set intersection.

```hkl
val disjoint : t -> t -> bool
```

Test if two sets are disjoint.

**Since: 4.08**

```hkl
val diff : t -> t -> t
```

Set difference: `diff s1 s2` contains the elements of `s1` that are not in `s2`.

```hkl
val cardinal : t -> int
```

Return the number of elements of a set.

## Elements

```hkl
val elements : t -> elt list
```

Return the list of all elements of the given set. The returned list is sorted in increasing order with respect to the ordering `Ord comparisons`, where `Ord` is the argument given to `Set.Make[28.49]`.

```hkl
val min_elt : t -> elt
```

Return the smallest element of the given set (with respect to the `Ord comparisons` ordering), or raise `Not_found` if the set is empty.

```hkl
val min_elt_opt : t -> elt option
```

Return the smallest element of the given set (with respect to the `Ord comparisons` ordering), or `None` if the set is empty.

**Since: 4.05**

```hkl
val max_elt : t -> elt
```

Same as `Set.S.min_elt[28.49]`, but returns the largest element of the given set.
`iter ~f m` applies `f` to all bindings in `m`. `f` receives the key as first argument, and the associated value as second argument. The bindings are passed to `f` in increasing order with respect to the ordering over the type of the keys.

**val fold :**
```h
f:(key:key -> data:'a -> 'acc -> 'acc) ->
'a t -> init:'acc -> 'acc
```
**fold ~f m ~init** computes (`f kN dN ... (f k1 d1 init) ...`), where `k1 ... kN` are the keys of all bindings in `m` (in increasing order), and `d1 ... dN` are the associated data.

Transforming

**val map :** `f:('a -> 'b) -> 'a t -> 'b t`

`map ~f m` returns a map with same domain as `m`, where the associated value `a` of all bindings of `m` has been replaced by the result of the application of `f` to `a`. The bindings are passed to `f` in increasing order with respect to the ordering over the type of the keys.

**val mapi :** `f:(key -> 'a -> 'b) ->
'a t -> 'b t`

Same as `MoreLabels.Map.S.map[29.37]`, but the function receives as arguments both the key and the associated value for each binding of the map.

**val filter :** `f:(key -> 'a -> bool) ->
'a t -> 'a t`

`filter ~f m` returns the map with all the bindings in `m` that satisfy predicate `p`. If every binding in `m` satisfies `f`, `m` is returned unchanged (the result of the function is then physically equal to `m`).

**Before 4.03** Physical equality was not ensured.

**Since:** 3.12

**val filter_map :** `f:(key -> 'a -> 'b option) ->
'a t -> 'b t`

`filter_map ~f m` applies the function `f` to every binding of `m`, and builds a map from the results. For each binding (`k`, `v`) in the input map:

* if `f k v` is `None` then `k` is not in the result,

* if `f k v` is `Some v'` then the binding (`k`, `v'`) is in the output map.

For example, the following function on maps whose values are lists

```h
filter_map
    (fun _k li -> match li with [] -> None | _:::tl -> Some tl)
    m
```
`val max_elt_opt : t -> elt option`

Same as `Set.S.min_elt_opt`[28.49], but returns the largest element of the given set.

**Since:** 4.05

`val choose : t -> elt`

Return one element of the given set, or raise `Not_found` if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets.

`val choose_opt : t -> elt option`

Return one element of the given set, or `None` if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets.

**Since:** 4.05

## Searching

`val find : elt -> t -> elt`

`find` `x s` returns the element of `s` equal to `x` (according to `Ord comparisons`), or raise `Not_found` if no such element exists.

**Since:** 4.01

`val find_opt : elt -> t -> elt option`

`find_opt` `x s` returns the element of `s` equal to `x` (according to `Ord comparisons`), or `None` if no such element exists.

**Since:** 4.05

`val find_first : (elt -> bool) -> t -> elt`

`find_first` `f s`, where `f` is a monotonically increasing function, returns the lowest element `e` of `s` such that `f e`, or raises `Not_found` if no such element exists.

For example, `find_first` (`fun e -> Ord comparisons e x >= 0) s` will return the first element `e` of `s` where `Ord comparisons e x >= 0` (intuitively: `e >= x`), or raise `Not_found` if `x` is greater than any element of `s`.

**Since:** 4.05

`val find_first_opt : (elt -> bool) -> t -> elt option`

`find_first_opt` `f s`, where `f` is a monotonically increasing function, returns an option containing the lowest element `e` of `s` such that `f e`, or `None` if no such element exists.

**Since:** 4.05

`val find_last : (elt -> bool) -> t -> elt`
drops all bindings of m whose value is an empty list, and pops the first element of
each value that is non-empty.

Since: 4.11

val partition : f:(key -> 'a -> bool) ->
'a t -> 'a t * 'a t

partition ~f m returns a pair of maps (m1, m2), where m1 contains all the
bindings of m that satisfy the predicate f, and m2 is the map with all the bindings of
m that do not satisfy f.

Since: 3.12

val split : key ->
'a t ->
'a t * 'a option * 'a t

split x m returns a triple (l, data, r), where l is the map with all the bindings of m whose key is strictly less than x; r is the map with all the bindings of m whose key is strictly greater than x; data is None if m contains no binding for x, or Some v if m binds v to x.

Since: 3.12

Predicates and comparisons

val is_empty : 'a t -> bool
Test whether a map is empty or not.

val mem : key -> 'a t -> bool

mem x m returns true if m contains a binding for x, and false otherwise.

val equal : cmp:('a -> 'a -> bool) ->
'a t -> 'a t -> bool

equal ~cmp m1 m2 tests whether the maps m1 and m2 are equal, that is, contain
equal keys and associate them with equal data. cmp is the equality predicate used to
compare the data associated with the keys.

val compare : cmp:('a -> 'a -> int) ->
'a t -> 'a t -> int

Total ordering between maps. The first argument is a total ordering used to
compare data associated with equal keys in the two maps.

val for_all : f:(key -> 'a -> bool) -> 'a t -> bool
for_all ~f m checks if all the bindings of the map satisfy the predicate f.
Since: 3.12

val exists : f:(key -> 'a -> bool) -> 'a t -> bool
exists ~f m checks if at least one binding of the map satisfies the predicate f.
Since: 3.12
`find_last f s`, where `f` is a monotonically decreasing function, returns the highest element `e` of `s` such that `f e`, or raises `Not_found` if no such element exists.

**Since:** 4.05

`val find_last_opt : (elt -> bool) -> t -> elt option`

`find_last_opt f s`, where `f` is a monotonically decreasing function, returns an option containing the highest element `e` of `s` such that `f e`, or `None` if no such element exists.

**Since:** 4.05

## Traversing

`val iter : (elt -> unit) -> t -> unit`

`iter f s` applies `f` in turn to all elements of `s`. The elements of `s` are presented to `f` in increasing order with respect to the ordering over the type of the elements.

`val fold : (elt -> 'acc -> 'acc) -> t -> 'acc -> 'acc`

`fold f s init` computes (`f xN ... (f x2 (f x1 init)) ...`), where `x1 ... xN` are the elements of `s`, in increasing order.

## Transforming

`val map : (elt -> elt) -> t -> t`

`map f s` is the set whose elements are `f a0, f a1... f aN`, where `a0, a1... aN` are the elements of `s`.

The elements are passed to `f` in increasing order with respect to the ordering over the type of the elements.

If no element of `s` is changed by `f`, `s` is returned unchanged. (If each output of `f` is physically equal to its input, the returned set is physically equal to `s`.)

**Since:** 4.04

`val filter : (elt -> bool) -> t -> t`

`filter f s` returns the set of all elements in `s` that satisfy predicate `f`. If `f` satisfies every element in `s`, `s` is returned unchanged (the result of the function is then physically equal to `s`).

**Before 4.03** Physical equality was not ensured.

`val filter_map : (elt -> elt option) -> t -> t`
Converting

val to_list : 'a t -> (key * 'a) list

to_list m is MoreLabels.Map.S.bindings[29.37] m.
Since: 5.1

val of_list : (key * 'a) list -> 'a t

of_list bs adds the bindings of bs to the empty map, in list order (if a key is
bound twice in bs the last one takes over).
Since: 5.1

val to_seq : 'a t -> (key * 'a) Seq.t
Iterate on the whole map, in ascending order of keys
Since: 4.07

val to_rev_seq : 'a t -> (key * 'a) Seq.t
Iterate on the whole map, in descending order of keys
Since: 4.12

val to_seq_from : key ->
'a t -> (key * 'a) Seq.t

to_seq_from k m iterates on a subset of the bindings of m, in ascending order of
keys, from key k or above.
Since: 4.07

val add_seq : (key * 'a) Seq.t ->
'a t -> 'a t

Add the given bindings to the map, in order.
Since: 4.07

val of_seq : (key * 'a) Seq.t -> 'a t
Build a map from the given bindings
Since: 4.07

end

Output signature of the functor MoreLabels.Map.Make[29.37].

module Make :
functor (Ord : OrderedType) -> S with type key = Ord.t and type 'a t = 'a
Map.Make(Ord).t

Functor building an implementation of the map structure given a totally ordered type.

end

module Set :
sig
`filter_map f s` returns the set of all `v` such that `f x = Some v` for some element `x` of `s`.

For example,

`filter_map (fun n -> if n mod 2 = 0 then Some (n / 2) else None) s` is the set of halves of the even elements of `s`.

If no element of `s` is changed or dropped by `f` (if `f x = Some x` for each element `x`), then `s` is returned unchanged: the result of the function is then physically equal to `s`.

**Since:** 4.11

`val partition : (elt -> bool) -> t -> t * t`

`partition f s` returns a pair of sets (`s1`, `s2`), where `s1` is the set of all the elements of `s` that satisfy the predicate `f`, and `s2` is the set of all the elements of `s` that do not satisfy `f`.

`val split : elt -> t -> t * bool * t`

`split x s` returns a triple `(l, present, r)`, where `l` is the set of elements of `s` that are strictly less than `x`; `r` is the set of elements of `s` that are strictly greater than `x`; `present` is `false` if `s` contains no element equal to `x`, or `true` if `s` contains an element equal to `x`.

## Predicates and comparisons

`val is_empty : t -> bool`

Test whether a set is empty or not.

`val mem : elt -> t -> bool`

`mem x s` tests whether `x` belongs to the set `s`.

`val equal : t -> t -> bool`

`equal s1 s2` tests whether the sets `s1` and `s2` are equal, that is, contain equal elements.

`val compare : t -> t -> int`

Total ordering between sets. Can be used as the ordering function for doing sets of sets.

`val subset : t -> t -> bool`

`subset s1 s2` tests whether the set `s1` is a subset of the set `s2`.

`val for_all : (elt -> bool) -> t -> bool`

`for_all f s` checks if all elements of the set satisfy the predicate `f`.

`val exists : (elt -> bool) -> t -> bool`

`exists f s` checks if at least one element of the set satisfies the predicate `f`.
Sets over ordered types.

This module implements the set data structure, given a total ordering function over the set elements. All operations over sets are purely applicative (no side-effects). The implementation uses balanced binary trees, and is therefore reasonably efficient: insertion and membership take time logarithmic in the size of the set, for instance.

The `MoreLabels.Set.Make[29.37]` functor constructs implementations for any type, given a `compare` function. For instance:

```python
module IntPairs =
    struct
        type t = int * int
        let compare (x0,y0) (x1,y1) =
            match Stdlib compares x0 x1 with
                0 -> Stdlib compare y0 y1
            | c -> c
        end

module PairsSet = Set.Make(IntPairs)

let m = PairsSet.(empty |> add (2,3) |> add (5,7) |> add (11,13))
```

This creates a new module `PairsSet`, with a new type `PairsSet.t` of sets of `int * int`.

```python
module type OrderedType =
    sig
        type t
        The type of the set elements.
        val compare : t -> t -> int
        A total ordering function over the set elements. This is a two-argument function f
        such that f e1 e2 is zero if the elements e1 and e2 are equal, f e1 e2 is strictly
        negative if e1 is smaller than e2, and f e1 e2 is strictly positive if e1 is greater
        than e2. Example: a suitable ordering function is the generic structural comparison
        function compare[28.2].
    end

Input signature of the functor MoreLabels.Set.Make[29.37].

module type S =
    sig
```
Converting

val to_list : t -> elt list

to_list s is Set.S[28.49] s.

Since: 5.1

val of_list : elt list -> t

of_list l creates a set from a list of elements. This is usually more efficient than
folding add over the list, except perhaps for lists with many duplicated elements.

Since: 4.02

val to_seq_from : elt -> t -> elt Seq.t

to_seq_from x s iterates on a subset of the elements of s in ascending order, from x or above.

Since: 4.07

val to_seq : t -> elt Seq.t

Iterate on the whole set, in ascending order

Since: 4.07

val to_rev_seq : t -> elt Seq.t

Iterate on the whole set, in descending order

Since: 4.12

val add_seq : elt Seq.t -> t -> t

Add the given elements to the set, in order.

Since: 4.07

val of_seq : elt Seq.t -> t

Build a set from the given bindings

Since: 4.07

end

Output signature of the functor Set.Make[28.49].

module Make :

functor (Ord : OrderedType) -> S with type elt = Ord.t

Functor building an implementation of the set structure given a totally ordered type.
## Sets

**type elt**

The type of the set elements.

**type t**

The type of sets.

**val empty : t**

The empty set.

**val add : elt -> t -> t**

add x s returns a set containing all elements of s, plus x. If x was already in s, s is returned unchanged (the result of the function is then physically equal to s).

**Before 4.03** Physical equality was not ensured.

**val singleton : elt -> t**

singleton x returns the one-element set containing only x.

**val remove : elt -> t -> t**

remove x s returns a set containing all elements of s, except x. If x was not in s, s is returned unchanged (the result of the function is then physically equal to s).

**Before 4.03** Physical equality was not ensured.

**val union : t -> t -> t**

Set union.

**val inter : t -> t -> t**

Set intersection.

**val disjoint : t -> t -> bool**

Test if two sets are disjoint.

**Since: 4.08**

**val diff : t -> t -> t**

Set difference: diff s1 s2 contains the elements of s1 that are not in s2.

**val cardinal : t -> int**

Return the number of elements of a set.

## Elements

**val elements : t -> elt list**

Return the list of all elements of the given set. The returned list is sorted in increasing order with respect to the ordering `Ord compares`, where `Ord` is the argument given to `MoreLabels.Set.Make[29.37]`.
## 28.50 Module Semaphore : Semaphores

A semaphore is a thread synchronization device that can be used to control access to a shared resource.

Two flavors of semaphores are provided: counting semaphores and binary semaphores.

**Since:** 4.12

### Counting semaphores

A counting semaphore is a counter that can be accessed concurrently by several threads. The typical use is to synchronize producers and consumers of a resource by counting how many units of the resource are available.

The two basic operations on semaphores are:

* "release" (also called "V", "post", "up", and "signal"), which increments the value of the counter. This corresponds to producing one more unit of the shared resource and making it available to others.

* "acquire" (also called "P", "wait", "down", and "pend"), which waits until the counter is greater than zero and decrements it. This corresponds to consuming one unit of the shared resource.

module Counting :

sig

type t

The type of counting semaphores.

val make : int -> t

make n returns a new counting semaphore, with initial value n. The initial value n must be nonnegative.

**Raises** Invalid_argument if n < 0

val release : t -> unit

release s increments the value of semaphore s. If other threads are waiting on s, one of them is restarted. If the current value of s is equal to max_int, the value of the semaphore is unchanged and a Sys_error exception is raised to signal overflow.

**Raises** Sys_error if the value of the semaphore would overflow max_int

val acquire : t -> unit

acquire s blocks the calling thread until the value of semaphore s is not zero, then atomically decrements the value of s and returns.

val try_acquire : t -> bool
### `val min_elt`: `t -> elt`

Return the smallest element of the given set (with respect to the `Ord comparisons`), or raise `Not_found` if the set is empty.

### `val min_elt_opt`: `t -> elt` option

Return the smallest element of the given set (with respect to the `Ord comparisons`), or `None` if the set is empty.

**Since:** 4.05

### `val max_elt`: `t -> elt`

Same as `MoreLabels.Set.S.min_elt` [29.37], but returns the largest element of the given set.

### `val max_elt_opt`: `t -> elt` option

Same as `MoreLabels.Set.S.min_elt_opt` [29.37], but returns the largest element of the given set.

**Since:** 4.05

### `val choose`: `t -> elt`

Return one element of the given set, or raise `Not_found` if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets.

### `val choose_opt`: `t -> elt` option

Return one element of the given set, or `None` if the set is empty. Which element is chosen is unspecified, but equal elements will be chosen for equal sets.

**Since:** 4.05

## Searching

### `val find`: `elt -> t -> elt`

`find` `x s` returns the element of `s` equal to `x` (according to `Ord comparisons`), or raise `Not_found` if no such element exists.

**Since:** 4.01

### `val find_opt`: `elt -> t -> elt` option

`find_opt` `x s` returns the element of `s` equal to `x` (according to `Ord comparisons`), or `None` if no such element exists.

**Since:** 4.05

### `val find_first`: `f:(elt -> bool) -> t -> elt`

`find_first` `~f s`, where `f` is a monotonically increasing function, returns the lowest element `e` of `s` such that `f e`, or raises `Not_found` if no such element exists. For example, `find_first` (`fun e -> Ord comparisons e x >= 0`) `s` will return the first element `e` of `s` where `Ord comparisons e x >= 0` (intuitively: `e >= x`), or raise `Not_found` if `x` is greater than any element of `s`.

**Since:** 4.05
`try_acquire` s immediately returns `false` if the value of semaphore `s` is zero. Otherwise, the value of `s` is atomically decremented and `try_acquire` s returns `true`.

`val get_value : t -> int`

`get_value` s returns the current value of semaphore `s`. The current value can be modified at any time by concurrent `Semaphore.Counting.release[28.50]` and `Semaphore.Counting.acquire[28.50]` operations. Hence, the `get_value` operation is racy, and its result should only be used for debugging or informational messages.

end

## Binary semaphores

Binary semaphores are a variant of counting semaphores where semaphores can only take two values, 0 and 1.

A binary semaphore can be used to control access to a single shared resource, with value 1 meaning "resource is available" and value 0 meaning "resource is unavailable".

The "release" operation of a binary semaphore sets its value to 1, and "acquire" waits until the value is 1 and sets it to 0.

A binary semaphore can be used instead of a mutex (see module Mutex[28.36]) when the mutex discipline (of unlocking the mutex from the thread that locked it) is too restrictive. The "acquire" operation corresponds to locking the mutex, and the "release" operation to unlocking it, but "release" can be performed in a thread different than the one that performed the "acquire". Likewise, it is safe to release a binary semaphore that is already available.

module Binary :

sig

type t

The type of binary semaphores.

`val make : bool -> t`

`make b` returns a new binary semaphore. If `b` is `true`, the initial value of the semaphore is 1, meaning "available". If `b` is `false`, the initial value of the semaphore is 0, meaning "unavailable".

`val release : t -> unit`

`release` s sets the value of semaphore `s` to 1, putting it in the "available" state. If other threads are waiting on `s`, one of them is restarted.

`val acquire : t -> unit`

`acquire` s blocks the calling thread until the semaphore `s` has value 1 (is available), then atomically sets it to 0 and returns.

`val try_acquire : t -> bool`
```hkl
val find_first_opt : f:(elt -> bool) ->
  t -> elt option
```

`find_first_opt ~f s`, where `f` is a monotonically increasing function, returns an option containing the lowest element `e` of `s` such that `f e`, or `None` if no such element exists.

**Since:** 4.05

```hkl
val find_last : f:(elt -> bool) ->
  t -> elt
```

`find_last ~f s`, where `f` is a monotonically decreasing function, returns the highest element `e` of `s` such that `f e`, or raises `Not_found` if no such element exists.

**Since:** 4.05

```hkl
val find_last_opt : f:(elt -> bool) ->
  t -> elt option
```

`find_last_opt ~f s`, where `f` is a monotonically decreasing function, returns an option containing the highest element `e` of `s` such that `f e`, or `None` if no such element exists.

**Since:** 4.05

## Traversing

```hkl
val iter : f:(elt -> unit) -> t -> unit
```

`iter ~f s` applies `f` in turn to all elements of `s`. The elements of `s` are presented to `f` in increasing order with respect to the ordering over the type of the elements.

```hkl
val fold : f:(elt -> 'acc -> 'acc) ->
  t -> init:'acc -> 'acc
```

`fold ~f s init` computes `(f xN ... (f x2 (f x1 init))...)`, where `x1 ... xN` are the elements of `s`, in increasing order.

## Transforming

```hkl
val map : f:(elt -> elt) ->
  t -> t
```

`map ~f s` is the set whose elements are `f a0, f a1... f aN`, where `a0, a1... aN` are the elements of `s`.

The elements are passed to `f` in increasing order with respect to the ordering over the type of the elements.

If no element of `s` is changed by `f`, `s` is returned unchanged. (If each output of `f` is physically equal to its input, the returned set is physically equal to `s`.)

**Since:** 4.04

```hkl
val filter : f:(elt -> bool) -> t -> t
```
`try_acquire` s immediately returns `false` if the semaphore `s` has value 0. If `s` has value 1, its value is atomically set to 0 and `try_acquire` s returns `true`.

end

## 28.51 Module Stack : Last-in first-out stacks.

This module implements stacks (LIFOs), with in-place modification.

**Alert unsynchronized_access.** Unsynchronized accesses to stacks are a programming error.

### Unsynchronized accesses

Unsynchronized accesses to a stack may lead to an invalid queue state. Thus, concurrent accesses to stacks must be synchronized (for instance with a `Mutex.t[28.36]`).

type !'a t

The type of stacks containing elements of type `'a`.

**exception Empty**

Raised when `Stack.pop[28.51]` or `Stack.top[28.51]` is applied to an empty stack.

val create : unit -> 'a t

Return a new stack, initially empty.

val push : 'a -> 'a t -> unit

`push` `x` `s` adds the element `x` at the top of stack `s`.

val pop : 'a t -> 'a

`pop` `s` removes and returns the topmost element in stack `s`, or raises `Stack.Empty[28.51]` if the stack is empty.

val pop_opt : 'a t -> 'a option

`pop_opt` `s` removes and returns the topmost element in stack `s`, or returns `None` if the stack is empty.

**Since: 4.08**

val drop : 'a t -> unit

`drop` `s` removes the topmost element in stack `s`, or raises `Stack.Empty[28.51]` if the stack is empty.

**Since: 5.1**

val top : 'a t -> 'a

`top` `s` returns the topmost element in stack `s`, or raises `Stack.Empty[28.51]` if the stack is empty.
`filter ~f s` returns the set of all elements in `s` that satisfy predicate `f`. If `f` satisfies every element in `s`, `s` is returned unchanged (the result of the function is then physically equal to `s`).

**Before 4.03** Physical equality was not ensured.

```hkl
val filter_map : f:(elt -> elt option) ->
    t -> t
```

`filter_map ~f s` returns the set of all `v` such that `f x = Some v` for some element `x` of `s`.

For example,

`filter_map (fun n -> if n mod 2 = 0 then Some (n / 2) else None) s` is the set of halves of the even elements of `s`.

If no element of `s` is changed or dropped by `f` (if `f x = Some x` for each element `x`), then `s` is returned unchanged: the result of the function is then physically equal to `s`.

**Since: 4.11**

```hkl
val partition : f:(elt -> bool) ->
    t -> t * t
```

`partition ~f s` returns a pair of sets (`s1`, `s2`), where `s1` is the set of all the elements of `s` that satisfy the predicate `f`, and `s2` is the set of all the elements of `s` that do not satisfy `f`.

```hkl
val split : elt ->
    t -> t * bool * t
```

`split x s` returns a triple `(l, present, r)`, where `l` is the set of elements of `s` that are strictly less than `x`; `r` is the set of elements of `s` that are strictly greater than `x`; `present` is `false` if `s` contains no element equal to `x`, or `true` if `s` contains an element equal to `x`.

## Predicates and comparisons

```hkl
val is_empty : t -> bool
```

Test whether a set is empty or not.

```hkl
val mem : elt -> t -> bool
```

`mem x s` tests whether `x` belongs to the set `s`.

```hkl
val equal : t -> t -> bool
```

`equal s1 s2` tests whether the sets `s1` and `s2` are equal, that is, contain equal elements.

```hkl
val compare : t -> t -> int
```

Total ordering between sets. Can be used as the ordering function for doing sets of sets.
val top_opt : 'a t -> 'a option

top_opt s returns the topmost element in stack s, or None if the stack is empty.

Since: 4.08

val clear : 'a t -> unit

Discard all elements from a stack.

val copy : 'a t -> 'a t

Return a copy of the given stack.

val is_empty : 'a t -> bool

Return true if the given stack is empty, false otherwise.

val length : 'a t -> int

Return the number of elements in a stack. Time complexity O(1)

val iter : ('a -> unit) -> 'a t -> unit

iter f s applies f in turn to all elements of s, from the element at the top of the stack to
the element at the bottom of the stack. The stack itself is unchanged.

val fold : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

fold f accu s is (f (... (f (accu x1) x2) ...) xn) where x1 is the top of the stack, x2 the second element, and xn the bottom element. The stack is unchanged.

Since: 4.03

Stacks and Sequences

val to_seq : 'a t -> 'a Seq.t

Iterate on the stack, top to bottom. It is safe to modify the stack during iteration.

Since: 4.07

val add_seq : 'a t -> 'a Seq.t -> unit

Add the elements from the sequence on the top of the stack.

Since: 4.07

val of_seq : 'a Seq.t -> 'a t

Create a stack from the sequence.

Since: 4.07
val subset : t -> t -> bool

subset s1 s2 tests whether the set s1 is a subset of the set s2.

val for_all : f:(elt -> bool) -> t -> bool

for_all ~f s checks if all elements of the set satisfy the predicate f.

val exists : f:(elt -> bool) -> t -> bool

exists ~f s checks if at least one element of the set satisfies the predicate f.

Converting

val to_list : t -> elt list

to_list s is MoreLabels.Set.S.element s [29.37] s.

Since: 5.1

val of_list : elt list -> t

of_list l creates a set from a list of elements. This is usually more efficient than
folding add over the list, except perhaps for lists with many duplicated elements.

Since: 4.02

val to_seq_from : elt ->

t -> elt Seq.t

to_seq_from x s iterates on a subset of the elements of s in ascending order, from
x or above.

Since: 4.07

val to_seq : t -> elt Seq.t

Iterate on the whole set, in ascending order

Since: 4.07

val to_rev_seq : t -> elt Seq.t

Iterate on the whole set, in descending order

Since: 4.12

val add_seq : elt Seq.t -> t -> t

Add the given elements to the set, in order.

Since: 4.07

val of_seq : elt Seq.t -> t

Build a set from the given bindings

Since: 4.07

end

Output signature of the functor MoreLabels.Set.Make[29.37].
## 28.52 Module StdLabels: Standard labeled libraries.

This meta-module provides versions of the StdLabels Array[28.52], StdLabels. Bytes[28.52], StdLabels. List[28.52] and StdLabels. String[28.52] modules where function arguments are systematically labeled. It is intended to be opened at the top of source files, as shown below.

```python
open StdLabels

let to_upper = String.map ~f:Char.uppercaseocos
let seq len = List.init ~f:(fun i -> i) ~len
let everything = Array.create_matrix ~dimx:42 ~dimy:42 42
```

module Array :
    ArrayLabels

module Bytes :
    BytesLabels

module List :
    ListLabels

module String :
    StringLabels

## 28.53 Module String: Strings.

A string `s` of length `n` is an indexable and immutable sequence of `n` bytes. For historical reasons these bytes are referred to as characters.

The semantics of string functions is defined in terms of indices and positions. These are depicted and described as follows.

<table><thead><tr><th>positions</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>n-1</th><th>n</th></tr></thead><tbody><tr><th>indices</th><td>0</td><td>1</td><td>2</td><td>3</td><td>...</td><td>n-1</td><td></td></tr></tbody></table>

* An *index* `i` of `s` is an integer in the range `[0; n-1]`. It represents the ith byte (character) of `s` which can be accessed using the constant time string indexing operator `s[i]`.

* A *position* `i` of `s` is an integer in the range `[0; n]`. It represents either the point at the beginning of the string, or the point between two indices, or the point at the end of the string. The ith byte index is between position `i` and `i+1`.

Two integers `start` and `len` are said to define a *valid substring* of `s` if `len >= 0` and `start`, `start`+`len` are positions of `s`.

**Unicode text.** Strings being arbitrary sequences of bytes, they can hold any kind of textual encoding. However the recommended encoding for storing Unicode text in OCaml strings is UTF-8.
```python
module Make :
functor (Ord : OrderedType) -> S with type elt = Ord.t and type t =
Set.Make(Ord).t
```

Functor building an implementation of the set structure given a totally ordered type.

end

## 29.38 Module Mutex : Locks for mutual exclusion.

Mutexes (mutual-exclusion locks) are used to implement critical sections and protect shared mutable data structures against concurrent accesses. The typical use is (if `m` is the mutex associated with the data structure `D`):

```c
Mutex.lock m;
(* Critical section that operates over D *);
Mutex unlock m
```

### type t

The type of mutexes.

### val create : unit -> t

Return a new mutex.

### val lock : t -> unit

Lock the given mutex. Only one thread can have the mutex locked at any time. A thread that attempts to lock a mutex already locked by another thread will suspend until the other thread unlocks the mutex.

**Before 4.12** `Sys_error` was not raised for recursive locking (platform-dependent behaviour)

**Raises** `Sys_error` if the mutex is already locked by the thread calling `Mutex.lock` [29.38].

### val try_lock : t -> bool

Same as `Mutex.lock` [29.38], but does not suspend the calling thread if the mutex is already locked: just return `false` immediately in that case. If the mutex is unlocked, lock it and return `true`.

### val unlock : t -> unit

Unlock the given mutex. Other threads suspended trying to lock the mutex will restart. The mutex must have been previously locked by the thread that calls `Mutex unlock` [29.38].

**Before 4.12** `Sys_error` was not raised when unlocking an unlocked mutex or when unlocking a mutex from a different thread.

**Raises** `Sys_error` if the mutex is unlocked or was locked by another thread.