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.
OCaml uses different order for the folds:
ReplyDeleteval 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`:
ReplyDelete```
(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).
ReplyDeleteI 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,
ReplyDeleteswap 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.
ReplyDeleteIf 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
ReplyDelete(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.
ReplyDeleteThe 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.
ReplyDelete