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