Re: SRFI-1's fold is not fold-left!

[Peter Kourzanov <peter.kourzanov@xxxxxxxxx>]

On Sat, 2012-11-03 at 12:39 +0000, Taylor R Campbell wrote: 
> Date: Sat, 03 Nov 2012 13:17:22 +0100
>    From: Peter Kourzanov <peter.kourzanov@xxxxxxxxx>
> 
>    > While translating some OCaml code I have come across the following
>    > discrepancy. Although it is known, it is worthwhile to mention it, I
>    > think. The SRFI-1's fold is not actually a fold-left (it is mentioned 
>    > in passing in SRFI-1 itself that F's args are flipped w.r.t. MIT-Scheme
>    > and Haskell). 
> 
> The only flipping here is the coin you flip when deciding which order
> the arguments are supposed to go in when specifying the operation.
> Haskell and MIT Scheme do it one way; SML and SRFI 1 do it the other
> way.  Neither one is the `actual' fold-left; I'm sure you can find
> lots more examples of both, under various names including `fold' and
> `foldl' and `fold-left' and `reduce'.

Yet, in many books one typically finds (fold-left f z x0 ... xn) defined as:

(f ... (f (f z x0) x1) ... xn)

and not as:

(f xn ... (f x1 (f x0 z))...)

which rather looks like a (fold-right f z (reverse x0 ... xn)).

As a bonus, BTW, the implementation of the "correct" generic fold-left
can avoid the linear overhead in (destructively) appending the
accumulator to the list of heads each round (I found this to be an 
issue in both SLIB and in Bigloo).

> Drawing a distinction between `fold [left]' (f xi state) and `fold
> left' (f state xi) is likely only to confuse matters further, I
> suspect.  (E.g., already, in SML, foldl is your `fold [left]' and not
> your `fold left'.)

All true. Still, when one finds himself chasing this silly issue
as the only bug left (after having done type-erasure and getting rid 
of horrific OCaml syntax), one does wish for the better.

What complicates matters too is the fact that SRFI-1 is careful enough
to avoid describing FOLD as fold-left. There goes much of the beautiful
symmetry in the underlying theory of lists. And probably many potential
users explicitly searching for a fold-left list iterator.

Kind regards,
Pjotr Kourzanov

P.S. BTW, how many programs do we expect to see converted from SML to 
     Scheme?