oseq 0.5 · OCaml Package

OSeq: Functional Iterators

type 'a t = 'a Stdlib.Seq.t

type 'a seq = 'a Stdlib.Seq.t

type 'a iter = ('a -> unit) -> unit

type 'a gen = unit -> 'a option

type 'a equal = 'a -> 'a -> bool

type 'a ord = 'a -> 'a -> int

type 'a printer = Stdlib.Format.formatter -> 'a -> unit

val head_exn : 'a t -> 'a

Returns first element, or fails.

raises Invalid_argument
on an empty sequence

since 0.4

val tail_exn : 'a t -> 'a t

Returns list without its first element, or fails.

raises Invalid_argument
on an empty sequence

since 0.4

val repeatedly : (unit -> 'a) -> 'a t

Call the same function an infinite number of times (useful for instance if the function is a random iterator).

Basic combinators

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

Fold on the iterator, tail-recursively.

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

Fold on the iterator, tail-recursively.

since 0.3

val reduce : ('a -> 'a -> 'a) -> 'a t -> 'a

Fold on non-empty iterators.

raises Invalid_argument
on an empty iterator

val unfold_scan : ('b -> 'a -> 'b * 'c) -> 'b -> 'a t -> 'c t

A mix of unfold and scan. The current state is combined with the current element to produce a new state, and an output value of type 'c.

val app : ('a -> 'b) t -> 'a t -> 'b t

Applicative

val fold_map : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t

Lazy fold and map. No iteration is performed now, the function will be called when the result is traversed. The result is an iterator over the successive states of the fold. The final accumulator is discarded. Unlike scan, fold_map does not return the first accumulator.

val flatten : 'a t t -> 'a t

Flatten the iterator of iterators

val app_interleave : ('a -> 'b) t -> 'a t -> 'b t

Same as app but interleaves the values of the function and the argument iterators. See interleave for more details.

since 0.4

val flat_map_interleave : ('a -> 'b t) -> 'a t -> 'b t

flat_map_interleave f seq is similar to flat_map f seq, except that each sub-sequence is interleaved rather than concatenated in order. See interleave for more details.

since 0.4

val mem : ('a -> 'a -> bool) -> 'a -> 'a t -> bool

Is the given element, member of the iterator?

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

n-th element, or Not_found

raises Not_found
if the iterator contains less than n arguments

val take_nth : int -> 'a t -> 'a t

take_nth n g returns every element of g whose index is a multiple of n. For instance take_nth 2 (1--10) |> to_list will return [1;3;5;7;9]

val fold_while : ('a -> 'b -> 'a * [ `Stop | `Continue ]) -> 'a -> 'b t -> 'a

Fold elements until ('a, `Stop) is indicated by the accumulator.

val zip_index : 'a t -> (int * 'a) t

Zip elements with their index in the iterator

val min : lt:('a -> 'a -> bool) -> 'a t -> 'a

Minimum element, according to the given comparison function.

raises Invalid_argument
if the iterator is empty

val max : lt:('a -> 'a -> bool) -> 'a t -> 'a

Maximum element, see min

raises Invalid_argument
if the iterator is empty

val sum : int t -> int

Sum of all elements

Multiple iterators

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

Fold the common prefix of the two iterators

val zip_with : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

Combine common part of the gens (stops when one is exhausted)

Complex combinators

val merge : 'a t t -> 'a t

Pick elements fairly in each sub-iterator. The merge of gens e1, e2, ... picks elements in e1, e2, in e3, e1, e2 .... Once an iterator is empty, it is skipped; when they are all empty, and none remains in the input, their merge is also empty. For instance, merge [1;3;5] [2;4;6] will be, in disorder, 1;2;3;4;5;6.

val intersection : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t

Intersection of two sorted iterators. Only elements that occur in both inputs appear in the output

val round_robin : ?n:int -> 'a t -> 'a t list

Split the iterator into n iterators in a fair way. Elements with index = k mod n with go to the k-th iterator. n default value is 2.

val intersperse : 'a -> 'a t -> 'a t

Put the separator element between all elements of the given iterator

val product3 : 'a t -> 'b t -> 'c t -> ('a * 'b * 'c) t

Cartesian product of three iterators, see product.

since 0.2

val product4 : 'a t -> 'b t -> 'c t -> 'd t -> ('a * 'b * 'c * 'd) t

Cartesian product of four iterators, see product.

since 0.2

val product5 : 
  'a t ->
  'b t ->
  'c t ->
  'd t ->
  'e t ->
  ('a * 'b * 'c * 'd * 'e) t

Cartesian product of five iterators, see product.

since 0.2

val product6 : 
  'a t ->
  'b t ->
  'c t ->
  'd t ->
  'e t ->
  'f t ->
  ('a * 'b * 'c * 'd * 'e * 'f) t

Cartesian product of six iterators, see product.

since 0.2

val product7 : 
  'a t ->
  'b t ->
  'c t ->
  'd t ->
  'e t ->
  'f t ->
  'g t ->
  ('a * 'b * 'c * 'd * 'e * 'f * 'g) t

Cartesian product of seven iterators, see product.

since 0.2

val cartesian_product : 'a t t -> 'a list t

Produce the cartesian product of this sequence of sequences, by returning all the ways of picking one element per sequence. NOTE the order of the returned sequence is unspecified.

This assumes each sub-sequence is finite, and that the main sequence is also finite.

For example:

# cartesian_product [[1;2];[3];[4;5;6]] |> sort =
[[1;3;4];[1;3;5];[1;3;6];[2;3;4];[2;3;5];[2;3;6]];;
# cartesian_product [[1;2];[];[4;5;6]] = [];;
# cartesian_product [[1;2];[3];[4];[5];[6]] |> sort =
[[1;3;4;5;6];[2;3;4;5;6]];;

invariant: cartesian_product l = map_product_l id l.

since 0.2

val map_product_l : ('a -> 'b t) -> 'a t -> 'b list t

map_product_l f l maps each element of l to a list of objects of type 'b using f. We obtain [l1;l2;...;ln] where length l=n and li : 'b list. Then, it returns all the ways of picking exactly one element per li.

since 0.2

val uniq : ('a -> 'a -> bool) -> 'a t -> 'a t

Remove consecutive duplicate elements. Basically this is like fun e -> map List.hd (group e).

val sort : ('a -> 'a -> int) -> 'a t -> 'a t

Sort according to the given comparison function. The iterator must be finite.

val sort_uniq : ('a -> 'a -> int) -> 'a t -> 'a t

Sort and remove duplicates. The iterator must be finite.

val chunks : int -> 'a t -> 'a array t

chunks n e returns a iterator of arrays of length n, composed of successive elements of e. The last array may be smaller than n

val permutations : 'a list -> 'a list t

Permutations of the list.

val combinations : int -> 'a t -> 'a list t

Combinations of given length. The ordering of the elements within each combination is unspecified. Example (ignoring ordering): combinations 2 (1--3) |> to_list = [[1;2]; [1;3]; [2;3]]

val power_set : 'a t -> 'a list t

All subsets of the iterator (in no particular order). The ordering of the elements within each subset is unspecified.

Relational combinators

module type HashedType = Stdlib.Hashtbl.HashedType

A type that can be compared and hashed. invariant: for any x and y, if equal x y then hash x=hash y must hold.

val group_by : 
  (module HashedType with type t = 'key) ->
  project:('a -> 'key) ->
  'a t ->
  ('key * 'a list) t

Group together elements that project onto the same key, ignoring their order of appearance. The order of each resulting list is unspecified.

This function needs to consume the whole input before it can emit anything.

since 0.4

val group_by_fold : 
  (module HashedType with type t = 'key) ->
  project:('a -> 'key) ->
  fold:('b -> 'a -> 'b) ->
  init:'b ->
  'a t ->
  ('key * 'b) t

Group together elements that project onto the same key, folding them into some aggregate of type 'b as they are met. This is the most general version of the "group_by" functions.

This function needs to consume the whole input before it can emit anything.

since 0.4

val group_count : (module HashedType with type t = 'a) -> 'a t -> ('a * int) t

Map each distinct element to its number of occurrences in the whole seq. Similar to group_by_fold hash_key ~project:(fun x->x) ~fold:(fun a _->a+1) ~init:0 seq.

This function needs to consume the whole input before it can emit anything.

since 0.4

val join_by : 
  (module HashedType with type t = 'key) ->
  project_left:('a -> 'key) ->
  project_right:('b -> 'key) ->
  merge:('key -> 'a -> 'b -> 'c option) ->
  'a t ->
  'b t ->
  'c t

join_by ~project_left ~project_right ~merge a b takes every pair of elements x from a and y from b, and if they map onto the same key k by project_left and project_right respectively, and if merge k x y = Some res, then it yields res.

If merge k x y returns None, the combination of values is discarded.

This function works with infinite inputs, it does not have to consume the whole input before yielding elements.

since 0.4

val join_by_fold : 
  (module HashedType with type t = 'key) ->
  project_left:('a -> 'key) ->
  project_right:('b -> 'key) ->
  init:'c ->
  merge:('key -> 'a -> 'b -> 'c -> 'c) ->
  'a t ->
  'b t ->
  'c t

join_by_fold ~project_left ~project_right ~init ~merge a b takes every pair of elements x from a and y from b, and if they map onto the same key k by project_left and project_right respectively, it fold x and y into the accumulator for this key (which starts at init).

This function consumes both inputs entirely before it emits anything.

since 0.4

Basic conversion functions

val of_list : 'a list -> 'a t

Enumerate elements of the list

val to_list : 'a t -> 'a list

non tail-call trasnformation to list, in the same order

val to_rev_list : 'a t -> 'a list

Tail call conversion to list, in reverse order (more efficient)

val to_array : 'a t -> 'a array

Convert the iterator to an array (not very efficient). The iterator must be memoized, as it's traversed twice.

val of_array : ?start:int -> ?len:int -> 'a array -> 'a t

Iterate on (a slice of) the given array

val of_gen : 'a gen -> 'a t

Build a functional iterator from a mutable, imperative generator. The result is properly memoized and can be iterated on several times, as a normal functional value.

val of_gen_transient : 'a gen -> 'a t

Build a functional iterator from a mutable, imperative generator. Note that the resulting iterator is not going to be really functional because the underlying generator can be consumed only once. Use memoize to recover the proper semantics, or use of_gen directly.

val to_gen : 'a t -> 'a gen

Build a mutable iterator that traverses this functional iterator.

since 0.4

val of_string : ?start:int -> ?len:int -> string -> char t

Iterate on bytes of the string

val to_string : char t -> string

Convert into a string

val to_buffer : Stdlib.Buffer.t -> char t -> unit

Traverse the iterator and writes its content to the buffer

val to_iter : 'a t -> 'a iter

Iterate on the whole sequence.

since 0.4

val concat_string : sep:string -> string t -> string

concat_string ~sep s concatenates all strings of i, separated with sep. The iterator must be memoized.

since 0.3

val lines : char t -> string t

Group together chars belonging to the same line

val unlines : string t -> char t

Explode lines into their chars, adding a '\n' after each one

module Infix : sig ... end

include module type of Infix

val (--) : int -> int -> int t

Integer range, inclusive

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

Integer range, exclusive in the right bound

val (>>=) : 'a t -> ('a -> 'b t) -> 'b t

Monadic bind operator

val (>>|) : 'a t -> ('a -> 'b) -> 'b t

Infix map operator

val (>|=) : 'a t -> ('a -> 'b) -> 'b t

Infix map operator

val (<*>) : ('a -> 'b) t -> 'a t -> 'b t

val let+ : 'a t -> ('a -> 'b) -> 'b t

Alias for map

since 0.5

val and+ : 'a t -> 'b t -> ('a * 'b) t

Alias for product

since 0.5

val let* : 'a t -> ('a -> 'b t) -> 'b t

Alias for flat_map

since 0.5

val and* : 'a t -> 'b t -> ('a * 'b) t

Alias for product

since 0.5

val pp : ?sep:string -> 'a printer -> 'a t printer

Pretty print the content of the iterator on a formatter.

Easy interface to Produce Iterators

module Generator : sig ... end

This interface is designed to make it easy to build complex streams of values in a way that resembles Python's generators (using "yield").

module IO : sig ... end

module type MONAD = sig ... end

module Traverse (M : MONAD) : sig ... end

include module type of Stdlib.Seq
  with type 'a node = 'a Stdlib.Seq.node
   and type 'a t := 'a t

type !'a1 node = 'a Stdlib.Seq.node =

| Nil
| Cons of 'a0 * 'a0 t

val is_empty : 'a t -> bool

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

val length : 'a t -> int

val iter : ('a -> unit) -> 'a t -> unit

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

val iteri : (int -> 'a -> unit) -> 'a t -> unit

val fold_lefti : ('acc -> int -> 'a -> 'acc) -> 'acc -> 'a t -> 'acc

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

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

val find : ('a -> bool) -> 'a t -> 'a option

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

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

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

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

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

val for_all2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

val exists2 : ('a -> 'b -> bool) -> 'a t -> 'b t -> bool

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

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

val empty : 'a t

val return : 'a -> 'a t

val cons : 'a -> 'a t -> 'a t

val init : int -> (int -> 'a) -> 'a t

val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t

val repeat : 'a -> 'a t

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

val cycle : 'a t -> 'a t

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

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

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t

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

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

val scan : ('b -> 'a -> 'b) -> 'b -> 'a t -> 'b t

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

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

val take_while : ('a -> bool) -> 'a t -> 'a t

val drop_while : ('a -> bool) -> 'a t -> 'a t

val group : ('a -> 'a -> bool) -> 'a t -> 'a t t

val memoize : 'a t -> 'a t

exception Forced_twice

val once : 'a t -> 'a t

val transpose : 'a t t -> 'a t t

val append : 'a t -> 'a t -> 'a t

val concat : 'a t t -> 'a t

val flat_map : ('a -> 'b t) -> 'a t -> 'b t

val concat_map : ('a -> 'b t) -> 'a t -> 'b t

val zip : 'a t -> 'b t -> ('a * 'b) t

val map2 : ('a -> 'b -> 'c) -> 'a t -> 'b t -> 'c t

val interleave : 'a t -> 'a t -> 'a t

val sorted_merge : ('a -> 'a -> int) -> 'a t -> 'a t -> 'a t

val product : 'a t -> 'b t -> ('a * 'b) t

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

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

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

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

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

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

val to_dispenser : 'a t -> unit -> 'a option

val ints : int -> int t

package oseq

Basic combinators

Multiple iterators

Complex combinators

Relational combinators

Basic conversion functions

Easy interface to Produce Iterators