/**

* Utilities for working with arrays.

*

* An immutable array implementation is available in the `Immutable` submodule.

*

* @example from "array" include Array

* @example [> 1, 2, 3]

*

* @since v0.2.0

* @history v0.1.0: Originally named `arrays`

* @history v0.2.0: Renamed to `array`

*/

module Array

from "number" include Number

from "list" include List

from "runtime/unsafe/wasmi32" include WasmI32

from "runtime/unsafe/memory" include Memory

from "runtime/dataStructures" include DataStructures

use DataStructures.{ allocateArray, tagSimpleNumber }

from "runtime/exception" include Exception

from "runtime/numbers" include Numbers

use Numbers.{ coerceNumberToWasmI32 }

from "runtime/unsafe/offsets" include Offsets

use Offsets.{ _ARRAY_DATA_OFFSET }

@unsafe

let checkLength = length => {

use WasmI32.{ (&), (>>), (<) }

let ptr = WasmI32.fromGrain(length)

if (WasmI32.eqz(ptr & 1n)) {

throw Exception.InvalidArgument("Length argument must be an integer")

}

let len = ptr >> 1n

if (len < 0n) {

throw Exception.InvalidArgument("Length argument must be non-negative")

}

}

/**

* A simple helper function to convert a negative array index

* number to its positive positional equivalent.

*/

let wrapNegativeIndex = (arrLen, idx) => {

if (idx >= 0) {

idx

} else {

arrLen + idx

}

}

/**

* Provides the length of the input array.

*

* @param array: The array to inspect

* @returns The number of elements in the array

*

* @example Array.length([> 1, 2, 3, 4, 5]) == 5

* @since v0.1.0

*/

@unsafe

provide primitive length = "@array.length"

/**

* Creates a new array of the specified length with each element being

* initialized with the given value.

*

* @param length: The length of the new array

* @param item: The value to store at each index

* @returns The new array

*

* @throws InvalidArgument(String): When `length` is not an integer

* @throws InvalidArgument(String): When `length` is negative

*

* @example Array.make(5, "foo") == [> "foo", "foo", "foo", "foo", "foo"]

*

* @since v0.1.0

*/

@unsafe

provide let make = (length: Number, item: a) => {

use WasmI32.{ (+), (*), (<) }

checkLength(length)

let length = coerceNumberToWasmI32(length)

let byteLength = length * 4n

let array = allocateArray(length)

for (let mut i = 0n; i < byteLength; i += 4n) {

WasmI32.store(

array + i,

Memory.incRef(WasmI32.fromGrain(item)),

_ARRAY_DATA_OFFSET

)

}

ignore(item)

WasmI32.toGrain(array): Array<a>

}

/**

* Creates a new array of the specified length where each element is

* initialized with the result of an initializer function. The initializer

* is called with the index of each array element.

*

* @param length: The length of the new array

* @param fn: The initializer function to call with each index, where the value returned will be used to initialize the element

* @returns The new array

*

* @throws InvalidArgument(String): When `length` is not an integer

* @throws InvalidArgument(String): When `length` is negative

*

* @example Array.init(5, n => n + 3) == [> 3, 4, 5, 6, 7]

*

* @since v0.1.0

*/

@unsafe

provide let init = (length: Number, fn: Number => a) => {

use WasmI32.{ (+), (*), (<) }

checkLength(length)

let length = coerceNumberToWasmI32(length)

let byteLength = length * 4n

let array = allocateArray(length)

let mut index = 0n

for (let mut i = 0n; i < byteLength; i += 4n) {

WasmI32.store(

array,

Memory.incRef(WasmI32.fromGrain(fn(tagSimpleNumber(index)))),

_ARRAY_DATA_OFFSET + i

)

index += 1n

}

WasmI32.toGrain(array): Array<a>

}

/**

* Creates a new array where each element is initialized with the `Ok`

* result value of an initializer function. The initializer is called with the

* index of each element, and returns the new array if all calls to the

* initializer succeed or the first error otherwise.

*

* @param length: The length of the new array

* @param fn: The initializer function to call with each index, where the `Ok` value returned will be used to initialize each element

* @returns `Ok(array)` if all elements were successfully initialized or `Err(error)` if the initializer function returned an error

*

* @throws InvalidArgument(String): When `length` is not an integer

* @throws InvalidArgument(String): When `length` is negative

*

* @example Array.tryInit(5, n => Ok(n + 3)) == [> 3, 4, 5, 6, 7]

* @example Array.tryInit(5, n => if (n == 1) Err("stop") else Ok(n)) == Err("stop")

*

* @since v0.7.0

*/

@unsafe

provide let tryInit = (length: Number, fn: Number => Result<a, b>) => {

use WasmI32.{ (+), (*), (<) }

checkLength(length)

let length = coerceNumberToWasmI32(length)

let byteLength = length * 4n

let array = allocateArray(length)

let mut index = 0n

for (let mut i = 0n; i < byteLength; i += 4n) {

let value = fn(tagSimpleNumber(index))

match (value) {

Ok(value) => {

WasmI32.store(

array,

Memory.incRef(WasmI32.fromGrain(value)),

_ARRAY_DATA_OFFSET + i

)

index += 1n

},

Err(e) => {

for (let mut j = 0n; j < i; j += 4n) {

ignore(Memory.decRef(WasmI32.load(array, _ARRAY_DATA_OFFSET + j)))

}

Memory.free(array)

return Err(e)

},

}

}

return Ok(WasmI32.toGrain(array): Array<a>)

}

/**

* An alias for normal syntactic array access, i.e. `array[n]`.

*

* Retrieves the element from the array at the specified index.

* A negative index is treated as an offset from the end of the array.

*

* @param index: The index to access

* @param array: The array to access

* @returns The element from the array

*

* @throws IndexOutOfBounds: When `index` is not an integer

* @throws IndexOutOfBounds: When `index` is out of bounds

*

* @example Array.get(1, [> 1, 2, 3, 4, 5]) == 2

*

* @since v0.1.0

* @history v0.2.0: Argument order changed to data-last

*/

provide let get = (index, array) => {

array[index]

}

/**

* An alias for normal syntactic array set, i.e. `array[n] = value`.

*

* Sets the element at the specified index in the array to the new value.

* A negative index is treated as an offset from the end of the array.

*

* @param index: The index to update

* @param value: The value to store

* @param array: The array to update

*

* @throws IndexOutOfBounds: When `index` is not an integer

* @throws IndexOutOfBounds: When `index` is out of bounds

*

* @example

* let array = [> 1, 2, 3, 4, 5]

* Array.set(1, 9, array)

* assert array == [> 1, 9, 3, 4, 5]

*

* @since v0.1.0

* @history v0.2.0: Argument order changed to data-last

*/

provide let set = (index, value, array) => {

array[index] = value

}

/**

* Creates a new array with the elements of the first array followed by

* the elements of the second array. This does not modify the arguments.

*

* @param array1: The array containing elements to appear first

* @param array2: The array containing elements to appear second

* @returns The new array containing elements from `array1` followed by elements from `array2`

*

* @throws InvalidArgument(String): When the combined length of the two arrays is not an integer

*

* @example Array.append([> 1, 2], [> 3, 4, 5]) == [> 1, 2, 3, 4, 5]

*

* @since v0.1.0

*/

provide let append = (array1, array2) => {

let len1 = length(array1)

let len2 = length(array2)

init(len1 + len2, n => {

if (n < len1) {

array1[n]

} else {

array2[n - len1]

}

})

}

/**

* Creates a single array containing the elements of all arrays in the

* provided list. Does not modify any of the input arguments.

*

* @param arrays: A list containing all arrays to combine

* @returns The new array

*

* @throws InvalidArgument(String): When the combined length of all arrays is not an integer

*

* @example Array.concat([[> 1, 2], [> 3, 4], [> 5, 6]]) == [> 1, 2, 3, 4, 5, 6]

*

* @since v0.1.0

*/

provide let concat = arrays => {

// This function is slightly verbose to avoid depending on the List stdlib.

let rec findLength = (arrays, acc) => {

match (arrays) {

[fst, ...rest] => findLength(rest, acc + length(fst)),

[] => acc,

}

}

let mut offset = 0

let mut arrs = arrays

let rec next = index => {

let array = match (arrs) {

[fst, ..._] => fst,

[] => fail "end of arrays list",

}

if (index - offset == length(array)) {

offset += length(array)

arrs = match (arrs) {

[_, ...rest] => rest,

[] => fail "end of arrays list",

}

next(index)

} else {

array[index - offset]

}

}

init(findLength(arrays, 0), next)

}

/**

* Produces a shallow copy of the input array. The new array contains the

* same elements as the original.

*

* @param array: The array to copy

* @returns The new array containing the elements from the input

*

* @example Array.copy([> 1, 2, 3]) == [> 1, 2, 3]

*

* @since v0.1.0

*/

provide let copy = array => {

init(length(array), n => array[n])

}

/**

* Iterates an array a given number of times, calling an iterator function on each element.

*

* @param fn: The iterator function to call with each element

* @param n: The number of times to iterate the given array

* @param array: The array to iterate

*

* @example

* let mut str = ""

* Array.cycle(s => str = str ++ s, 2, [> "a", "b", "c"])

* assert str == "abcabc"

*

* @since v0.4.4

*/

provide let cycle = (fn, n, array) => {

let length = length(array)

for (let mut iteration = 0; iteration < n; iteration += 1) {

for (let mut count = 0; count < length; count += 1) {

fn(array[count]): Void

}

}

}

/**

* Iterates an array, calling an iterator function on each element.

*

* @param fn: The iterator function to call with each element

* @param array: The array to iterate

*

* @example

* let mut str = ""

* Array.forEach(s => str = str ++ s, [> "a", "b", "c"])

* assert str == "abc"

*

* @since v0.1.0

* @history v0.2.0: Argument order changed to data-last

*/

provide let forEach = (fn, array) => {

let length = length(array)

for (let mut count = 0; count < length; count += 1) {

fn(array[count]): Void

}

}

/**

* Iterates an array, calling an iterator function on each element.

* Also passes the index as the second argument to the function.

*

* @param fn: The iterator function to call with each element

* @param array: The array to iterate

*

* @example

* let mut str = ""

* Array.forEachi((s, i) => str = str ++ s ++ toString(i), [> "a", "b", "c"])

* assert str == "a0b1c2"

*

* @since v0.1.0

* @history v0.2.0: Argument order changed to data-last

*/

provide let forEachi = (fn, array) => {

let length = length(array)

for (let mut count = 0; count < length; count += 1) {

fn(array[count], count): Void

}

}

/**

* Produces a new array initialized with the results of a mapper function

* called on each element of the input array.

*

* @param fn: The mapper function to call on each element, where the value returned will be used to initialize the element in the new array

* @param array: The array to iterate

* @returns The new array with mapped values

*

* @example Array.map(x => x * 2, [> 1, 2, 3]) == [> 2, 4, 6]

*

* @since v0.1.0

* @history v0.2.0: Argument order changed to data-last

*/

provide let map = (fn, array) => {

let length = length(array)

init(length, i => {

fn(array[i])

})

}

/**

* Produces a new array initialized with the results of a mapper function

* called on each element of the input array and its index.

*

* @param fn: The mapper function to call on each element, where the value returned will be used to initialize the element in the new array

* @param array: The array to iterate

* @returns The new array with mapped values

*

* @example Array.mapi((x, i) => (x * 2, i), [> 1, 2, 3]) == [> (2, 0), (4, 1), (6, 2)]

*

* @since v0.1.0

*/

provide let mapi = (fn, array) => {

let length = length(array)

init(length, index => {

fn(array[index], index)

})

}

/**

* Combines all elements of an array using a reducer function,

* starting from the "head", or left side, of the array.

*

* In `Array.reduce(fn, initial, array)`, `fn` is called with

* an accumulator and each element of the array, and returns

* a new accumulator. The final value is the last accumulator

* returned. The accumulator starts with value `initial`.

*

* @param fn: The reducer function to call on each element, where the value returned will be the next accumulator value

* @param initial: The initial value to use for the accumulator on the first iteration

* @param array: The array to iterate

* @returns The final accumulator returned from `fn`

*

* @example Array.reduce((acc, el) => acc + el, 0, [> 1, 2, 3]) == 6

* @example Array.reduce((acc, el) => acc ++ el, "", [> "baz", "bar", "foo"]) == "bazbarfoo"

*

* @since v0.3.0

*/

provide let reduce = (fn, initial, array) => {

let mut acc = initial

forEach(el => acc = fn(acc, el), array)

acc

}

/**

* Combines all elements of an array using a reducer function,

* starting from the "end", or right side, of the array.

*

* In `Array.reduceRight(fn, initial, array)`, `fn` is called with

* each element of the array and an accumulator, and returns

* a new accumulator. The final value is the last accumulator

* returned. The accumulator starts with value `initial`.

*

* @param fn: The reducer function to call on each element, where the value returned will be the next accumulator value

* @param initial: The initial value to use for the accumulator on the first iteration

* @param array: The array to iterate

* @returns The final accumulator returned from `fn`

*

* @example Array.reduceRight((el, acc) => acc ++ el, "", [> "baz", "bar", "foo"]) == "foobarbaz"

*

* @since v0.5.3

*/

provide let reduceRight = (fn, initial, array) => {

let mut acc = initial

for (let mut i = length(array) - 1; i >= 0; i -= 1) {

acc = fn(array[i], acc)

}

acc

}

/**

* Combines all elements of an array using a reducer function,

* starting from the "head", or left side, of the array.

*

* In `Array.reducei(fn, initial, array)`, `fn` is called with

* an accumulator, each element of the array, and the index

* of that element, and returns a new accumulator. The final

* value is the last accumulator returned. The accumulator

* starts with value `initial`.

*

* @param fn: The reducer function to call on each element, where the value returned will be the next accumulator value

* @param initial: The initial value to use for the accumulator on the first iteration

* @param array: The array to iterate

* @returns The final accumulator returned from `fn`

*

* @example Array.reducei((acc, el, index) => acc + el + index, 0, [> 1, 2, 3]) == 9

* @example

* let output = Array.reducei((acc, el, index) => {

* acc ++ el ++ toString(index)

* }, "", [> "baz", "bar", "foo"])

* assert output == "baz0bar1foo2"

*

* @since v0.3.0

*/

provide let reducei = (fn, initial, array) => {

let mut acc = initial

forEachi((el, index) => acc = fn(acc, el, index), array)

acc

}

/**

* Produces a new array by calling a function on each element

* of the input array. Each iteration produces an intermediate

* array, which are all appended to produce a "flattened" array

* of all results.

*

* @param fn: The function to be called on each element, where the value returned will be an array that gets appended to the new array

* @param array: The array to iterate

* @returns The new array

*

* @throws InvalidArgument(String): When the combined length of all arrays is not an integer

*

* @example Array.flatMap(e => [> 1, e], [> 1, 2, 3]) == [> 1, 1, 1, 2, 1, 3]

*

* @since v0.3.0

*/

provide let flatMap = (fn, array) => {

let nested = map(fn, array)

let arrLen = reduce((acc, arr) => acc + length(arr), 0, nested)

let mut outerI = 0

let mut innerI = 0

init(arrLen, i => {

if (innerI >= length(nested[outerI])) {

innerI = 0

outerI += 1

}

let res = nested[outerI][innerI]

innerI += 1

res

})

}

/**

* Checks that the given condition is satisfied for all

* elements in the input array.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to check

* @returns `true` if all elements satisfy the condition or `false` otherwise

*

* @example Array.every(e => e % 2 == 0, [> 2, 4, 6]) == true

* @example Array.every(e => e % 2 == 0, [> 2, 4, 7]) == false

*

* @since v0.3.0

*/

provide let every = (fn, array) => {

let len = length(array)

let mut all = true

for (let mut index = 0; all && index < len; index += 1) {

all = fn(array[index])

}

all

}

/**

* Checks that the given condition is satisfied **at least

* once** by an element in the input array.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to iterate

* @returns `true` if one or more elements satisfy the condition or `false` otherwise

*

* @example Array.some(e => e % 2 == 0, [> 2, 4, 6]) == true

* @example Array.some(e => e % 2 == 0, [> 2, 4, 7]) == true

* @example Array.some(e => e % 2 == 0, [> 3, 5, 7]) == false

*

* @since v0.3.0

*/

provide let some = (fn, array) => {

let len = length(array)

let mut found = false

for (let mut index = 0; !found && index < len; index += 1) {

found = fn(array[index])

}

found

}

/**

* Replaces all elements in an array with the new value provided.

*

* @param value: The value replacing each element

* @param array: The array to update

*

* @example

* let arr = [> 2, 4, 6]

* Array.fill(0, arr)

* assert arr == [> 0, 0, 0]

*

* @since v0.2.0

*/

provide let fill = (value, array) => {

let length = length(array)

forEachi((_, index) => {

array[index] = value

}, array)

void

}

/**

* Replaces all elements in the provided index range in the array

* with the new value provided. Fails if the index is out-of-bounds.

*

* @param value: The value replacing each element between the indexes

* @param start: The index to begin replacement

* @param stop: The (exclusive) index to end replacement

* @param array: The array to update

*

* @throws IndexOutOfBounds: When the start index is out of bounds

* @throws IndexOutOfBounds: When the start index is greater then the stop index

*

* @example

* let arr = [> 2, 4, 6, 8]

* Array.fillRange(0, 1, 3, arr)

* assert arr == [> 2, 0, 0, 8]

*

* @since v0.2.0

*/

provide let fillRange = (value, start, stop, array) => {

let length = length(array)

let startIndex = wrapNegativeIndex(length, start)

let stopIndex = wrapNegativeIndex(length, stop)

// Ensure we aren't working with a `stop` value that is too big

let stopIndex = if (stopIndex < 0 || stopIndex > length) {

length

} else {

stopIndex

}

if (startIndex > length || startIndex > stopIndex) {

throw IndexOutOfBounds

}

for (let mut index = startIndex; index < stopIndex; index += 1) {

array[index] = value

}

void

}

/**

* Creates a new array with all elements in reverse order.

*

* @param array: The array to reverse

* @returns The new array

*

* @example Array.reverse([> 1, 2, 3]) == [> 3, 2, 1]

*

* @since v0.4.0

*/

provide let reverse = array => {

let len = length(array)

init(len, index => {

let last = len - index - 1

array[last]

})

}

/**

* Converts the input array to a list.

*

* @param array: The array to convert

* @returns The list containing all elements from the array

*

* @example Array.toList([> 1, 2, 3]) == [1, 2, 3]

*

* @since v0.1.0

*/

provide let toList = array => {

let rec buildList = (acc, index) => {

let index = index - 1

if (index < 0) {

acc

} else {

buildList([array[index], ...acc], index)

}

}

buildList([], length(array))

}

/**

* Converts the input list to an array.

*

* @param list: The list to convert

* @returns The array containing all elements from the list

*

* @example Array.fromList([1, 2, 3]) == [> 1, 2, 3]

*

* @since v0.1.0

*/

provide let fromList = list => {

let rec listLength = (list, acc) => {

match (list) {

[_, ...rest] => listLength(rest, acc + 1),

[] => acc,

}

}

let mut lst = list

let rec next = index => {

match (lst) {

[fst, ...rest] => {

lst = rest

fst

},

[] => next(index),

}

}

init(listLength(list, 0), next)

}

/**

* Checks if the value is an element of the input array.

* Uses the generic `==` structural equality operator.

*

* @param search: The value to compare

* @param array: The array to inspect

* @returns `true` if the value exists in the array or `false` otherwise

*

* @example Array.contains(1, [> 1, 2, 3]) == true

* @example Array.contains(0, [> 1, 2, 3]) == false

*

* @since v0.2.0

*/

provide let contains = (search, array) => {

// TODO(#189): This should be rewritten to use recursion and pattern matching

let len = length(array)

for (let mut i = 0; i < len; i += 1) {

if (array[i] == search) return true

}

return false

}

/**

* Finds the first element in an array that satisfies the given condition.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to search

* @returns `Some(element)` containing the first value found or `None` otherwise

*

* @example Array.find(e => e % 2 == 0, [> 1, 4, 3]) == Some(4)

* @example Array.find(e => e % 2 == 0, [> 1, 2, 3, 4]) == Some(2)

* @example Array.find(e => e % 2 == 0, [> 1, 3, 5]) == None

*

* @since v0.2.0

*/

provide let find = (fn, array) => {

let len = length(array)

for (let mut i = 0; i < len; i += 1) {

if (fn(array[i])) {

return Some(array[i])

}

}

return None

}

/**

* Finds the first index in an array where the element satisfies the given condition.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to search

* @returns `Some(index)` containing the index of the first element found or `None` otherwise

*

* @example Array.findIndex(e => e % 2 == 0, [> 1, 4, 3]) == Some(1)

* @example Array.findIndex(e => e % 2 == 0, [> 1, 2, 3, 4]) == Some(1)

* @example Array.findIndex(e => e % 2 == 0, [> 1, 3, 5]) == None

*

* @since v0.2.0

*/

provide let findIndex = (fn, array) => {

let len = length(array)

for (let mut i = 0; i < len; i += 1) {

if (fn(array[i])) return Some(i)

}

return None

}

/**

* Combines two arrays into a Cartesian product of tuples containing

* all ordered pairs `(a, b)`.

*

* @param array1: The array to provide values for the first tuple element

* @param array2: The array to provide values for the second tuple element

* @returns The new array containing all pairs of `(a, b)`

*

* @throws InvalidArgument(String): When the multiplied array lengths are not an integer

*

* @example Array.product([> 1, 2], [> 3, 4]) == [> (1, 3), (1, 4), (2, 3), (2, 4)]

*

* @since v0.2.0

*/

provide let product = (array1: Array<a>, array2: Array<b>) => {

let lenA = length(array1)

let lenB = length(array2)

let mut indexA = -1

init(lenA * lenB, n => {

if (n % lenB == 0) {

indexA += 1

}

(array1[indexA], array2[n % lenB])

})

}

/**

* Counts the number of elements in an array that satisfy the given condition.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to iterate

* @returns The total number of elements that satisfy the condition

*

* @example Array.count(e => e % 2 == 0, [> 1, 2, 3, 4]) == 2

*

* @since v0.2.0

*/

provide let count = (fn, array) => {

let len = length(array)

let mut n = 0

for (let mut i = 0; i < len; i += 1) {

if (fn(array[i])) {

n += 1

}

}

n

}

/**

* Counts the number of elements in an array that satisfy the

* given condition. Also passes the index to the function.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to iterate

* @returns The total number of elements that satisfy the condition

*

* @example Array.counti((e, i) => e % 2 == 0 && i % 2 == 0, [> 1, 2, 3, 4, 5]) == 0

* @example Array.counti((e, i) => e % 2 == 0 && i % 2 == 0, [> 0, 1, 2, 3, 5]) == 2

*

* @since v0.3.0

*/

provide let counti = (fn, array) => {

let len = length(array)

let mut n = 0

for (let mut i = 0; i < len; i += 1) {

if (fn(array[i], i)) {

n += 1

}

}

n

}

/**

* Produces a new array by calling a function on each element of

* the input array and only including it in the result array if the element satisfies

* the condition.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to iterate

* @returns The new array containing elements where `fn` returned `true`

*

* @example Array.filter(e => e % 2 == 0, [> 1, 2, 3, 4]) == [> 2, 4]

*

* @since v0.3.0

*/

provide let filter = (fn, array) => {

let filtered = copy(array)

let mut position = 0

forEach(el => {

if (fn(el)) {

filtered[position] = el

position += 1

}

}, array)

init(position, index => {

filtered[index]

})

}

/**

* Produces a new array by calling a function on each element of

* the input array and only including it in the result array if the element satisfies

* the condition. Also passes the index to the function.

*

* @param fn: The function to call on each element, where the returned value indicates if the element satisfies the condition

* @param array: The array to iterate

* @returns The new array containing elements where `fn` returned `true`

*

* @example Array.filteri((e, i) => e % 2 == 0, [> 1, 2, 3, 4]) == [> 2, 4]

* @example Array.filteri((e, i) => e % 2 == 1 && i % 2 == 0, [> 1, 2, 3, 4, 5]) == [> 1, 3, 5]

*

* @since v0.3.0

*/

provide let filteri = (fn, array) => {

let filtered = copy(array)

let mut position = 0

forEachi((el, index) => {

if (fn(el, index)) {

filtered[position] = el

position += 1

}

}, array)

init(position, index => {

filtered[index]

})

}

/**

* Produces a new array with any duplicates removed.

* Uses the generic `==` structural equality operator.

*

* @param array: The array to filter

* @returns The new array with only unique values

*

* @example Array.unique([> 1, 2, 1, 2, 3, 1]) == [> 1, 2, 3]

*

* @since v0.3.0

*/

provide let unique = array => {

// TODO(#1651): improve performance

filteri(

(el, index) => findIndex(value => value == el, array) == Some(index),

array

)

}

/**

* Produces a new array filled with tuples of elements from both given arrays.

* The first tuple will contain the first item of each array, the second tuple

* will contain the second item of each array, and so on.

*

* @param array1: The array to provide values for the first tuple element

* @param array2: The array to provide values for the second tuple element

* @returns The new array containing indexed pairs of `(a, b)`

*

* @throws IndexOutOfBounds: When the arrays have different sizes

*

* @example Array.zip([> 1, 2, 3], [> 4, 5, 6]) == [> (1, 4), (2, 5), (3, 6)]

*

* @since v0.4.0

* @history v0.6.0: Support zipping arrays of different sizes

*/

provide let zip = (array1: Array<a>, array2: Array<b>) => {

let len = length(array1)

let len2 = length(array2)

let len = if (len > len2) len2 else len

init(len, n => {

(array1[n], array2[n])

})

}

/**

* Produces a new array filled with elements defined by applying a function on

* pairs from both given arrays. The first element will contain the result of

* applying the function to the first elements of each array, the second element

* will contain the result of applying the function to the second elements of

* each array, and so on.

*

* Calling this function with arrays of different sizes will cause the returned

* array to have the length of the smaller array.

*

* @param fn: The function to apply to pairs of elements

* @param array1: The array whose elements will each be passed to the function as the first argument

* @param array2: The array whose elements will each be passed to the function as the second argument

* @returns The new array containing elements derived from applying the function to pairs of input array elements

*

* @throws IndexOutOfBounds: When the arrays have different sizes

*

* @example Array.zipWith((a, b) => a + b, [> 1, 2, 3], [> 4, 5, 6]) == [> 5, 7, 9]

* @example Array.zipWith((a, b) => a * b, [> 1, 2, 3], [> 4, 5]) == [> 4, 10]

*

* @since v0.5.3

*/

provide let zipWith = (fn, array1: Array<a>, array2: Array<b>) => {

let len1 = length(array1)

let len2 = length(array2)

let minLen = if (len1 > len2) len2 else len1

init(minLen, index => {

fn(array1[index], array2[index])

})

}

/**

* Produces two arrays by splitting apart an array of tuples.

*

* @param array: The array of tuples to split

* @returns An array containing all elements from the first tuple element, and an array containing all elements from the second tuple element

*

* @example Array.unzip([> (1, 4), (2, 5), (3, 6)]) == ([> 1, 2, 3], [> 4, 5, 6])

*

* @since v0.4.0

*/

provide let unzip = array => {

let lenArr = length(array)

let a = init(lenArr, n => {

let (fst, _) = array[n]

fst

})

let b = init(lenArr, n => {

let (_, snd) = array[n]

snd