`fold-left`

takes arguments like
this:

(fold-leftand computesfunctioninitlist)

* (fold-left (lambda (l r) `(f ,l ,r)) 'init '(a b c)) (F (F (F INIT A) B) C)Notice how

`init`

is the leftmost
of all the arguments to the function, and each argument appears left
to right as it is folded in.
Now look at the usual way `fold-right`

is
defined:

(fold-rightIt computesfunctioninitlist)

* (fold-right (lambda (l r) `(f ,l ,r)) 'init '(a b c)) (F A (F B (F C INIT)))although

`init`

appears first
and to the left of `'(a b c)`

in the arguments
to `fold-right`

, it is actually used as the rightmost
argument to the last application.
It seems to me that the arguments to `fold-right`

should
be in this order:

; (fold-rightThe argument lists tofunctionlistfinal) * (fold-right (lambda (l r) `(f ,l ,r)) '(a b c) 'final) (F A (F B (F C FINAL)))

`fold-left`

and `fold-right`

would no longer match, but I think
switching things around so that the anti-symmetry of the arguments
matches the anti-symmetry of the folding makes things clearer.
## 8 comments:

OCaml uses different order for the folds:

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

If I take SRFI-1's `fold-left`:

```

(define (fold-left kons knil lis)

(if (null? lis)

knil

(fold kons (kons (car lis) knil) (cdr lis))))

```

then

```

> (fold-left (lambda (l r) `(f ,l ,r)) 'init '(a b c))

(f c (f b (f a init)))

```

which is not your definition. So I'm confused.

You're right! SRFI-1 supplies the arguments to the function in the reverse order of what I implicitly assume. In other words, SRFI-1 assumes the arguments to the function are (element-of-list last-output-of-func), but I define it as taking (last-output-of-func element-of-list).

I think SRFI-1 has made a wrong decision here. If we image extending FOLD-LEFT to take multiple lists, then the calling signature would be something like this: (fold-left func initial list1 list2 ...) and each call to the func would be (func last-output element-of-list1 element-of-list2 ...)

The Jane Street libraries for OCaml put the list first in both cases,

swap the positions of the function and initial value arguments, and swap the

order of the function arguments:

val fold_left : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

val fold_right : 'a t -> f:('a -> 'b -> 'b) -> init:'b -> 'b

OK, so is this something to be fixed? I'm concerned about the definitions of array-fold, array-fold-right, array-reduce in SRFI-179.

If we define the 2x2 array with elements

a_00 a_01

a_10 a_11

Then this is the current behavior, which matches the documentation, but is it the "right thing"?

heine:~/programs/gambit/gambit> gsi

Gambit v4.9.3-1503-gd1a6c6bf

> (import (srfi 179))

> (define a (make-array (make-interval '#(2 2))

(lambda (i j)

(string->symbol (string-append "a_" (number->string i) (number->string j))))))

> (array-fold (lambda (l r) `(f ,l ,r)) 'init a)

(f a_11 (f a_10 (f a_01 (f a_00 init))))

> (array-fold-right (lambda (l r) `(f ,l ,r)) 'init a)

(f a_00 (f a_01 (f a_10 (f a_11 init))))

> (array-reduce (lambda (l r) `(f ,l ,r)) a)

(f (f (f a_00 a_01) a_10) a_11)

When I'd think of fold-left and fold-right and reduce, I'd think of matrix multiplication, so I'd have

(define (fold-left f init l)

(if (null? l)

init

(fold-left f (f init (car l)) (cdr l))))

(define (fold-right f l final)

(if (null? l)

final

(f (car l) (fold-right f (cdr l) final))))

And reduce would assume that f is associative, so the order wouldn't matter.

But SRFI 1 doesn't define things this way.

I don't understand the OCaml notation; how do the OCaml versions work?

Jane Street's fold_left is operationally the same as the Scheme code above.

The fold_right reverses the list, and eta-expands the function, while reversing the function's argument order, to call fold_left. That gets you tail recursion for the fold, at the cost of a (tail-recursive) reversal.

---

let fold_right l ~f ~init =

match l with

| [] -> init

| _ -> fold ~f:(fun a b -> f b a) ~init (rev l)

---

where "fold" is the same as "fold_left".

A more serious inconsistency is that for some of the foldable data structure SRFIs the folding procedure is called in the order

(proc new old)whereas others are(proc old new). Someone prepared a list of these, but I've forgotten where to find that.Post a Comment