Module Parallel_sequence.With_length

'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.

length seq returns the number of elements in seq.

unfold ~init ~next ~split_at ~length 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.

length state must return the exact number of elements next state will produce before returning None.

split_at state ~n optionally returns two states s0, s1 such that length s0 = n and the concatenation of the unfoldings of s0 and s1 produces the same elements as the original sequence. split_at must return Some whenever n > 0 && n < length state

zip_exn seq0 seq1 joins an 'a sequence and a 'b sequence into a ('a * 'b) sequence by pairing each element. Raises if the two sequences do not have equal lengths.

mapi seq ~f converts an 'a sequence to a 'b sequence by applying f to each element of seq and its index.

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

foldi parallel seq ~f ~init ~combine folds combine over mapi 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.

findi parallel seq ~f returns the first element of seq, along with its index i, 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.