I have several questions about the discussion of folds and
reductions and the implementation of FOLDL, PAIR-FOLDL, and REDUCEL.

        (1) All of these procedures take one argument that is a procedure
of arity equal to one plus the number of list arguments.  All of them apply
this procedure along the list arguments, adding an additional
``fold-state'' argument as the _last_ argument.

        I would have expected the folds and reductions that start applying
the procedure at the left end of the list(s) -- FOLDL, PAIR-FOLDL, and
REDUCEL -- to apply the procedure so that it takes the fold-state argument
as the _first_ argument.  For example, I would expect

                    (FOLDL KONS KNIL '(E1 E2 E3 E4 E5))

to have the same value as

        (KONS (KONS (KONS (KONS (KONS KNIL 'E1) 'E2) 'E3) 'E4) 'E5)

However, SRFI-1's FOLDL procedure returns the same value as

        (KONS 'E5 (KONS 'E4 (KONS 'E3 (KONS 'E2 (KONS 'E1 KNIL)))))

        On this point, SRFI-1 includes the following note (at the end of
the discussion of REDUCEL):

# MIT Scheme flips F's arg order for its REDUCE-LEFT and FOLD-LEFT. This is
# a fairly isolated departure from the standard definition of FOLDL used in
# the rest of the (Haskell, ML, Scheme, etc.) FP community. (The MIT Scheme
# implementors had good reasons for choosing the inverted argument order,
# but I do not find them compelling enough to warrant departing from the
# simple, standard definitions.)

        Well, as a member of the FP community, I don't find the SRFI-1
order particularly simple or standard, and in fact my impression is that
the SRFI-1 order is the one that is ``inverted.''  It's true that version
110 of Standard ML provides a SRFI-1-style foldl; however, the Haskell 1.4
report (http://haskell.org/onlinereport/standard-prelude.html) defines
foldl thus:

------------------------------------------------------------------------
foldl            :: (a -> b -> a) -> a -> [b] -> a
foldl f z []     =  z
foldl f z (x:xs) =  foldl f (f z x) xs
------------------------------------------------------------------------

which is the MIT-Scheme order, not the SRFI-1 order.

        The only advantage I can think of in the SRFI-1 order is that it's
so much fun to write REVERSE as (LAMBDA (LIS) (FOLDL CONS '() LIS)),
whereas with the MIT-Scheme order you have to write (LAMBDA (LIS) (FOLDL
XCONS '() LIS)) instead.

        Maybe I'm missing something, but I think that at the least a better
justification is needed for this design decision, and unless one is
forthcoming I'd prefer procedures with the argument order that MIT Scheme
and Haskell have used.  This does not complicate the coding.  On the
contrary, it makes it more natural -- you can use %CARS instead of %CARS+,
and (CONS ANS LISTS) instead of (APPEND! LISTS (LIST ANS)):

------------------------------------------------------------------------
(define (foldl kons knil lis1 . lists)
  (if (pair? lists)
    (let lp ((lists (cons lis1 lists)) (ans knil))
      (if (%all-pairs? lists)
          (lp (%cdrs lists)
              (apply kons ans (%cars lists)))
          ans))
    (let lp ((lis lis1) (ans knil))
      (if (pair? lis)
          (lp (cdr lis) (kons ans (car lis)))
          ans))))

(define (pair-foldl f zero lis1 . lists)
  (if (pair? lists)
      (let lp ((lists (cons lis1 lists)) (ans zero))
        (if (%all-pairs? lists)
            (let ((tails (%cdrs lists)))
              (lp tails (apply f (cons ans lists))))
            ans))
      (let lp ((lis lis1) (ans zero))
        (if (pair? lis)
            (let ((tail (cdr lis)))
              (lp tail (f ans lis)))
            ans))))

(define (reducel f ridentity lis)
  (if (pair? lis)
      (foldl f (car lis) (cdr lis))
      ridentity))
------------------------------------------------------------------------

        (2) The terminology used in the specification for REDUCEL is messed
up.  In the parlance of mathematicians, a ``right zero'' of a binary
procedure F is a value RZERO such that, for any value X that F accepts as a
first argument, (F X RZERO) is RZERO.  What SRFI-1 calls a right zero is
what is usually called a ``right identity'' -- a value RIDENTITY such that,
for any value X that F accepts as a first argument, (F X RIDENTITY) is X.
There are also left zeroes -- such that (F LZERO X) is LZERO -- and left
identities -- such that (F LIDENTITY X) is X.

        The value that REDUCER returns when its list argument is empty
should be a right identity.  The value that REDUCEL returns when its list
argument is empty should be a left identity of F if the argument order for
F is MIT-Scheme-style, with the fold-state argument on the left, or a right
identity of F if the argument order for F is Standard-ML-style, with the
fold-state argument on the right.

        (3) The specification for REDUCEL also mentions LZERO at one point,
which I assume is a typo.

        (4) The three dots in the syntax picture at the beginning of the
specification of REDUCEL should be deleted.  (Note that the implementation
doesn't handle multiple list arguments.)

        (5) In the syntax picture at the beginning of the specification of
REDUCER, `lis' should be `list'.

--
======  John David Stone - Lecturer in Computer Science and Philosophy  =====
==============  Manager of the Mathematics Local-Area Network  ==============
==============  Grinnell College - Grinnell, Iowa 50112 - USA  ==============
==========  xxxxxx@math.grin.edu - http://www.math.grin.edu/~stone/  =========