Abstract

Functions on pure arrays.

This module contains modules and functions for manipulating arrays. Which might be something like deduplication or a generalized reduction by a key.

Synopsis

local module type array = {
val eq [n] [m] 't: (eq: (t -> t -> bool)) -> [n]t -> [m]t -> bool
val le [n] [m] 't: (lte: (t -> t -> bool)) -> [n]t -> [m]t -> bool
}
module array: array
module type array_key = {
type key
type ctx
type rng
val reduce_by_key [n] 'v: ctx -> rng -> (v -> v -> v) -> v -> [n](key, v) -> ?[m].(rng, [m](key, v))
val dedup [n]: ctx -> rng -> [n]key -> ?[m].(rng, [m]key)
}
module mk_array_key: (K: hashkey) -> (E: rng_engine with int.t = u64) -> array_key with rng = E.rng with key = K.key with ctx = K.ctx

Description

↑local module type array

Fairly simple functions on arrays. Implemented by the module array.

↑val eq [n] [m] 't: (eq: (t -> t -> bool)) -> [n]t -> [m]t -> bool

True if the provided arrays have the same size and the same elements as determined by the provided operator.

↑val le [n] [m] 't: (lte: (t -> t -> bool)) -> [n]t -> [m]t -> bool

Lexicographical less-or-equal comparison of two arrays.

↑module array
↑module type array_key

A module type for functions on arrays of keys. Use mk_array_key to produce a module that implements this module type, given a random number generator.

↑type key

The key type.

↑type ctx

The context type.

↑type rng

The random number generator.

↑val reduce_by_key [n] 'v: ctx -> rng -> (v -> v -> v) -> v -> [n](key, v) -> ?[m].(rng, [m](key, v))

Reduce by key works like Futharks reduce_by_index but instead of the need to make every value correspond to an index in some array it can instead correspond to a key. Here an array of n key k and value v pairs are given as an array. And every value with the same key will be reduced with an associative and commutative operator op, futhermore an neutral element ne must be given.

↑val dedup [n]: ctx -> rng -> [n]key -> ?[m].(rng, [m]key)

Removes duplicate elements from an array as defined by the equality relation of the key. This implementation works much like reduce_by_key but saves some steps which makes it faster.

↑module mk_array_key