Folds and reductions

*John David Stone*08 Jan 1999 22:13 UTCI 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/ =========