array

Arrays: a fixed number of elements, each reached at once by its index (from 0). Import it by a name, import array as Array: Array.length, Array.index, as length and map are the prelude’s lists’ too.

An array is a value and never changes: set gives another. Where nothing else holds the array, though, set writes in place, and so does everything here made of it (modify, swap, fill, reverse); held elsewhere too, it is copied first, once. So an array passed from one step of a loop to the next is changed in place, as a mutable one is. It grows so too: an array held only there keeps room after its elements, which push, append and insertAt write into, and grows it, twice as much, where there is none — an array built a push at a time is copied a few times, not once a push. pop and removeAt take an element off, the room kept, and reserve makes room ahead.

import array as Array

-- | the primes below `n`, by a sieve
-- | >>> primes 20
-- | [2, 3, 5, 7, 11, 13, 17, 19]
primes : Int -> List Int
primes n = List.keepIf (\i -> Array.index sieve i == Just 1) (List.range 2 (n - 1))
  where
  cross : Int -> Int -> Array Int -> Array Int
  cross p j xs = if j >= n then xs else cross p (j + p) (Array.set xs j 0)

  sift : Int -> Array Int -> Array Int
  sift p xs = if p * p >= n then xs else sift (p + 1) (cross p (p * p) xs)

  sieve : Array Int
  sieve = sift 2 (Array.replicate n 1)

An array of a number’s type (Float64, Int64, UInt8, …) is kept flat where it is built knowing the type, as C’s array of it: an Array Float64 is doubles, an Array UInt8 bytes. In JavaScript, an array of numbers is a Float64Array.

arrayLength

arrayLength : {a : Type} -> Array a -> Int

arrayIndex

arrayIndex : {a : Type} -> Array a -> Int -> a

arraySet

arraySet : {a : Type} -> Array a -> Int -> a -> Array a

arrayGenerate

arrayGenerate : {a : Type} -> Int -> (Int -> a) -> Array a

arrayReplicate

arrayReplicate : {a : Type} -> Int -> a -> Array a

arrayFromList

arrayFromList : {a : Type} -> List a -> Array a

arrayToList

arrayToList : {a : Type} -> Array a -> List a

arraySlice

arraySlice : {a : Type} -> Array a -> Int -> Int -> Array a

arrayAppend

arrayAppend : {a : Type} -> Array a -> Array a -> Array a

arrayInsertAt

arrayInsertAt : {a : Type} -> Array a -> Int -> a -> Array a

arrayRemoveAt

arrayRemoveAt : {a : Type} -> Array a -> Int -> Array a

arrayPush

arrayPush : {a : Type} -> Array a -> a -> Array a

arrayReserve

arrayReserve : {a : Type} -> Array a -> Int -> Array a

length

length : {a : Type} -> Array a -> Int

How many elements it has.

>>> length (arrayFromList ["a", "b"])
2

instanceIterateArray

instance instanceIterateArray : {a : Type} -> Iterate (Array a)

An array, from its first element: for x in xs goes through it by its index (the cursor is the array and the index).

index

index : {a : Type} -> Array a -> Int -> Maybe a

The element at i, if there is one: out of range, Nothing.

>>> index (arrayFromList ["a", "b"]) 1
Just "b"
>>> index (arrayFromList ["a", "b"]) 2
Nothing
>>> index (arrayFromList ["a", "b"]) -1
Nothing

set

set : {a : Type} -> Array a -> Int -> a -> Array a

Another array, with x at i; out of range, the array as it is. Written in place where nothing else holds the array, else a copy.

>>> arrayToList (set (arrayFromList [1, 2]) 0 7)
Cons 7 (Cons 2 Nil)
>>> arrayToList (set (arrayFromList [1, 2]) 2 7)
Cons 1 (Cons 2 Nil)
>>> arrayToList (set (arrayFromList [1, 2]) -1 7)
Cons 1 (Cons 2 Nil)

generate

generate : {a : Type} -> Int -> (Int -> a) -> Array a

n elements, the one at i being f i.

replicate

replicate : {a : Type} -> Int -> a -> Array a

n elements, each x; fewer than none, none.

>>> arrayToList (replicate 3 'a')
Cons 'a' (Cons 'a' (Cons 'a' Nil))
>>> length (replicate -1 0.5)
0

fromList

fromList : {a : Type} -> List a -> Array a

A list’s elements, in its order.

toList

toList : {a : Type} -> Array a -> List a

The elements, in order, as a list.

empty

empty : {a : Type} -> Array a

An array of no elements.

>>> length (empty : Array Int)
0

modify

modify : {a : Type} -> Array a -> Int -> (a -> a) -> Array a

The element at i made f of it; out of range, the array as it is.

>>> toList (modify (fromList [1, 2, 3]) 1 (\x -> x * 10))
Cons 1 (Cons 20 (Cons 3 Nil))
>>> toList (modify (fromList [1, 2, 3]) 3 (\x -> x * 10))
Cons 1 (Cons 2 (Cons 3 Nil))

swap

swap : {a : Type} -> Array a -> Int -> Int -> Array a

The elements at i and j swapped; either out of range, the array as it is.

>>> toList (swap (fromList ["a", "b", "c"]) 0 2)
Cons "c" (Cons "b" (Cons "a" Nil))
>>> toList (swap (fromList ["a", "b", "c"]) 0 3)
Cons "a" (Cons "b" (Cons "c" Nil))

fill

fill : {a : Type} -> Array a -> a -> Array a

Each element x.

>>> toList (fill (fromList [1, 2, 3]) 0)
Cons 0 (Cons 0 (Cons 0 Nil))

slice

slice : {a : Type} -> Array a -> Int -> Int -> Array a

The elements from i up to j, j not among them, each where it is clamped to them, and a negative one counted from the end, as a string’s slice is.

>>> List.map toList [slice (fromList [1, 2, 3, 4]) 1 3, slice (fromList [1, 2, 3, 4]) 2 9, slice (fromList [1, 2, 3, 4]) -1 4]
Cons (Cons 2 (Cons 3 Nil)) (Cons (Cons 3 (Cons 4 Nil)) (Cons (Cons 4 Nil) Nil))

append

append : {a : Type} -> Array a -> Array a -> Array a

The elements of one, then of the other: the first’s room grown, in place, where nothing else holds it.

>>> toList (append (fromList [1, 2]) (fromList [3]))
Cons 1 (Cons 2 (Cons 3 Nil))

push

push : {a : Type} -> Array a -> a -> Array a

x after the last element. In place where nothing else holds the array and it has room; where it has none, its room is doubled first. Held elsewhere too, a copy, with room.

>>> toList (push (fromList [1, 2]) 3)
Cons 1 (Cons 2 (Cons 3 Nil))
>>> toList (push empty "a")
Cons "a" Nil

pop

pop : {a : Type} -> Array a -> Maybe (Array a, a)

The last element and the others, if there is one; of none, Nothing. Where nothing else holds the array, it is shortened in place, its room kept for the next push. A match on it where it is called builds neither the Just nor the pair: it is inlined, a test of the length, and the match chooses in each of its ways.

>>> pop (fromList [1, 2, 3])
Just (MkPair [1, 2] 3)
>>> pop (empty : Array Int)
Nothing

reserve

reserve : {a : Type} -> Array a -> Int -> Array a

The same elements, with room for at least k more, so that so many pushes are not grown; fewer than none, none. In place where nothing else holds the array, else a copy.

>>> toList (push (reserve (fromList [1]) 100) 2)
Cons 1 (Cons 2 Nil)

insertAt

insertAt : {a : Type} -> Array a -> Int -> a -> Array a

x put in at i — clamped to them, from 0 up to the length — the elements from there one further on. In place where nothing else holds the array and it has room.

>>> toList (insertAt (fromList ["a", "c"]) 1 "b")
Cons "a" (Cons "b" (Cons "c" Nil))
>>> toList (insertAt (fromList ["a", "b"]) 9 "c")
Cons "a" (Cons "b" (Cons "c" Nil))

removeAt

removeAt : {a : Type} -> Array a -> Int -> Array a

The element at i taken out, those after it one nearer; out of range, the array as it is. In place where nothing else holds the array, its room kept, as pop keeps it.

>>> toList (removeAt (fromList ["a", "b", "c"]) 1)
Cons "a" (Cons "c" Nil)
>>> toList (removeAt (fromList ["a", "b"]) 2)
Cons "a" (Cons "b" Nil)

map

map : {a b : Type} -> (a -> b) -> Array a -> Array b

Each element, f of it: another array.

>>> toList (map (\x -> x * 2) (fromList [1, 2]))
Cons 2 (Cons 4 Nil)

foldl

foldl : {a b : Type} -> (b -> a -> b) -> b -> Array a -> b

The elements, from the first, into z.

foldr

foldr : {a b : Type} -> (a -> b -> b) -> b -> Array a -> b

The elements, from the last, into z: foldr f z of [a, b] is f a (f b z).

>>> foldr (\x s -> s ^ x) "" (fromList ["a", "b", "c"])
"cba"

reverse

reverse : {a : Type} -> Array a -> Array a

The elements the other way round.

>>> toList (reverse (fromList [1, 2, 3]))
Cons 3 (Cons 2 (Cons 1 Nil))

sort

sort : {a : Type} -> {{ord : Order a}} -> Array a -> Array a

Sorted by the elements’ Order, stably.

>>> toList (sort (fromList ["b", "c", "a"]))
Cons "a" (Cons "b" (Cons "c" Nil))

sortOn

sortOn : {a k : Type} -> {{ord : Order k}} -> (a -> k) -> Array a -> Array a

Sorted by key’s Order, stably, as List.sortOn is: of two whose keys are equal, the first first. Where nothing else holds the array, it is sorted in place, one other array made.

>>> List.map snd (toList (sortOn (\p -> fst p) (fromList (List.map (\i -> MkPair (i % 3) i) (List.range 1 40)))))
[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38]
>>> toList (sortOn (\x -> 0 - x) (fromList [3, 1, 2]))
Cons 3 (Cons 2 (Cons 1 Nil))

search

search : {a : Type} -> (a -> Bool) -> Array a -> Int

The least index whose element p holds of, the length if none, by halving: p must hold, if at all, from some index to the end — of an array sorted going up, \x -> x >= y finds where y is, or would go (Go’s sort.Search).

>>> List.map (\y -> search (\x -> x >= y) (fromList [1, 3, 3, 7])) [0, 3, 4, 8]
Cons 0 (Cons 1 (Cons 3 (Cons 4 Nil)))

null

null : {a : Type} -> Array a -> Bool

Whether it has no elements.

>>> List.map null [empty, fromList [1]]
Cons True (Cons False Nil)

keepIf

keepIf : {a : Type} -> (a -> Bool) -> Array a -> Array a

Those p holds of, in order.

>>> toList (keepIf (\x -> x % 2 == 1) (fromList [1, 2, 3]))
Cons 1 (Cons 3 Nil)

indexWhere

indexWhere : {a : Type} -> (a -> Bool) -> Array a -> Maybe Int

Where the first element p holds of is, if one is.

>>> List.map (\y -> indexWhere (\x -> x > y) (fromList [1, 3, 5])) [2, 9]
Cons (Just 1) (Cons Nothing Nil)

find

find : {a : Type} -> (a -> Bool) -> Array a -> Maybe a

The first element p holds of, if one does.

>>> find (\x -> x > 2) (fromList [1, 3, 5])
Just 3

any

any : {a : Type} -> (a -> Bool) -> Array a -> Bool

Whether p holds of some element.

>>> any (\x -> x > 4) (fromList [1, 3, 5])
True

all

all : {a : Type} -> (a -> Bool) -> Array a -> Bool

Whether p holds of every element (of none, it does).

>>> List.map (all (\x -> x > 0)) [fromList [1, 3], fromList [1, 0], empty]
Cons True (Cons False (Cons True Nil))