Module BatEnumSource
Enumeration over abstract collection of elements.
Enumerations are a representation of finite or infinite sequences of elements. In Batteries Included, enumerations are used pervasively, both as a uniform manner of reading and manipulating the contents of a data structure, or as a simple manner of reading or writing sequences of characters, numbers, strings, etc. from/to files, network connections or other inputs/outputs.
Enumerations are typically computed as needed, which allows the definition and manipulation of huge (possibly infinite) sequences. Manipulating an enumeration is a uniform and often comfortable way of extracting subsequences (function filter or operator // et al), converting sequences into other sequences (function map or operators /@ and @/ et al), gathering information (function scanl et al) or performing loops (functions iter and map).
For instance, function BatRandom.enum_int creates an infinite enumeration of random numbers. Combined with // and map, we may turn this into an infinite enumeration of squares of random even numbers: map (fun x -> x * x) ( (Random.enum_int 100) // even )
Similarly, to obtain an enumeration of 50 random integers, we may use take, as follows: take 50 (Random.enum_int 100)
As most data structures in Batteries can be enumerated and built from enumerations, these operations may be used also on lists, arrays, hashtables, etc. When designing a new data structure, it is usually a good idea to allow enumeration and construction from an enumeration.
Note Enumerations are not thread-safe. You should not attempt to access one enumeration from different threads.
A signature for data structures which may be converted to and from enum.
Final functions
These functions consume the enumeration until it ends or an exception is raised by the first argument function.
Sourceval iter : ('a -> unit) -> 'a t -> unit iter f e calls the function f with each elements of e in turn.
Sourceval iter2 : ('a -> 'b -> unit) -> 'a t -> 'b t -> unit iter2 f e1 e2 calls the function f with the next elements of e1 and e2 repeatedly until one of the two enumerations ends.
Sourceval exists : ('a -> bool) -> 'a t -> bool exists f e returns true if there is some x in e such that f x
Sourceval for_all : ('a -> bool) -> 'a t -> bool for_all f e returns true if for every x in e, f x is true
Sourceval fold : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b A general loop on an enumeration.
If e is empty, fold f v e returns v. Otherwise, fold v e returns f (... (f (f v a0) a1) ...) aN where a0,a1..aN are the elements of e. This function may be used, for instance, to compute the sum of all elements of an enumeration e as follows: fold ( + ) 0 e. Eager.
Sourceval reduce : ('a -> 'a -> 'a) -> 'a t -> 'a A simplified version of fold, which uses the first element of the enumeration as a default value.
reduce f e throws Not_found if e is empty, returns its only element if e is a singleton, otherwise f (... (f (f a0 a1) a2)...) aN where a0,a1..aN are the elements of e.
sum returns the sum of the given int enum. If the argument is empty, returns 0. Eager
Sourceval kahan_sum : float t -> float kahan_sum l returns a numerically-accurate sum of the floats of l. See BatArray.fsum for more details.
Sourceval fold2 : ('a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c fold2 is similar to fold but will fold over two enumerations at the same time until one of the two enumerations ends.
Sourceval scanl : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t A variant of fold producing an enumeration of its intermediate values. If e contains x0, x1, ..., scanl f init e is the enumeration containing init, f init x0, f (f init x0) x1... Lazy.
Sourceval scan : ('a -> 'a -> 'a) -> 'a t -> 'a t scan is similar to scanl but without the init value: if e contains x0, x1, x2 ..., scan f e is the enumeration containing x0, f x0 x1, f (f x0 x1) x2...
For instance, scan ( * ) (1 -- 10) will produce an enumeration containing the successive values of the factorial function.
Indexed functions : these functions are similar to previous ones except that they call the function with one additional argument which is an index starting at 0 and incremented after each call to the function.
Sourceval iteri : (int -> 'a -> unit) -> 'a t -> unit Sourceval iter2i : (int -> 'a -> 'b -> unit) -> 'a t -> 'b t -> unit Sourceval foldi : (int -> 'a -> 'b -> 'b) -> 'b -> 'a t -> 'b Sourceval fold2i : (int -> 'a -> 'b -> 'c -> 'c) -> 'c -> 'a t -> 'b t -> 'c Useful functions
Sourceval find : ('a -> bool) -> 'a t -> 'a find f e returns the first element x of e such that f x returns true, consuming the enumeration up to and including the found element.
Since find (eagerly) consumes a prefix of the enumeration, it can be used several times on the same enumeration to find the next element.
Sourceval find_map : ('a -> 'b option) -> 'a t -> 'b find_map f e finds the first element x of e such that f x returns Some r, then returns r. It consumes the enumeration up to and including the found element.
Since find_map (eagerly) consumes a prefix of the enumeration, it can be used several times on the same enumeration to find the next element.
is_empty e returns true if e does not contains any element. Forces at most one element.
peek e returns None if e is empty or Some x where x is the next element of e. The element is not removed from the enumeration.
get e returns None if e is empty or Some x where x is the next element of e, in which case the element is removed from the enumeration.
get_exn e returns the first element of e.
Sourceval push : 'a t -> 'a -> unit push e x will add x at the beginning of e.
junk e removes the first element from the enumeration, if any.
clone e creates a new enumeration that is copy of e. If e is consumed by later operations, the clone will not get affected.
force e forces the application of all lazy functions and the enumeration of all elements, exhausting the enumeration.
An efficient intermediate data structure of enumerated elements is constructed and e will now enumerate over that data structure.
take n e returns the prefix of e of length n, or e itself if n is greater than the length of e
Sourceval drop : int -> 'a t -> unit drop n e removes the first n element from the enumeration, if any.
skip n e removes the first n element from the enumeration, if any, then returns e.
This function has the same behavior as drop but is often easier to compose with, e.g., skip 5 %> take 3 is a new function which skips 5 elements and then returns the next 3 elements.
Sourceval take_while : ('a -> bool) -> 'a t -> 'a t take_while f e produces a new enumeration in which only remain the first few elements x of e such that f x
Sourceval drop_while : ('a -> bool) -> 'a t -> 'a t drop_while p e produces a new enumeration in which only all the first elements such that f e have been junked.
Sourceval span : ('a -> bool) -> 'a t -> 'a t * 'a t span test e produces two enumerations (hd, tl), such that hd is the same as take_while test e and tl is the same as drop_while test e.
Sourceval break : ('a -> bool) -> 'a t -> 'a t * 'a t Negated span. break test e is equivalent to span (fun x -> not (test x)) e
Sourceval group : ('a -> 'b) -> 'a t -> 'a t t group test e divides e into an enumeration of enumerations, where each sub-enumeration is the longest continuous enumeration of elements whose test results are the same.
Enum.group (x -> x mod 2) [1;2;4;1] = [[1];[2;4];[1]]
Enum.group (fun x -> x mod 3) [1;2;4;1] = [[1];[2];[4;1]]
Enum.group (fun s -> s.[0]) ["cat"; "canary"; "dog"; "dodo"; "ant"; "cow"] = [["cat"; "canary"];["dog";"dodo"];["ant"];["cow"]]
Warning: The result of this operation cannot be directly cloned safely; instead, reify to a non-lazy structure and read from that structure multiple times.
Sourceval group_by : ('a -> 'a -> bool) -> 'a t -> 'a t t group_by eq e divides e into an enumeration of enumerations, where each sub-enumeration is the longest continuous enumeration of elements that are equal, as judged by eq.
Warning: The result of this operation cannot be directly cloned safely; instead, reify to a non-lazy structure and read from that structure multiple times.
Sourceval clump : int -> ('a -> unit) -> (unit -> 'b) -> 'a t -> 'b t clump size add get e runs add on size (or less at the end) elements of e and then runs get to produce value for the result enumeration. Useful to convert a char enum into string enum.
Sourceval cartesian_product : 'a t -> 'b t -> ('a * 'b) t cartesian_product e1 e2 computes the cartesian product of e1 and e2. Pairs are enumerated in a non-specified order, but in fair enough an order so that it works on infinite enums (i.e. even then, any pair is eventually returned)
Lazy constructors
These functions are lazy which means that they will create a new modified enumeration without actually enumerating any element until they are asked to do so by the programmer (using one of the functions above).
When the resulting enumerations of these functions are consumed, the underlying enumerations they were created from are also consumed.
Sourceval map : ('a -> 'b) -> 'a t -> 'b t map f e returns an enumeration over (f a0, f a1, ...) where a0,a1... are the elements of e. Lazy.
Sourceval mapi : (int -> 'a -> 'b) -> 'a t -> 'b t mapi is similar to map except that f is passed one extra argument which is the index of the element in the enumeration, starting from 0 : mapi f e returns an enumeration over (f 0 a0, f 1 a1, ...) where a0,a1... are the elements of e.
Sourceval filter : ('a -> bool) -> 'a t -> 'a t filter f e returns an enumeration over all elements x of e such as f x returns true. Lazy.
Note filter is lazy in that it returns a lazy enumeration, but each element in the result is eagerly searched in the input enumeration. Therefore, the access to a given element in the result will diverge if it is preceded, in the input enumeration, by infinitely many false elements (elements on which the predicate p returns false).
Other functions that may drop an unbound number of elements (filter_map, take_while, etc.) have the same behavior.
Sourceval filter_map : ('a -> 'b option) -> 'a t -> 'b t filter_map f e returns an enumeration over all elements x such as f y returns Some x , where y is an element of e.
filter_map works on infinite enumerations; see filter.
append e1 e2 returns an enumeration that will enumerate over all elements of e1 followed by all elements of e2. Lazy.
Note The behavior of appending e to itself or to something derived from e is not specified. In particular, cloning append e e may destroy any sharing between the first and the second argument.
Sourceval prefix_action : (unit -> unit) -> 'a t -> 'a t prefix_action f e will behave as e but guarantees that f () will be invoked exactly once before the current first element of e is read.
If prefix_action f e is cloned, f is invoked only once, during the cloning. If prefix_action f e is counted, f is invoked only once, during the counting.
May be used for signalling that reading starts or for performing delayed evaluations.
Sourceval suffix_action : (unit -> unit) -> 'a t -> 'a t suffix_action f e will behave as e but guarantees that f () will be invoked after the contents of e are exhausted.
If suffix_action f e is cloned, f is invoked only once, when the original enumeration is exhausted. If suffix_action f e is counted, f is only invoked if the act of counting requires a call to force.
May be used for signalling that reading stopped or for performing delayed evaluations.
concat e returns an enumeration over all elements of all enumerations of e.
Sourceval concat_map : ('a -> 'b t) -> 'a t -> 'b t Synonym of Monad.bind, with flipped arguments. concat_map f e is the same as concat (map f e).
Constructors
In this section the word shall denotes a semantic requirement. The correct operation of the functions in this interface are conditional on the client meeting these requirements.
Sourceexception No_more_elements This exception shall be raised by the next function of make or from when no more elements can be enumerated, it shall not be raised by any function which is an argument to any other function specified in the interface.
As a convenience for debugging, this exception may be raised by the count function of make when attempting to count an infinite enum.
The empty enumeration : contains no element
Sourceval make :
next:(unit -> 'a) ->
count:(unit -> int) ->
clone:(unit -> 'a t) ->
'a t This function creates a fully defined enumeration.
- the
next function shall return the next element of the enumeration or raise No_more_elements if the underlying data structure does not have any more elements to enumerate. - the
count function shall return the actual number of remaining elements in the enumeration or may raise Infinite_enum if it is known that the enumeration is infinite. - the
clone function shall create a clone of the enumeration such as operations on the original enumeration will not affect the clone.
For some samples on how to correctly use make, you can have a look at implementation of BatList.enum.
Sourceval from : (unit -> 'a) -> 'a t from next creates an enumeration from the next function. next shall return the next element of the enumeration or raise No_more_elements when no more elements can be enumerated. Since the enumeration definition is incomplete, a call to count will result in a call to force that will enumerate all elements in order to return a correct value.
Sourceval from_while : (unit -> 'a option) -> 'a t from_while next creates an enumeration from the next function. next shall return Some x where x is the next element of the enumeration or None when no more elements can be enumerated. Since the enumeration definition is incomplete, a call to clone or count will result in a call to force that will enumerate all elements in order to return a correct value.
Sourceval from_loop : 'b -> ('b -> 'a * 'b) -> 'a t from_loop data next creates a (possibly infinite) enumeration from the successive results of applying next to data, then to the result, etc. The list ends whenever the function raises BatEnum.No_more_elements.
Sourceval seq : 'a -> ('a -> 'a) -> ('a -> bool) -> 'a t seq init step cond creates a sequence of data, which starts from init, extends by step, until the condition cond fails. E.g. seq 1 ((+) 1) ((>) 100) returns 1, 2, ... 99. If cond init is false, the result is empty.
Sourceval unfold : 'b -> ('b -> ('a * 'b) option) -> 'a t As from_loop, except uses option type to signal the end of the enumeration.
unfold data next creates a (possibly infinite) enumeration from the successive results of applying next to data, then to the result, etc. The enumeration ends whenever the function returns None
Example: Enum.unfold n (fun x -> if x = 1 then None else Some (x, if x land 1 = 1 then 3 * x + 1 else x / 2)) returns the hailstone sequence starting at n.
Sourceval init : int -> (int -> 'a) -> 'a t init n f creates a new enumeration over elements f 0, f 1, ..., f (n-1)
Create an enumeration consisting of exactly one element.
Sourceval repeat : ?times:int -> 'a -> 'a t repeat ~times:n x creates a enum sequence filled with n times of x. It return infinite enum when ~times is absent. It returns empty enum when times <= 0
Sourceval cycle : ?times:int -> 'a t -> 'a t cycle is similar to repeat, except that the content to fill is a subenum rather than a single element. Note that times represents the times of repeating not the length of enum. When ~times is absent the result is an infinite enum.
Sourceval delay : (unit -> 'a t) -> 'a t delay (fun () -> e) produces an enumeration which behaves as e. The enumeration itself will only be computed when consumed.
A typical use of this function is to explore lazily non-trivial data structures, as follows:
type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree let enum_tree = let rec aux = function | Leaf -> BatEnum.empty () | Node (n, l, r) -> BatEnum.append (BatEnum.singleton n) (BatEnum.append (delay (fun () -> aux l)) (delay (fun () -> aux r)))
Sourceval to_object : 'a t -> < next : 'a ; count : int ; clone : 'b > as 'b to_object e returns a representation of e as an object.
Sourceval of_object : < next : 'a ; count : int ; clone : 'b > as 'b -> 'a t of_object e returns a representation of an object as an enumeration
identity : added for consistency with the other data structures
identity : added for consistency with the other data structures
Sourceval combination : ?repeat:bool -> int -> int -> int list t combination n k returns an enumeration over combination of k elements between n distincts elements.
If repeat is true, the combination may contain the same elements many times.
Counting
count e returns the number of remaining elements in e without consuming the enumeration.
Depending of the underlying data structure that is implementing the enumeration functions, the count operation can be costly, and even sometimes can cause a call to force.
Sourceval fast_count : 'a t -> bool For users worried about the speed of count you can call the fast_count function that will give an hint about count implementation. Basically, if the enumeration has been created with make or init or if force has been called on it, then fast_count will return true.
hard_count returns the number of remaining in elements in e, consuming the whole enumeration somewhere along the way. This function is always at least as fast as the fastest of either count or a fold on the elements of t.
This function is useful when you have opened an enumeration for the sole purpose of counting its elements (e.g. the number of lines in a file).
Utilities
Sourceval range : ?until:int -> int -> int t range p until:q creates an enumeration of integers [p, p+1, ..., q]. If until is omitted, the enumeration is not bounded. Behaviour is not-specified once max_int has been reached.
dup stream returns a pair of streams which are identical to stream. Note that stream is a destructive data structure, the point of dup is to return two streams can be used independently.
Sourceval combine : 'a t -> 'b t -> ('a * 'b) t combine transform two streams into a stream of pairs of corresponding elements. If one stream is shorter, excess elements of the longer stream are ignored.
Sourceval uncombine : ('a * 'b) t -> 'a t * 'b t uncombine is the opposite of combine
Sourceval merge : ('a -> 'a -> bool) -> 'a t -> 'a t -> 'a t merge test a b merge the elements from a and b into a single enumeration. At each step, test is applied to the first element xa of a and the first element xb of b to determine which should get first into resulting enumeration. If test xa xb returns true, xa (the first element of a) is used, otherwise xb is used. If a or b runs out of elements, the process will append all elements of the other enumeration to the result.
For example, if a and b are enumerations of integers sorted in increasing order, then merge (<) a b will also be sorted.
Sourceval interleave : 'a t array -> 'a t interleave enums creates a new enumeration from an array of enumerations. The new enumeration first yields the first elements of the enumerations in the supplied order, then second elements, etc. Thus, a sequence [| [x11 ; x12 ; ...] ; [x21 ; x22, ...] , ... [xN1 ; xN2 ; ...] |] becomes [ x11 ; x12 ; ... ; xN1 ; x21 ; x22 ; ... ; xN2 ; x31 ; ... ].
uniq e returns a duplicate of e with repeated values omitted (similar to unix's uniq command). It uses structural equality to compare consecutive elements.
uniqq e behaves as uniq e except it uses physical equality to compare consecutive elements.
Sourceval uniq_by : ('a -> 'a -> bool) -> 'a t -> 'a t uniq_by cmp e behaves as uniq e except it allows to specify a comparison function.
Sourceval switch : ('a -> bool) -> 'a t -> 'a t * 'a t switch test enum splits enum into two enums, where the first enum have all the elements satisfying test, the second enum is opposite. The order of elements in the source enum is preserved.
Sourceval partition : ('a -> bool) -> 'a t -> 'a t * 'a t Sourceval arg_min : ('a -> 'b) -> 'a t -> 'a Sourceval arg_max : ('a -> 'b) -> 'a t -> 'a arg_min f xs returns the x in xs for which f x is minimum. Similarly for arg_max, except it returns the maximum. If multiple values reach the maximum, one of them is returned. (currently the first, but this is not guaranteed)
Example: -5 -- 5 |> arg_min (fun x -> x * x + 6 * x - 5) = -3 Example: List.enum ["cat"; "canary"; "dog"; "dodo"; "ant"; "cow"] |> arg_max String.length = "canary"
Trampolining
Sourceval while_do : ('a -> bool) -> ('a t -> 'a t) -> 'a t -> 'a t while_do cont f e is a loop on e using f as body and cont as condition for continuing.
If e contains elements x0, x1, x2..., then if cont x0 is false, x0 is returned as such and treatment stops. On the other hand, if cont x0 is true, f x0 is returned and the loop proceeds with x1...
Note that f is used as halting condition after the corresponding element has been added to the result stream.
Infix operators
Infix versions of some functions
This module groups together all infix operators so that you can open it without opening the whole batEnum module.
Sourceval (--) : int -> int -> int t Sourceval (--^) : int -> int -> int t Sourceval (--.) : (float * float) -> float -> float t Sourceval (---) : int -> int -> int t Sourceval (--~) : char -> char -> char t Sourceval (//) : 'a t -> ('a -> bool) -> 'a t Sourceval (/@) : 'a t -> ('a -> 'b) -> 'b t Sourceval (@/) : ('a -> 'b) -> 'a t -> 'b t Sourceval (//@) : 'a t -> ('a -> 'b option) -> 'b t Sourceval (@//) : ('a -> 'b option) -> 'a t -> 'b t Monadic operations on Enumerations containing monadic elements
Boilerplate code
Print and consume the contents of an enumeration.
print_at_most pp limit out enum consumes enum to print its elements into out (using pp to print individual elements). At most limit arguments are printed, if more elements are available an ellipsis "..." is added.
Sourceval compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int compare cmp a b compares enumerations a and b by lexicographical order using comparison cmp.
Same as compare but returning a BatOrd.order instead of an integer.
Sourceval equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool equal eq a b returns true when a and b contain the same sequence of elements.
Override modules
The following modules replace functions defined in BatEnum with functions behaving slightly differently but having the same name. This is by design: the functions meant to override the corresponding functions of BatEnum.
Operations on BatEnum without exceptions.