I am posting this as an individual member of the Scheme community. I am not speaking for the R6RS editors, and this message should not be confused with the editors' eventual formal response.
AndrevanTonder <andre_at_het.brown.edu> wrote:
> That is interesting. In addition to breaking with SRFI-1, r5.92rs fold-left is
> also inconsistent with
>
> - PLT Scheme foldl
> - Guile fold.
>
> On the other hand, I notice that the current 5.92 argument order
> coincides with that of
>
> - MIT Scheme
> - Haskell
> - Mathematica
OCaml is also a member of the latter set.
> I think it would probably cause the least amount of confusion if r6rs were to
> follow srfi-1 and PLT, as the formal comment suggests, but I am curious as to
> whether there is a deeper reason why the r5.92rs order has been proposed.
Informally and intuitively, the fold-right procedure folds a procedure over the elements of a list in right-to-left order, whereas fold-left uses left-to-right order.
Given this reversal in order, in the general case it makes sense for the arguments to the provided procedure to also be reversed. An example of the reason for this can be seen when folding the subtraction operation (which is non-associative and non-commutative) over a list, for example:
(fold-right - 0 '(10 3 2 1)) ;=> (10 - (3 - (2 - (1 - 0)))) = 8
(fold-right - 1 '(10 3 2)) ;=> (10 - (3 - (2 - 1))) = 8
(fold-left - 10 '(3 2 1)) ;=> (((10 - 3) - 2) - 1) = 4
(srfi1-fold - 10 '(3 2 1)) ;=> (1 - (2 - (3 - 10))) = -8
Another way to characterize the behavior of the R5.92RS procedures, which can be seen in the infix expansions above, is that fold-right applies its procedure as though it associates to the right, whereas fold-left applies its procedure as though it associates to the left. This mnemonic fails for the SRFI-1 fold.
>From this perspective, the SRFI-1 'fold' procedure (which I note doesn't mention 'left' anywhere in its name or definition) seems a rather strange beast, and perhaps should be called something more like 'fold-reverse'.
There are a couple of nice diagrams on the Wikipedia page about fold, under the heading "Another approach":
http://en.wikipedia.org/wiki/Fold_(higher-order_function)
These diagrams are consistent with the R5.92RS definitions. A similar diagram for SRFI-1 fold would have as its right-hand side:
f
/ \
5 f
/ \
4 f
/ \
3 f
/ \
2 f
/ \
1 z
...which is identical to the right-hand side tree for foldr, except that the list elements are reversed (hence my suggestion of the name 'fold-reverse').
The SRFI-1 argument order seems to derive from the argument order of 'cons', but generalizing away from 'cons', this rationale doesn't hold.
Anton
Received on Mon Jan 29 2007 - 00:16:00 UTC