Module Parallel_sequence

'a t represents a finite sequence of independent computations that produce an 'a. These computations are evaluated in parallel upon collecting the sequence into a strict data structure. Parallel sequences are distinguished from normal sequences by supporting the split operation, which divides a sequence into two parts that may be collected in parallel.

The empty sequence.

globalize seq copies a local sequence to the heap.

range ?stride ?start ?stop start_i stop_i is the sequence of integers from start_i to stop_i, stepping by stride. If stride < 0 then we need start_i > stop_i for the result to be nonempty (or start_i >= stop_i in the case where both bounds are inclusive).

init n ~f is a sequence containing f _ i for each i in 0..n-1.

of_iarray i is a sequence containing the contents of the iarray i. This sequence has a known length and may be split in constant time.

append s0 s1 returns a sequence containing the elements of s0 and then the elements of s1.

product_left seq0 seq1 joins an 'a sequence and a 'b sequence into an ('a * 'b) sequence by pairing each element of seq0 with a copy of seq1.

product_right seq0 seq1 joins an 'a sequence and a 'b sequence into an ('a * 'b) sequence by pairing each element of seq1 with a copy of seq0.

map seq ~f converts an 'a sequence to a 'b sequence by applying f to each element of seq.

iter parallel seq ~f applies f to each element of seq in parallel. The order in which f is applied is unspecified and potentially non-deterministic.

fold parallel seq ~f ~init ~combine folds combine over map seq ~f in parallel. combine and init must form a monoid over 'acc: combine must be associative and init () must be a neutral element. The order in which f and combine are applied is unspecified and potentially non-deterministic.

reduce parallel seq ~f reduces seq using f in parallel. f must be associative. If the sequence is empty, reduce returns None. The order in which f is applied is unspecified and potentially non-deterministic.

find parallel seq ~f returns the first element of seq for which f returns true, if it exists. f will always be applied to every element of seq. The order in which f is applied is unspecified and potentially non-deterministic.

to_list seq collects a sequence into a list by evaluating each element in parallel. Requires iterating the sequence sequentially.

to_iarray seq collects a sequence into an iarray by evaluating each element in parallel. If the sequence has a known length, does not require iterating the sequence sequentially.

unfold ~init ~next ~split creates a sequence representing the stream of values produced by recursively applying next to init.

next state returns either Some (a,s), representing the element a and the new state s, or None, representing the end of the sequence.

split state optionally returns two states s0, s1 such that the concatenation of the unfoldings of s0 and s1 produces the same elements as the original sequence. split must return Some whenever the sequence contains more than one element.

concat seqs creates a sequence representing the concatenation of all sequences in seqs. When possible, splitting the resulting sequence is equivalent to splitting the top-level input sequence. Otherwise, splitting separates out only the first element of seqs.

concat_map seq ~f is equivalent to map seq ~f |> concat.

filter_map seq ~f converts an 'a sequence to a 'b sequence containing only the elements of seq such that f returns Some b.

Sequences of type 'a With_length.t are guaranteed to have a known length. When the length is known, collecting the sequence can be more efficient. Note that concat and filter functions are not supported.

of_with_length seq converts a sequence with a known length to a sequence with a potentially unknown length. However, the known length will be preserved when possible, so collecting the sequence may be equally efficient.