Documentation

Fleet arrays.

Convert a list into an array. O(n)

Converting an array into a list. O(n)

Indexing an array. O(1)

WARNING: If you were to write your own swap function. You might be tempted to write it like this:

swap :: Int -> Int -> Array a -> Array a
swap !i !j !xs = set i (xs ! j) (set j (xs ! i) xs)

Unfortunately, this leaves the order between the reads and writes undefined. And in practice, GHC picks the wrong order. To enforce that reads happen before writes, you can use tag. See its documentation for more info.

Indexing an array. O(1)

The tuple and Token serve two purposes:

• You can now separately force the evaluation of the tuple and the actual array element
• You can use the Token to with the tag function on an array to force the indexing to happen before the array can be written to.

This is a no-op, but can be used to enforce an ordering between indexing and other array operations, to avoid the overhead of indexing from older versions of the array.

For example, swapping two elements in an array by using index and set can be done like this:

swap :: Int -> Int -> Array a -> Array a
swap i j xs =
  let (x, t1) = index i xs
      (y, t2) = index j xs
  in set i y (set j x (tag t1 (tag t2 xs)))

This ensures the indexing happens before the setting.

Update the array element at a given position to a new value. O(1)

Copy an array. O(n) This detaches any future updates from old versions of the array. Use this when you know you will be updating a large part of an array.

Swap two elements in an array. O(1)