fold-left(3scm) Scheme Programmer's Manual fold-left(3scm)

fold-left, fold-right - list iteration and recursion operators 

(import (rnrs))                     ;R6RS
(import (rnrs lists))               ;R6RS


(fold-left combine nil list1 list2 ... listn)
(fold-right combine nil list1 list2 ... listn)

These procedures apply combine to elements of the lists in left to right order or right to left order. They also pass it an argument (called the accumulator) which starts out as nil and is updated to the return value of combine after each application.

The fold-left procedure passes the accumulator as the first argument to combine and fold-right passes it as the last argument. The other arguments are the elements from the lists, i.e., the first time combine it called it gets the first (or last) element from each list, then the second (or second to last) element from each list, etc. The combine procedure should return a single value; the new accumulator.

The accumulator is returned when the lists have been exhausted. This implies that nil is returned immediately if the lists are empty.

The combine procedure is always called in the same dynamic environment as fold-left or fold-right itself. It should not mutate the list arguments.

Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on combine to the extent performed by applying it as described. An implementation may check whether combine is an appropriate argument before applying it.

These procedures return a single value; the last accumulator value. 

(fold-left + 0 '(1 2 3 4 5))
    =>  15
(fold-left (lambda (a e) (cons e a)) '()
           '(1 2 3 4 5))
    =>  (5 4 3 2 1)
(fold-left (lambda (count x)
             (if (odd? x) (+ count 1) count))
           0
           '(3 1 4 1 5 9 2 6 5 3))
    =>  7
(fold-left (lambda (max-len s)
             (max max-len (string-length s)))
           0
           '("longest" "long" "longer"))
    =>  7
(fold-left cons '(q) '(a b c))
    =>  ((((q) . a) . b) . c)
(fold-left + 0 '(1 2 3) '(4 5 6))
    =>  21
(fold-right + 0 '(1 2 3 4 5))
    =>  15
(fold-right cons '() '(1 2 3 4 5))
    =>  (1 2 3 4 5)
(fold-right (lambda (x l)
              (if (odd? x) (cons x l) l))
            '()
            '(3 1 4 1 5 9 2 6 5))
    =>  (3 1 1 5 9 5)
(fold-right cons '(q) '(a b c))
    =>  (a b c q)
(fold-right + 0 '(1 2 3) '(4 5 6))
    =>  21
;; Side-effects in fold are not pretty,
;; but this should highlight the differences
;; between fold-left and fold-right.
(fold-left (lambda (acc x)
             (write (list acc x))
             (newline)
             (+ acc x))
           0
           '(1 2 3 5 7 11))
  -> (0 1)
  -> (1 2)
  -> (3 3)
  -> (6 5)
  -> (11 7)
  -> (18 11)
    => 29
(fold-right (lambda (x acc)
              (write (list x acc))
              (newline)
              (+ x acc))
            0
            '(1 2 3 5 7 11))
  -> (11 0)
  -> (7 11)
  -> (5 18)
  -> (3 23)
  -> (2 26)
  -> (1 28)
    => 29

These are higher-order procedures that express list iteration and recursion. They are often more compact and expressive than writing the corresponding code without them.

These procedures are unique to R6RS, but equivalents can be found in SRFI-1.

This procedure can raise exceptions with the following condition types:
&assertion (R6RS)
The wrong number of arguments was passed or an argument was outside its domain. In particular, the lists should all have the same length and combine must be a procedure. It should accept one more argument than there are lists and return a single value.

map(3scm), let(3scm), do(3scm)

R6RS

These procedures appear in SRFI-1 under the names fold and fold-right where they are respectively referred to as "[t]he fundamental list iterator" and "[t]he fundamental list recursion operator".

This page is part of the scheme-manpages project. It includes materials from the RnRS documents. More information can be found at https://weinholt.se/scheme/manpages/.

2023-08-11