On 5/4/20 10:14 AM, John Cowan wrote:
> +1.  These correspond loosely to the CL functions array-row-major-aref,
> which takes a single index, and array-row-major-index, which takes
> indices and returns a single index acceptable to array-row-major-aref.
>
> On Sun, May 3, 2020 at 11:59 PM Bradley Lucier <xxxxxx@purdue.edu
> <mailto:xxxxxx@purdue.edu>> wrote:
>
>     I haven't put reshape operators into the SRFI because, in general, they
>     are not affine, so they don't compose with the other existing array
>     transformations.
>
>     But there is one important class of reshape operators that *are*
>     affine,
>     where one maps the elements of a d-dimensional array lexicographically
>     to a one-dimensional array with the same volume.  (The inverse
>     transform, for example, is not affine.)

Here's when reshaping one array into another leads to an affine mapping.

Assume A is the original array, with domain an interval called A-domain,
and B-domain is an interval proposed as the domain of the new array.
(At this point we don't care what type of array A is, we're just asking
about mappings between intervals.)

Then the lexicographical (row-major) mapping from B-domain to A-domain
is affine if and only if

(define (array-reshape-affine? A-domain B-domain)

   ;; A-domain is the domain of the original array to be shared,
   ;; B-domain is the proposed domain of the new array

   (define (interval-sub-volumes interval)
     (fold-right (lambda (len res)
                   (cons (* len (car res))
                         res))
                 '(1)
                 (map -
                      (interval-upper-bounds->list interval)
                      (interval-lower-bounds->list interval))))

   (let ((A-volumes (interval-sub-volumes A-domain))
         (B-volumes (interval-sub-volumes B-domain)))
     (every? (lambda (size)
               (memv size B-volumes))
             A-volumes)))

returns #t.  Basically, if and only if the volumes of all possible
curried subarrays of A are in the set of volumes of all possible curried
subarrays of B.

In particular, if A-domain is one-dimensional and B-domain has the same
volume as A-domain, then the mapping from B-domain to A-domain is affine
(which is the example I gave in my previous email).

Here are some examples:

 > (array-reshape-affine? (make-interval '#(10)) (make-interval '#(2 5)))
#t
 > (array-reshape-affine? (make-interval '#(5 3)) (make-interval '#(3 5)))
#f
 > (array-reshape-affine? (make-interval '#(5 9)) (make-interval '#(3 3 5)))
#f
 > (array-reshape-affine? (make-interval '#(9 5)) (make-interval '#(3 3 5)))
#t
 > (array-reshape-affine? (make-interval '#(3 15)) (make-interval '#(3 3
5)))
#t
 > (array-reshape-affine? (make-interval '#(3 1 1 1 15)) (make-interval
'#(3 3 5)))
#t
 > (array-reshape-affine? (make-interval '#(3 15)) (make-interval '#(3 5
3)))
#t
 > (array-reshape-affine? (make-interval '#(3 15)) (make-interval '#(5 3
3)))
#f
 > (array-reshape-affine? (make-interval '#(3 15)) (make-interval '#(3 5
1 1 3)))
#t

This is doable with specialized arrays, but not so easily with
generalized arrays just by manipulating multi-indices.  So I would propose

(specialized-array-reshape A I)

where A is the array to be shared with a reshaped array, and I is an
interval that is the proposed domain of the new array.

Allowing only affine transformations keeps the resulting array
specialized, so it can be curried, rotated, etc.

Brad