Fold Functions

A fold function is an abstract function based directly on the template (or templates in the case of mutual reference) where each ... is replaced by a parameter

Consider the following:

;; ListOfX is one of:
;; - empty
;; - (cons X ListOfX)
;; interp. a list of x
 
(define (fn-for-lox lox)
	(cond [(empty? lox) (...)]
		  [else
			  (... (first lox)
				   (fn-for-lox (rest lox)))]))

The first step is to rename the function and notice how many ... are present in the template. We can replace each of those ... with an argument:

(define (fold fn b lox)
	(cond [(empty? lox) b] ; b for base case
		  [else
			  (fn (first lox) ; combination func
				   (fold fn b (rest lox)))]))

Above, we replace the base case with a parameter b, and the second ellipsis with fn. There, fn represents the combination function that combines (first lox) and the natural recursion on (rest lox).

By using the above, we can expect the following tests to pass:

(check-expect (fold + 0 (list 1 2 3)) 6)
(check-expect (fold * 1 (list 1 2 3)) 6)

The signature and purpose, then, can be included as follows:

;;  (X Y -> Y) Y (listof X) -> Y
;; the abstract fold function for (listof X)

Notice that the signature here defines the putput as being of type Y, not X. This is because X type items are passed into the fn parameter, but need not have an output of that type necessarily. However, the base case b must be of the same type, given that the ((empty? lox) b) condition exists.

In the end, the fold function looks as follows:

;;  (X Y -> Y) Y (listof X) -> Y
;; the abstract fold function for (listof X)
(check-expect (fold + 0 (list 1 2 3)) 6)
(check-expect (fold * 1 (list 1 2 3)) 6)
(check-expect (fold string-append "" (list "a" "bc" "def")) ("abcdef"))
 
(define (fold fn b lox)
	(cond [(empty? lox) b]
		  [else
			  (fn (first lox)
				  (fold fn b (rest lox)))]))

The above signature and function are identical to foldr.