package containers

  1. Overview
  2. Docs
package containers
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module CCSeqSource

Helpers for the standard Seq type

See oseq for a richer API.

  • since 3.0
Sourcetype 'a iter = ('a -> unit) -> unit
Sourcetype 'a gen = unit -> 'a option
Sourcetype 'a equal = 'a -> 'a -> bool
Sourcetype 'a ord = 'a -> 'a -> int
Sourcetype 'a printer = Format.formatter -> 'a -> unit

Basics

include module type of Seq
Sourcetype 'a t = unit -> 'a node

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.

Sourceand +'a node =
  1. | Nil
  2. | 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.

Sourceval 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
Sourceval 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

Constructing sequences

The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.

Transforming sequences

The functions in this section are lazy: that is, they return sequences whose elements are computed only when demanded.

Sourceexception Forced_twice

This exception is raised when a sequence returned by once (or a suffix of it) is queried more than once.

  • since 4.14
Sourceval 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.

  • raises Forced_twice

    if once xs, or a suffix of it, is queried more than once.

  • since 4.14
Sourceval transpose : 'a t t -> 'a t t

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

Splitting a sequence into two sequences

Sourceval 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
Sourceval 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

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.

Sourceval of_dispenser : (unit -> 'a option) -> 'a t

of_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_dispenser it).

  • since 4.14
Sourceval to_dispenser : 'a t -> unit -> 'a option

to_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

Sourceval ints : int -> int t

ints i is the infinite sequence of the integers beginning at i and counting up.

  • since 4.14
Sourceval nil : 'a t
Sourceval empty : 'a t
Sourceval cons : 'a -> 'a t -> 'a t
Sourceval singleton : 'a -> 'a t
Sourceval init : int -> (int -> 'a) -> 'a t

init n f corresponds to the sequence f 0; f 1; ...; f (n-1).

  • since 3.10
Sourceval repeat : ?n:int -> 'a -> 'a t

repeat ~n x repeats x n times then stops. If n is omitted, then x is repeated forever.

Sourceval forever : (unit -> 'a) -> 'a t

forever f corresponds to the infinit sequence containing all the f ().

  • since 3.10
Sourceval cycle : 'a t -> 'a t

Cycle through the iterator infinitely. The iterator shouldn't be empty.

Sourceval iterate : ('a -> 'a) -> 'a -> 'a t

iterate f a corresponds to the infinit sequence containing a, f a, f (f a), ...]

  • since 3.10
Sourceval unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t

unfold f acc calls f acc and:

  • if f acc = Some (x, acc'), yield x, continue with unfold f acc'.
  • if f acc = None, stops.
Sourceval is_empty : 'a t -> bool

is_empty xs checks in the sequence xs is empty

Sourceval head : 'a t -> 'a option

Head of the list.

Sourceval head_exn : 'a t -> 'a

Unsafe version of head.

Sourceval tail : 'a t -> 'a t option

Tail of the list.

Sourceval tail_exn : 'a t -> 'a t

Unsafe version of tail.

Sourceval uncons : 'a t -> ('a * 'a t) option

uncons xs return None if xs is empty other

  • since 3.10
Sourceval equal : 'a equal -> 'a t equal

Equality step by step. Eager.

Sourceval compare : 'a ord -> 'a t ord

Lexicographic comparison. Eager.

Sourceval fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

Fold on values.

Sourceval fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

Alias for fold

Sourceval foldi : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold_lefti f init xs applies f acc i x where acc is the result of the previous computation or init for the first one, i is the index in the sequence (starts at 0) and x is the element of the sequence.

  • since 3.10
Sourceval fold_lefti : ('a -> int -> 'b -> 'a) -> 'a -> 'b t -> 'a

Alias of foldi.

  • since 3.10
Sourceval iter : ('a -> unit) -> 'a t -> unit
Sourceval iteri : (int -> 'a -> unit) -> 'a t -> unit

Iterate with index (starts at 0).

Sourceval length : _ t -> int

Number of elements in the list. Will not terminate if the list if infinite: use (for instance) take to make the list finite if necessary.

Sourceval take : int -> 'a t -> 'a t
Sourceval take_while : ('a -> bool) -> 'a t -> 'a t
Sourceval drop : int -> 'a t -> 'a t
Sourceval drop_while : ('a -> bool) -> 'a t -> 'a t
Sourceval map : ('a -> 'b) -> 'a t -> 'b t
Sourceval mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

Map with index (starts at 0).

Sourceval fmap : ('a -> 'b option) -> 'a t -> 'b t
Sourceval filter : ('a -> bool) -> 'a t -> 'a t
Sourceval append : 'a t -> 'a t -> 'a t
Sourceval product_with : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Fair product of two (possibly infinite) lists into a new list. Lazy. The first parameter is used to combine each pair of elements.

Sourceval map_product : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Alias of product_with.

  • since 3.10
Sourceval product : 'a t -> 'b t -> ('a * 'b) t

Specialization of product_with producing tuples.

Sourceval group : 'a equal -> 'a t -> 'a t t

group eq l groups together consecutive elements that satisfy eq. Lazy. For instance group (=) [1;1;1;2;2;3;3;1] yields [1;1;1]; [2;2]; [3;3]; [1].

Sourceval uniq : 'a equal -> 'a t -> 'a t

uniq eq l returns l but removes consecutive duplicates. Lazy. In other words, if several values that are equal follow one another, only the first of them is kept.

Sourceval for_all : ('a -> bool) -> 'a t -> bool

for_all p [a1; ...; an] checks if all elements of the sequence satisfy the predicate p. That is, it returns (p a1) && ... && (p an) for a non-empty list and true if the sequence is empty. It consumes the sequence until it finds an element not satisfying the predicate.

  • since 3.3
Sourceval exists : ('a -> bool) -> 'a t -> bool

exists p [a1; ...; an] checks if at least one element of the sequence satisfies the predicate p. That is, it returns (p a1) || ... || (p an) for a non-empty sequence and false if the list is empty. It consumes the sequence until it finds an element satisfying the predicate.

  • since 3.3
Sourceval find : ('a -> bool) -> 'a t -> 'a option

find p [a1; ...; an] return Some ai for the first ai satisfying the predicate p and return None otherwise.

  • since 3.10
Sourceval find_map : ('a -> 'b option) -> 'a t -> 'b option

find f [a1; ...; an] return Some (f ai) for the first ai such that f ai = Some _ and return None otherwise.

  • since 3.10
Sourceval scan : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a t

scan f init xs is the sequence containing the intermediate result of fold f init xs.

  • since 3.10
Sourceval flat_map : ('a -> 'b t) -> 'a t -> 'b t
Sourceval concat_map : ('a -> 'b t) -> 'a t -> 'b t

Aliass of flat_map

  • since 3.10
Sourceval filter_map : ('a -> 'b option) -> 'a t -> 'b t
Sourceval flatten : 'a t t -> 'a t
Sourceval concat : 'a t t -> 'a t

Alias of flatten.

  • since 3.10
Sourceval range : int -> int -> int t
Sourceval (--) : int -> int -> int t

a -- b is the range of integers containing a and b (therefore, never empty).

Sourceval (--^) : int -> int -> int t

a -- b is the integer range from a to b, where b is excluded.

Operations on two Collections

Sourceval fold2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc

Fold on two collections at once. Stop at soon as one of them ends.

Sourceval fold_left2 : ('acc -> 'a -> 'b -> 'acc) -> 'acc -> 'a t -> 'b t -> 'acc

Alias for fold2.

  • since 3.10
Sourceval map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Map on two collections at once. Stop as soon as one of the arguments is exhausted.

Sourceval iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit

Iterate on two collections at once. Stop as soon as one of them ends.

Sourceval for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
Sourceval exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool
Sourceval merge : 'a ord -> 'a t -> 'a t -> 'a t

Merge two sorted iterators into a sorted iterator.

Sourceval sorted_merge : 'a ord -> 'a t -> 'a t -> 'a t

Alias of merge.

  • since 3.10
Sourceval zip : 'a t -> 'b t -> ('a * 'b) t

Combine elements pairwise. Stop as soon as one of the lists stops.

Sourceval unzip : ('a * 'b) t -> 'a t * 'b t

Split each tuple in the list.

Sourceval split : ('a * 'b) t -> 'a t * 'b t

Alias of unzip.

  • since 3.10
Sourceval zip_i : 'a t -> (int * 'a) t

zip_i seq zips the index of each element with the element itself.

  • since 3.8

Misc

Sourceval sort : cmp:'a ord -> 'a t -> 'a t

Eager sort. Require the iterator to be finite. O(n ln(n)) time and space.

Sourceval sort_uniq : cmp:'a ord -> 'a t -> 'a t

Eager sort that removes duplicate values. Require the iterator to be finite. O(n ln(n)) time and space.

Sourceval memoize : 'a t -> 'a t

Avoid recomputations by caching intermediate results.

Fair Combinations

Sourceval interleave : 'a t -> 'a t -> 'a t

Fair interleaving of both streams.

Sourceval fair_flat_map : ('a -> 'b t) -> 'a t -> 'b t

Fair version of flat_map.

Sourceval fair_app : ('a -> 'b) t -> 'a t -> 'b t

Fair version of (<*>).

Implementations

Sourceval return : 'a -> 'a t
Sourceval pure : 'a -> 'a t
Sourceval (>>=) : 'a t -> ('a -> 'b t) -> 'b t
Sourceval (>|=) : 'a t -> ('a -> 'b) -> 'b t
Sourceval (<*>) : ('a -> 'b) t -> 'a t -> 'b t
Sourceval (>>-) : 'a t -> ('a -> 'b t) -> 'b t

Infix version of fair_flat_map.

Sourceval (<.>) : ('a -> 'b) t -> 'a t -> 'b t

Infix version of fair_app.

Infix operators

Sourcemodule Infix : sig ... end
Sourcemodule type MONAD = sig ... end
Sourcemodule Traverse (M : MONAD) : sig ... end

Conversions

Sourceval of_list : 'a list -> 'a t
Sourceval to_list : 'a t -> 'a list

Gather all values into a list.

Sourceval of_array : 'a array -> 'a t

Iterate on the array.

Sourceval to_array : 'a t -> 'a array

Convert into array.

Sourceval to_rev_list : 'a t -> 'a list

Convert to a list, in reverse order. More efficient than to_list.

Sourceval to_iter : 'a t -> 'a iter
Sourceval to_gen : 'a t -> 'a gen
Sourceval of_gen : 'a gen -> 'a t

of_gen g consumes the generator and caches intermediate results.

Sourceval of_string : string -> char t

Iterate on characters.

  • since 3.7

IO

Sourceval pp : ?pp_start:unit printer -> ?pp_stop:unit printer -> ?pp_sep:unit printer -> 'a printer -> 'a t printer

pp ~pp_start ~pp_stop ~pp_sep pp_item ppf s formats the sequence s on ppf. Each element is formatted with pp_item, pp_start is called at the beginning, pp_stop is called at the end, pp_sep is called between each elements. By defaults pp_start and pp_stop does nothing and pp_sep defaults to (fun out -> Format.fprintf out ",@ ").