fold

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

Further reading:

• http://en.wikipedia.org/wiki/Fold_(higher-order_function)
• http:/www.cs.nott.ac.uk/~gmh/fold.pdf