Wednesday, August 18, 2021

Fold right

fold-left takes arguments like this:

(fold-left function init list)
and computes
* (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-right function init list)
It computes
* (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-right function list final)
* (fold-right (lambda (l r) `(f ,l ,r)) '(a b c) 'final)
(F A (F B (F C FINAL)))
The argument lists to 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.


Leah Neukirchen said...

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

Gambiteer said...

If I take SRFI-1's `fold-left`:
(define (fold-left kons knil lis)
(if (null? lis)
(fold kons (kons (car lis) knil) (cdr lis))))
> (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.

Joe Marshall said...

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 ...)

steck said...

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

Gambiteer said...

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)

Gambiteer said...

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)
(fold-left f (f init (car l)) (cdr l))))

(define (fold-right f l final)
(if (null? l)
(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?

steck said...

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".

John Cowan said...

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.