Folding (also known as reduce or accumulate) is a method of reducing a sequence of terms down to a single term. This is accomplished by providing a fold function with a binary operator, an initial (or identity) value, and a sequence.
There are two kinds of fold: a right one and a left one.
Here's the definition for the fold-right function:
(define (fold-right f init seq) (if (null? seq) init (f (car seq) (fold-right f init (cdr seq)))))
Here are two definitions for fold-left, one recursive, one iterative:
;; iterative definition (define (fold-left f init seq) (define (iter result rest) (if (null? rest) result (iter (f result (car rest)) (cdr rest)))) (iter init seq)) ;; recursive definition (define (fold-left f init seq) (if (null? seq) init (fold-left f (f init (car seq)) (cdr seq))))
(fold-right + 0 '(1 2 3 4)) ; expands to (+ 1 (+ 2 (+ 3 (+ 4 0)))) (fold-left + 0 '(1 2 3 4)) ; expands to (+ (+ (+ (+ 0 1) 2) 3) 4)
A list reversal function can easily be defined using fold-left:
(define (reverse l) (fold-left (lambda (i j) (cons j i)) '() l))