SRFI 231 change of the day: Define array-foldl and array-foldr instead of array-fold and array-fold-right
Bradley Lucier 12 Jan 2022 17:18 UTC
The list of differences between SRFI 231 and SRFI 179 includea
===================================================================
The SRFI 179 procedures array-fold and array-fold-right have been
replaced by array-foldl and array-foldr, which follow the definition of
the left and right folds in Ocaml and Haskell. The left folds of Ocaml
and Haskell differ from the (left) fold of SRFI 1, so array-foldl from
this SRFI has different semantics to array-fold from SRFI 179.
===================================================================
In the end I found array-fold to be counter-intuitive.
Alex Shinn made some comments here:
https://srfi-email.schemers.org/srfi-179/msg/17412787/
where he mentions matrix multiplication as a noncommutative operation.
The file test-arrays has some tests of array-fold{l|r} and array-reduce
with 2x2 matrix multiplication, which is not commutative and which I
include below.
Maybe I'm opening a can of worms, but I like the new way.
Brad
;;; OK, how to test array-reduce?
;;; Well, we take an associative, non-commutative operation,
;;; multiplying 2x2 matrices, with data such that doing operations
;;; in the opposite order gives the wrong answer, doing it for the
;;; wrong interval (e.g., swapping axes) gives the wrong answer.
;;; This is not in the same style as the other tests, which use random
;;; data to a great extent, but I couldn't see how to choose random
;;; data that would satisfy the constraints.
(define matrix vector)
(define (2x2-multiply A B)
(let ((a_11 (vector-ref A 0)) (a_12 (vector-ref A 1))
(a_21 (vector-ref A 2)) (a_22 (vector-ref A 3))
(b_11 (vector-ref B 0)) (b_12 (vector-ref B 1))
(b_21 (vector-ref B 2)) (b_22 (vector-ref B 3)))
(vector (+ (* a_11 b_11) (* a_12 b_21)) (+ (* a_11 b_12) (* a_12 b_22))
(+ (* a_21 b_11) (* a_22 b_21)) (+ (* a_21 b_12) (* a_22
b_22)))))
(define A (make-array (make-interval '#(1) '#(11))
(lambda (i)
(if (even? i)
(matrix 1 i
0 1)
(matrix 1 0
i 1)))))
(test (array-reduce 2x2-multiply A)
(array-foldr 2x2-multiply (matrix 1 0 0 1) A))
(test (array-reduce 2x2-multiply A)
(array-foldl 2x2-multiply (matrix 1 0 0 1) A))
(define A_2 (make-array (make-interval '#(1 1) '#(3 7))
(lambda (i j)
(if (and (even? i) (even? j))
(matrix 1 i
j 1)
(matrix 1 j
i -1)))))
(test (array-reduce 2x2-multiply A_2)
(array-foldr 2x2-multiply (matrix 1 0 0 1) A_2))
(test (array-reduce 2x2-multiply A_2)
(array-foldl 2x2-multiply (matrix 1 0 0 1) A_2))
(test (equal? (array-reduce 2x2-multiply A_2)
(array-reduce 2x2-multiply (array-permute A_2
(index-rotate (array-dimension A_2) 1))))
#f)
(define A_3 (make-array (make-interval '#(1 1 1) '#(3 5 4))
(lambda (i j k)
(if (and (even? i) (even? j))
(matrix 1 i
j k)
(matrix k j
i -1)))))
(test (array-reduce 2x2-multiply A_3)
(array-foldr 2x2-multiply (matrix 1 0 0 1) A_3))
(test (array-reduce 2x2-multiply A_3)
(array-foldl 2x2-multiply (matrix 1 0 0 1) A_3))
(test (equal? (array-reduce 2x2-multiply A_3)
(array-reduce 2x2-multiply (array-permute A_3
(index-rotate (array-dimension A_3) 1))))
#f)
(define A_4 (make-array (make-interval '#(1 1 1 1) '#(3 2 4 3))
(lambda (i j k l)
(if (and (even? i) (even? j))
(matrix l i
j k)
(matrix l k
i j)))))
(test (array-reduce 2x2-multiply A_4)
(array-foldr 2x2-multiply (matrix 1 0 0 1) A_4))
(test (array-reduce 2x2-multiply A_4)
(array-foldl 2x2-multiply (matrix 1 0 0 1) A_4))
(test (equal? (array-reduce 2x2-multiply A_4)
(array-reduce 2x2-multiply (array-permute A_4
(index-rotate (array-dimension A_4) 1))))
#f)
(define A_5 (make-array (make-interval '#(1 1 1 1 1) '#(3 2 4 3 3))
(lambda (i j k l m)
(if (even? m)
(matrix (+ m l) i
j k)
(matrix (- l m) k
i j)))))
(test (array-reduce 2x2-multiply A_5)
(array-foldr 2x2-multiply (matrix 1 0 0 1) A_5))
(test (equal? (array-reduce 2x2-multiply A_5)
(array-reduce 2x2-multiply (array-permute A_5
(index-rotate (array-dimension A_5) 1))))
#f)