Re: array-fold, array-fold-right, and array-reduce

*Alex Shinn* 20 Aug 2021 03:07 UTC

On Fri, Aug 20, 2021 at 9:58 AM Bradley Lucier <xxxxxx@math.purdue.edu> wrote:
>
> SRFI 1 says that
>
> reduce f ridentity list -> value
> reduce is a variant of fold.
>
> ridentity should be a "right identity" of the procedure f -- that
> is, for any value x acceptable to f,
>
> (f x ridentity) = x
>
> reduce has the following definition:
> If list = (), return ridentity;
> Otherwise, return (fold f (car list) (cdr list)).
> ...in other words, we compute (fold f ridentity list).
>
> If the idea is that
>
> (array-reduce f a)
>
> is the same as
>
> (reduce f (array->list a))
Joe's post only talked about fold*, not reduce. We can't actually
match the SRFI 1 reduce exactly because there's no ridentity, but...
> > (reduce (lambda (l r) `(f ,l ,r)) (array->list a))
> (f a_11 (f a_10 (f a_01 a_00)))
> > (array-reduce (lambda (l r) `(f ,l ,r)) a)
> (f (f (f a_00 a_01) a_10) a_11)
This illustrates the bigger problem of the argument order, which is
reversed in SRFI 1 and SRFI 179:
SRFI 1: (f element accumulator)
SRFI 179: (f accumulator element)
This actually tripped me up in my earliest lazy implementations of
SRFI 179 because I tried to define array-reduce as reduce of
array->list, and the tests failed because matrix multiplication is not
commutative!
I think reduce should match the argument order of fold, and the order
in fold seems correct (it works naturally using cons as the kons
argument). So SRFI 1 looks correct, and it may be worth swapping the
order in any revision to SRFI 179.
--
Alex