## Abstract

Various Second-Order Array Combinators that are operationally parallel in a way that can be exploited by the compiler.

The functions here are recognised specially by the compiler (or
built on those that are). The asymptotic work and
span
is provided for each function, but note that this easily hides very
substantial constant factors. For example, `scan`

is *much*
slower than `reduce`

, although they have the same asymptotic
complexity.

**Higher-order complexity**

Specifying the time complexity of higher-order functions is tricky
because it depends on the functional argument. We use the informal
convention that *W(f)* denotes the largest (asymptotic) *work* of
function *f*, for the values it may be applied to. Similarly,
*S(f)* denotes the largest span. See this Wikipedia
article
for a general introduction to these constructs.

**Reminder on terminology**

A function `op`

is said to be *associative* if

```
(x `op` y) `op` z == x `op` (y `op` z)
```

for all `x`

, `y`

, `z`

. Similarly, it is *commutative* if

```
x `op` y == y `op` x
```

The value `o`

is a *neutral element* if

```
x `op` o == o `op` x == x
```

for any `x`

.

## Synopsis

val map | 'a [n] 'x : | (f: a -> x) -> (as: [n]a) -> *[n]x |

val map1 | 'a [n] 'x : | (f: a -> x) -> (as: [n]a) -> *[n]x |

val map2 | 'a 'b [n] 'x : | (f: a -> b -> x) -> (as: [n]a) -> (bs: [n]b) -> *[n]x |

val map3 | 'a 'b 'c [n] 'x : | (f: a -> b -> c -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> *[n]x |

val map4 | 'a 'b 'c 'd [n] 'x : | (f: a -> b -> c -> d -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> (ds: [n]d) -> *[n]x |

val map5 | 'a 'b 'c 'd 'e [n] 'x : | (f: a -> b -> c -> d -> e -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> (ds: [n]d) -> (es: [n]e) -> *[n]x |

val reduce | [n] 'a : | (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> a |

val reduce_comm | [n] 'a : | (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> a |

val hist | 'a [n] : | (op: a -> a -> a) -> (ne: a) -> (k: i64) -> (is: [n]i64) -> (as: [n]a) -> *[k]a |

val reduce_by_index | 'a [k] [n] : | (dest: *[k]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n]i64) -> (as: [n]a) -> *[k]a |

val reduce_by_index_2d | 'a [k] [n] [m] : | (dest: *[k][m]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n](i64, i64)) -> (as: [n]a) -> *[k][m]a |

val reduce_by_index_3d | 'a [k] [n] [m] [l] : | (dest: *[k][m][l]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n](i64, i64, i64)) -> (as: [n]a) -> *[k][m][l]a |

val scan | [n] 'a : | (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> *[n]a |

val filter | [n] 'a : | (p: a -> bool) -> (as: [n]a) -> *[]a |

val partition | [n] 'a : | (p: a -> bool) -> (as: [n]a) -> ?[k].([k]a, [n - k]a) |

val partition2 | [n] 'a : | (p1: a -> bool) -> (p2: a -> bool) -> (as: [n]a) -> ?[k][l].([k]a, [l]a, [n - k - l]a) |

val all | [n] 'a : | (f: a -> bool) -> (as: [n]a) -> bool |

val any | [n] 'a : | (f: a -> bool) -> (as: [n]a) -> bool |

val spread | 't [n] : | (k: i64) -> (x: t) -> (is: [n]i64) -> (vs: [n]t) -> *[k]t |

val scatter | 't [k] [n] : | (dest: *[k]t) -> (is: [n]i64) -> (vs: [n]t) -> *[k]t |

val scatter_2d | 't [k] [n] [l] : | (dest: *[k][n]t) -> (is: [l](i64, i64)) -> (vs: [l]t) -> *[k][n]t |

val scatter_3d | 't [k] [n] [o] [l] : | (dest: *[k][n][o]t) -> (is: [l](i64, i64, i64)) -> (vs: [l]t) -> *[k][n][o]t |

## Description

- ↑val map 'a [n] 'x: (f: a -> x) -> (as: [n]a) -> *[n]x
Apply the given function to each element of an array.

**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val map1 'a [n] 'x: (f: a -> x) -> (as: [n]a) -> *[n]x
Apply the given function to each element of a single array.

**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val map2 'a 'b [n] 'x: (f: a -> b -> x) -> (as: [n]a) -> (bs: [n]b) -> *[n]x
As

`map1`

, but with one more array.**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val map3 'a 'b 'c [n] 'x: (f: a -> b -> c -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> *[n]x
As

`map2`

, but with one more array.**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val map4 'a 'b 'c 'd [n] 'x: (f: a -> b -> c -> d -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> (ds: [n]d) -> *[n]x
As

`map3`

, but with one more array.**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val map5 'a 'b 'c 'd 'e [n] 'x: (f: a -> b -> c -> d -> e -> x) -> (as: [n]a) -> (bs: [n]b) -> (cs: [n]c) -> (ds: [n]d) -> (es: [n]e) -> *[n]x
As

`map3`

, but with one more array.**Work:***O(n ✕ W(f))***Span:***O(S(f))*- ↑val reduce [n] 'a: (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> a
Reduce the array

`as`

with`op`

, with`ne`

as the neutral element for`op`

. The function`op`

must be associative. If it is not, the return value is unspecified. If the value returned by the operator is an array, it must have the exact same size as the neutral element, and that must again have the same size as the elements of the input array.**Work:***O(n ✕ W(op))***Span:***O(log(n) ✕ W(op))*Note that the complexity implies that parallelism in the combining operator will

*not*be exploited.- ↑val reduce_comm [n] 'a: (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> a
As

`reduce`

, but the operator must also be commutative. This is potentially faster than`reduce`

. For simple built-in operators, like addition, the compiler already knows that the operator is commutative, so plain`reduce`

will work just as well.**Work:***O(n ✕ W(op))***Span:***O(log(n) ✕ W(op))*- ↑val hist 'a [n]: (op: a -> a -> a) -> (ne: a) -> (k: i64) -> (is: [n]i64) -> (as: [n]a) -> *[k]a
`h = hist op ne k is as`

computes a generalised`k`

-bin histogram`h`

, such that`h[i]`

is the sum of those values`as[j]`

for which`is[j]==i`

. The summation is done with`op`

, which must be a commutative and associative function with neutral element`ne`

. If a bin has no elements, its value will be`ne`

.**Work:***O(k + n ✕ W(op))***Span:***O(n ✕ W(op))*in the worst case (all updates to same position), but*O(W(op))*in the best case.In practice, linear span only occurs if

*k*is also very large.- ↑val reduce_by_index 'a [k] [n]: (dest: *[k]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n]i64) -> (as: [n]a) -> *[k]a
Like

`hist`

, but with initial contents of the histogram, and the complexity is proportional only to the number of input elements, not the total size of the histogram.**Work:***O(n ✕ W(op))***Span:***O(n ✕ W(op))*in the worst case (all updates to same position), but*O(W(op))*in the best case.In practice, linear span only occurs if

*k*is also very large.- ↑val reduce_by_index_2d 'a [k] [n] [m]: (dest: *[k][m]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n](i64, i64)) -> (as: [n]a) -> *[k][m]a
As

`reduce_by_index`

, but with two-dimensional indexes.- ↑val reduce_by_index_3d 'a [k] [n] [m] [l]: (dest: *[k][m][l]a) -> (f: a -> a -> a) -> (ne: a) -> (is: [n](i64, i64, i64)) -> (as: [n]a) -> *[k][m][l]a
As

`reduce_by_index`

, but with three-dimensional indexes.- ↑val scan [n] 'a: (op: a -> a -> a) -> (ne: a) -> (as: [n]a) -> *[n]a
Inclusive prefix scan. Has the same caveats with respect to associativity and complexity as

`reduce`

.**Work:***O(n ✕ W(op))***Span:***O(log(n) ✕ W(op))*- ↑val filter [n] 'a: (p: a -> bool) -> (as: [n]a) -> *[]a
Remove all those elements of

`as`

that do not satisfy the predicate`p`

.**Work:***O(n ✕ W(p))***Span:***O(log(n) ✕ W(p))*- ↑val partition [n] 'a: (p: a -> bool) -> (as: [n]a) -> ?[k].([k]a, [n - k]a)
Split an array into those elements that satisfy the given predicate, and those that do not.

**Work:***O(n ✕ W(p))***Span:***O(log(n) ✕ W(p))*- ↑val partition2 [n] 'a: (p1: a -> bool) -> (p2: a -> bool) -> (as: [n]a) -> ?[k][l].([k]a, [l]a, [n - k - l]a)
Split an array by two predicates, producing three arrays.

**Work:***O(n ✕ (W(p1) + W(p2)))***Span:***O(log(n) ✕ (W(p1) + W(p2)))*- ↑val all [n] 'a: (f: a -> bool) -> (as: [n]a) -> bool
Return

`true`

if the given function returns`true`

for all elements in the array.**Work:***O(n ✕ W(f))***Span:***O(log(n) + S(f))*- ↑val any [n] 'a: (f: a -> bool) -> (as: [n]a) -> bool
Return

`true`

if the given function returns`true`

for any elements in the array.**Work:***O(n ✕ W(f))***Span:***O(log(n) + S(f))*- ↑val spread 't [n]: (k: i64) -> (x: t) -> (is: [n]i64) -> (vs: [n]t) -> *[k]t
`r = spread k x is vs`

produces an array`r`

such that`r[i] = vs[j]`

where`is[j] == i`

, or`x`

if no such`j`

exists. Intuitively,`is`

is an array indicating where the corresponding elements of`vs`

should be located in the result. Out-of-bounds elements of`is`

are ignored. In-bounds duplicates in`is`

result in unspecified behaviour - see`hist`

for a function that can handle this.**Work:***O(k + n)***Span:***O(1)*- ↑val scatter 't [k] [n]: (dest: *[k]t) -> (is: [n]i64) -> (vs: [n]t) -> *[k]t
Like

`spread`

, but takes an array indicating the initial values, and has different work complexity.**Work:***O(n)***Span:***O(1)*- ↑val scatter_2d 't [k] [n] [l]: (dest: *[k][n]t) -> (is: [l](i64, i64)) -> (vs: [l]t) -> *[k][n]t
`scatter_2d as is vs`

is the equivalent of a`scatter`

on a 2-dimensional array.**Work:***O(n)***Span:***O(1)*- ↑val scatter_3d 't [k] [n] [o] [l]: (dest: *[k][n][o]t) -> (is: [l](i64, i64, i64)) -> (vs: [l]t) -> *[k][n][o]t
`scatter_3d as is vs`

is the equivalent of a`scatter`

on a 3-dimensional array.**Work:***O(n)***Span:***O(1)*