6.13 Folds, Reductions and Expansions
6.13.1 Axis Folds
procedure
(array-axis-fold arr k f) → (Array A)
arr : (Array A) k : Integer f : (A A -> A) (array-axis-fold arr k f init) → (Array B) arr : (Array A) k : Integer f : (A B -> B) init : B
The three-argument variant uses the first value of each row in axis k as init. It therefore requires axis k to have positive length.
> (define arr (index-array #(3 4))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2 3] #[4 5 6 7] #[8 9 10 11]])
> (array-axis-fold arr 0 +)
- : #(struct:Array
(Indexes
Index
(Boxof Boolean)
(-> Void)
(-> Indexes Nonnegative-Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[12 15 18 21])
> (array-axis-fold arr 1 (inst cons Index (Listof Index)) empty)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes (Listof Index)))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #['(3 2 1 0) '(7 6 5 4) '(11 10 9 8)])
If you need control over the order of evaluation in axis k’s rows, see array-axis-reduce.
syntax
(array-axis-sum arr k)
(array-axis-sum arr k init)
syntax
(array-axis-prod arr k)
(array-axis-prod arr k init)
arr : (Array Number)
k : Integer
init : Number
syntax
(array-axis-min arr k)
(array-axis-min arr k init)
syntax
(array-axis-max arr k)
(array-axis-max arr k init)
arr : (Array Real)
k : Integer
init : Real
> (define arr (index-array #(3 4))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2 3] #[4 5 6 7] #[8 9 10 11]])
> (array-axis-fold arr 1 +)
- : #(struct:Array
(Indexes
Index
(Boxof Boolean)
(-> Void)
(-> Indexes Nonnegative-Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[6 22 38])
> (array-axis-sum arr 1)
- : #(struct:Array
(Indexes
Index
(Boxof Boolean)
(-> Void)
(-> Indexes Nonnegative-Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[6 22 38])
> (array-axis-sum arr 0 0.0)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Nonnegative-Flonum))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[12.0 15.0 18.0 21.0])
procedure
(array-axis-count arr k pred?) → (Array Index)
arr : (Array A) k : Integer pred? : (A -> Any)
> (define arr (index-array #(3 3))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2] #[3 4 5] #[6 7 8]])
> (array-axis-count arr 1 odd?)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[1 2 1])
procedure
(array-axis-and arr k) → (Array (U A Boolean))
arr : (Array A) k : Integer
procedure
(array-axis-or arr k) → (Array (U A #f))
arr : (Array A) k : Integer
> (define second? (ann #f Boolean))
> (define arr (parameterize ([array-strictness #f]) (build-array #(2) (λ: ([js : Indexes]) (cond [(zero? (vector-ref js 0)) #f] [else (set! second? #t) #t])))))
> (array-axis-and arr 0)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Boolean))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #f)
> second? - : Boolean
#f
6.13.2 Whole-Array Folds
> (define arr (index-array #(3 4))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2 3] #[4 5 6 7] #[8 9 10 11]])
> (array-fold arr (λ: ([arr : (Array Integer)] [k : Index]) (array-axis-sum arr k)))
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array 66)
> (apply + (array->list arr)) - : Integer [more precisely: Nonnegative-Integer]
66
> (array-ref (array-fold arr (inst array->list-array (Listof* Integer))) #()) - : (U (Listof (Rec g8466622 (U (Listof g8466622) Integer))) Index)
'((0 1 2 3) (4 5 6 7) (8 9 10 11))
procedure
(array-all-fold arr f) → A
arr : (Array A) f : (A A -> A) (array-all-fold arr f init) → A arr : (Array A) f : (A A -> A) init : A
(array-ref (array-fold arr (λ: ([arr : (Array A)] [k : Index]) (array-axis-fold arr k f))) #())
> (define arr (index-array #(3 4))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2 3] #[4 5 6 7] #[8 9 10 11]])
> (array-all-fold arr +) - : Integer [more precisely: Nonnegative-Integer]
66
> (array-all-fold (array #[]) + 0.0) - : Flonum [more precisely: Nonnegative-Flonum]
0.0
syntax
(array-all-sum arr)
(array-all-sum arr init)
syntax
(array-all-prod arr)
(array-all-prod arr init)
arr : (Array Number)
init : Number
syntax
(array-all-min arr)
(array-all-min arr init)
syntax
(array-all-max arr)
(array-all-max arr init)
arr : (Array Real)
init : Real
> (define arr (index-array #(3 4))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2 3] #[4 5 6 7] #[8 9 10 11]])
> (array-all-fold arr +) - : Integer [more precisely: Nonnegative-Integer]
66
> (array-all-sum arr) - : Integer [more precisely: Nonnegative-Integer]
66
> (array-all-sum arr 0.0) - : Real [more precisely: Nonnegative-Real]
66.0
procedure
(array-all-and arr) → (U A Boolean)
arr : (Array A)
procedure
(array-all-or arr) → (U A #f)
arr : (Array A)
> (define arr (index-array #(3 3))) > (array-all-and (array= arr arr)) - : Boolean
#t
> (define brr (array+ arr (array 1))) > (array-all-and (array= arr brr)) - : Boolean
#f
> (array-all-or (array= arr (array 0))) - : Boolean
#t
(parameterize ([array-strictness #f]) (array-ref (array-fold arr array-axis-and) #()))
syntax
(array-count pred? arrs ...)
arrs : (Array Ts)
pred? : (Ts ... -> Any)
> (array-count zero? (array #[#[0 1 0 2] #[0 3 -1 4]])) - : Integer [more precisely: Index]
3
> (array-count equal? (array #[#[0 1] #[2 3] #[0 1] #[2 3]]) (array #[0 1])) - : Integer [more precisely: Index]
4
syntax
(array-andmap pred? arrs ...)
syntax
(array-ormap pred? arrs ...)
arrs : (Array Ts)
pred? : (Ts ... -> Any)
> (array-andmap equal? (array #[#[0 1] #[0 1] #[0 1] #[0 1]]) (array #[0 1])) - : Boolean
#t
> (array-ormap equal? (array #[#[0 2] #[2 3] #[1 1] #[2 3]]) (array #[0 1])) - : Boolean
#t
> (array-ormap equal? (array->list-array (array #[#[0 2] #[2 3] #[1 1] #[2 3]])) (array->list-array (array #[0 1]))) - : Boolean
#f
(parameterize ([array-strictness #f]) (array-all-and (array-map pred? arrs ...)))
6.13.3 General Reductions and Expansions
procedure
(array-axis-reduce arr k h) → (Array B)
arr : (Array A) k : Integer h : (Index (Integer -> A) -> B)
The arguments to h are the length of axis k and a procedure that retrieves elements from that axis’s rows by their indexes in axis k. It should return the elements of the resulting array.
> (define arr (index-array #(3 3))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2] #[3 4 5] #[6 7 8]])
> (array-axis-reduce arr 1 (λ: ([dk : Index] [proc : (Integer -> Real)]) (for/fold: ([s : Real 0]) ([jk (in-range dk)]) (+ s (sqr (proc jk))))))
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Real))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[5 50 149])
> (array-axis-sum (array-map sqr arr) 1)
- : #(struct:Array
(Indexes
Index
(Boxof Boolean)
(-> Void)
(-> Indexes Nonnegative-Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[5 50 149])
> (array-map (inst reverse Index) (array-axis-fold arr 1 (inst cons Index (Listof Index)) empty))
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes (Listof Index)))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #['(0 1 2) '(3 4 5) '(6 7 8)])
> (array-axis-reduce arr 1 (inst build-list Index))
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes (Listof Index)))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #['(0 1 2) '(3 4 5) '(6 7 8)])
Every fold, including array-axis-fold, is ultimately defined using array-axis-reduce or its unsafe counterpart.
procedure
(array-axis-expand arr k dk g) → (Array B)
arr : (Array A) k : Integer dk : Integer g : (A Index -> B)
Conceptually, g is applied dk times to each element in each row of axis k, once for each nonnegative index jk < dk.
> (define arr (array #['#(a b c) '#(d e f) '#(g h i)])) > (array-axis-expand arr 1 3 vector-ref)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Any))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#['a 'b 'c] #['d 'e 'f] #['g 'h 'i]])
> (array-axis-expand (list->array '(1 2 3 4)) 1 5 expt)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Positive-Integer))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[1 1 1 1 1] #[1 2 4 8 16] #[1 3 9 27 81] #[1 4 16 64 256]])
This function is a dual of array-axis-reduce in that it can be used to invert applications of array-axis-reduce. To do so, g should be a destructuring function that is dual to the constructor passed to array-axis-reduce. Example dual pairs are vector-ref and build-vector, and list-ref and build-list.
(Do not pass list-ref to array-axis-expand if you care about performance, though. See list-array->array for a more efficient solution.)
procedure
(array->list-array arr [k]) → (Array (Listof A))
arr : (Array A) k : Integer = 0
> (define arr (index-array #(3 3))) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2] #[3 4 5] #[6 7 8]])
> (array->list-array arr 1)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes (Listof Index)))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #['(0 1 2) '(3 4 5) '(6 7 8)])
> (array-ref (array->list-array (array->list-array arr 1) 0) #()) - : (Listof (Listof Index))
'((0 1 2) (3 4 5) (6 7 8))
procedure
(list-array->array arr [k]) → (Array A)
arr : (Array (Listof A)) k : Integer = 0
> (define arr (array->list-array (index-array #(3 3)) 1)) > arr
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes (Listof Index)))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #['(0 1 2) '(3 4 5) '(6 7 8)])
> (list-array->array arr 1)
- : #(struct:Array
(Indexes Index (Boxof Boolean) (-> Void) (-> Indexes Index))
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:56:13 prop:equal+hash>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:55:13 prop:custom-write>
#<syntax:build/user/8.14.0.2/pkgs/math-lib/math/private/array/typed-array-struct.rkt:54:13 prop:custom-print-quotable>)
(array #[#[0 1 2] #[3 4 5] #[6 7 8]])
For fixed k, this function and array->list-array are mutual inverses with respect to their array arguments.