►Math Library
▼6 Arrays
On this page:
array-strictness
array-strict?
array-strict!
array-strict
array-default-strict!
array-default-strict
build-simple-array
array-lazy
  top  contents    up   

6.16 Strictness🔗ℹ

parameter

(array-strictness) → Boolean

(array-strictness strictness) → void?
  strictness : Boolean
Determines whether math/array functions return strict arrays. The default value is #t.

See Nonstrict Arrays for a discussion on nonstrict arrays.

procedure

(array-strict? arr) → Boolean

  arr : (Array A)
Returns #t when arr is strict.

Examples:
> (define arr
    (parameterize ([array-strictness #f])
      (array+ (array 10) (array #[0 1 2 3]))))
> (array-strict? arr)

- : Boolean

#f

> (array-strict! arr)
> (array-strict? arr)

- : Boolean

#t

procedure

(array-strict! arr) → Void

  arr : (Array A)
Causes arr to compute and store all of its elements. Thereafter, arr computes its elements by retrieving them from the store.

If arr is already strict, (array-strict! arr) does nothing.

syntax

(array-strict arr)

 
  arr : (Array A)
An expression form of array-strict!, which is often more convenient. First evaluates (array-strict! arr), then returns arr.

This is a macro so that Typed Racket will preserve arr’s type exactly. If it were a function, (array-strict arr) would always have the type (Array A), even if arr were a subtype of (Array A), such as (Mutable-Array A).

procedure

(array-default-strict! arr) → Void

  arr : (Array A)

syntax

(array-default-strict arr)

 
  arr : (Array A)
Like array-strict! and array-strict, but do nothing when array-strictness is #f.

Apply one of these to return values from library functions to ensure that users get strict arrays by default. See Nonstrict Arrays for details.

procedure

(build-simple-array ds proc) → (Array A)

  ds : In-Indexes
  proc : (Indexes -> A)
Like build-array, but returns an array without storage that is nevertheless considered to be strict, regardless of the value of array-strictness. Such arrays will not cache their elements when array-strict! or array-strict is applied to them.

Use build-simple-array to create arrays that represent simple functions of their indexes. For example, basic array constructors such as make-array are defined in terms of this or its unsafe counterpart.

Be careful with this function. While it creates arrays that are always memory-efficient, it is easy to ruin your program’s performance by using it to define arrays for which element lookup is permanently expensive. In the wrong circumstances, using it instead of build-array can turn a linear algorithm into an exponential one!

In general, use build-simple-array when

  • Computing an element is never more expensive than computing a row-major index followed by applying vector-ref. An example is index-array, which only computes row-major indexes.

  • Computing an element is independent of any other array’s elements. In this circumstance, it is impossible to compose some unbounded number of possibly expensive array procedures.

  • You can prove that each element will be computed at most once, throughout the entire life of your program. This is true, for example, when the result is sent only to a function that makes a copy of it, such as array-lazy or array->mutable-array.

See array-lazy for an example of the last circumstance.

procedure

(array-lazy arr) → (Array A)

  arr : (Array A)
Returns an immutable, nonstrict array with the same elements as arr, but element computations are cached.

Perhaps the most natural way to use array-lazy is for so-called “dynamic programming,” or memoizing a function that happens to have a rectangular domain. For example, this computes the first 10 Fibonacci numbers in linear time:
> (define: fibs : (Array Natural)
    (array-lazy
     (build-simple-array
      #(10) (λ: ([js : Indexes])
              (define j (vector-ref js 0))
              (cond [(j . < . 2)  j]
                    [else  (+ (array-ref fibs (vector (- j 1)))
                              (array-ref fibs (vector (- j 2))))])))))
> fibs

- : #(struct:Array

      (Indexes

       Index

       (Boxof Boolean)

       (-> Void)

       (-> Indexes Nonnegative-Integer))

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)

(array #[0 1 1 2 3 5 8 13 21 34])

Because build-simple-array never stores its elements, its procedure argument may refer to the array it returns. Wrapping its result with array-lazy makes each array-ref take no more than linear time; further, each takes constant time when the elements of fibs are computed in order. Without array-lazy, computing the elements of fibs would take exponential time.

Printing a lazy array computes and caches all of its elements, as does applying array-strict! or array-strict to it.

Except for arrays returned by build-simple-array, it is useless to apply array-lazy to a strict array. Using the lazy copy instead of the original only degrades performance.

While it may seem that array-lazy should just return arr when arr is strict, this would violate the invariant that array-lazy returns immutable arrays. For example:
> (: array-maybe-lazy (All (A) ((Array A) -> (Array A))))
> (define (array-maybe-lazy arr)
    (if (array-strict? arr) arr (array-lazy arr)))
> (define arr (mutable-array #[0 1 2 3]))
> (define brr (array-maybe-lazy arr))
> (array-set! arr #(0) -1000)
> brr

- : #(struct:Array

      (Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Integer))

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>

      #<syntax:build/user/8.14.900/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)

(array #[-1000 1 2 3])

  top  contents    up