Am So., 18. Sept. 2022 um 12:41 Uhr schrieb John Cowan <[email protected]>:
> > > On Sun, Sep 18, 2022 at 4:44 AM Marc Nieper-Wißkirchen < > [email protected]> wrote: > > >> The situation with the right fold is not that obvious. The dynamic order >> of the invocations to `car' and `kons' in the definition of `fold-right' in >> SRFI 1 depends on the order in which the implementation evaluates procedure >> arguments. >> > > Can you demonstrate this using a fold-oid with a side-effecting getter? > Chibi evaluates its arguments right to left, Chicken and most other Schemes > (see <https://docs.scheme.org/surveys/argument-order/>) evaluate them > left to right. > The following implements SRFI 1's fold for one list: (define fold-right (lambda (proc seed ls) (let f ((ls ls)) (if (null? ls) seed (proc (car ls) (f (cdr ls))))))) In the last line, one sees that when `(car ls)` is evaluated first, we get SRFI 231's right fold semantics of evaluating all getters first; on the other hand, if `(f (cdr ls))` is evaluated first, we get calls to `proc` interleaved with calls to `car`. A perfectly optimizing Scheme would not choose a fixed evaluation order but the optimal one in each case. If `car` is replaced by a getter with side effects, we get ambiguity. (In fact, there is already an ambiguity in SRFI 1's `fold-right` because `car` looks up the store and the store's contents potentially depend on the evaluation of `proc`.) This ambiguity can be fixed by either one of the following two versions: (define fold-right1 (lambda (proc seed ls) (let f ((ls ls)) (if (null? ls) seed (let ((old-head (car ls))) (proc old-head (f (cdr ls)))))))) (define fold-right2 (lambda (proc seed ls) (let f ((ls ls)) (if (null? ls) seed (let ((new-tail (f (cdr ls)))) (proc (car ls) new-tail)))))) Of course, in general, `null?`, `car` and `cdr` should be replaced by the accessors of the sequence type at hand. I argue that the first fixed version (`fold-right1`) is better and that it is this one that we should standardize. One reason is that this is the same order as demanded in `vector-map` and `string-map` (viewed as specialized versions of right folds). Another more fundamental reason is that `fold-right` categorically defines a catamorphism for the algebra of lists (sequences) of some type T. The endofunctor F defining this algebra is given by: F: X -> 1 + T * X Here, 1 is the unit type, + the disjoint union, and * the product type. F can be seen as the destructor. Given an object of list type, it is either nil (the unit type's value) or a pair consisting of a head and a tail. In other words, conceptually the test for `null?` and `car+cdr` belong together. To make this apparent in Scheme, I have been experimenting with a `list-case` form, which is the fundamental list destructor. So, with it, the better right fold looks like this: (define fold-right1 (lambda (proc seed ls) (let f ((ls ls)) (list-case ls ((h . t) (proc h (f t))) (() seed))))) Using a general matcher, one also arrives at this, more natural version. For example, with the matcher by Friedman/Hilsdale/Dybvig (chosen because of its catamorphism feature), we have (define fold-right1 (lambda (proc seed ls) (match ls ((,h ,(t)) (f h t)) (() seed)))) Also, in what circumstances would the getter naturally be side-effecting? > In the case of generators instead of lists, for example. And when we consider processing time, the getters of streams are naturally side-effecting. PS The above remark about category theory and catamorphism was very brief. If needed, I can say more.
