Abstract

Irregular segmented operations, like scans and reductions.

Synopsis

val segmented_scan [n] 't : (op: t -> t -> t) -> (ne: t) -> (flags: [n]bool) -> (as: [n]t) -> [n]t
val segmented_reduce [n] 't : (op: t -> t -> t) -> (ne: t) -> (flags: [n]bool) -> (as: [n]t) -> *[]t
val replicated_iota [n] : (reps: [n]i64) -> []i64
val segmented_iota [n] : (flags: [n]bool) -> [n]i64
val expand 'a 'b [impl₀] : (sz: a -> i64) -> (get: a -> i64 -> b) -> (arr: [impl₀]a) -> []b
val expand_reduce 'a 'b [impl₀] : (sz: a -> i64) -> (get: a -> i64 -> b) -> (op: b -> b -> b) -> (ne: b) -> (arr: [impl₀]a) -> []b
val expand_outer_reduce 'a 'b [n] : (sz: a -> i64) -> (get: a -> i64 -> b) -> (op: b -> b -> b) -> (ne: b) -> (arr: [n]a) -> [n]b

Description

↑val segmented_scan [n] 't: (op: t -> t -> t) -> (ne: t) -> (flags: [n]bool) -> (as: [n]t) -> [n]t

Segmented scan. Given a binary associative operator op with neutral element ne, computes the inclusive prefix scan of the segments of as specified by the flags array, where true starts a segment and false continues a segment.

↑val segmented_reduce [n] 't: (op: t -> t -> t) -> (ne: t) -> (flags: [n]bool) -> (as: [n]t) -> *[]t

Segmented reduction. Given a binary associative operator op with neutral element ne, computes the reduction of the segments of as specified by the flags array, where true starts a segment and false continues a segment. One value is returned per segment.

↑val replicated_iota [n]: (reps: [n]i64) -> []i64

Replicated iota. Given a repetition array, the function returns an array with each index (starting from 0) repeated according to the repetition array. As an example, replicated_iota [2,3,1] returns the array [0,0,1,1,1,2].

↑val segmented_iota [n]: (flags: [n]bool) -> [n]i64

Segmented iota. Given a flags array, the function returns an array of index sequences, each of which is reset according to the flags array. As an examples, segmented_iota [false,false,false,true,false,false,false] returns the array [0,1,2,0,1,2,3].

↑val expand 'a 'b [impl₀]: (sz: a -> i64) -> (get: a -> i64 -> b) -> (arr: [impl₀]a) -> []b

Generic expansion function. The function expands a source array into a target array given (1) a function that determines, for each source element, how many target elements it expands to and (2) a function that computes a particular target element based on a source element and the target element number associated with the source. As an example, the expression expand (\x->x) (*) [2,3,1] returns the array [0,2,0,3,6,0].

↑val expand_reduce 'a 'b [impl₀]: (sz: a -> i64) -> (get: a -> i64 -> b) -> (op: b -> b -> b) -> (ne: b) -> (arr: [impl₀]a) -> []b

Expansion function equivalent to performing a segmented reduction to the result of a general expansion with a flags vector expressing the beginning of the expanded segments. The function makes use of the intermediate flags vector generated as part of the expansion and the expand_reduce function is therefore more efficient than if a segmented reduction (with an appropriate flags vector) is explicitly followed by a call to expand.

↑val expand_outer_reduce 'a 'b [n]: (sz: a -> i64) -> (get: a -> i64 -> b) -> (op: b -> b -> b) -> (ne: b) -> (arr: [n]a) -> [n]b

Expansion followed by an ''outer segmented reduce'' that ensures that each element in the result array corresponds to expanding and reducing the corresponding element in the source array.