Note: Designing Abstractions from Templates

At the very beginning of this part of the book, we discussed how we design sets of functions from the same template. More specifically, when we design a set of functions that all consume the same kind of data, we reuse the same template over and over again. It is therefore not surprising that the function definitions look similar and that we will abstract them later.

Indeed, we could abstract from the templates directly. While this topic is highly advanced and still subject of research in the area of programming languages, we can discuss it with a short example. Consider the template for lists:

(define (fun-for-l l)
  (cond 
    [(empty? l) ...] 
    [else ... (first l) ... (fun-for-l (rest l)) ...])) 

We can abstract over this programming task with the following function:

;; reduce : X (X Y -> Y) (listof Y) -> Y
(define (reduce base combine l) 
  (cond 
    [(empty? l) base] 
    [else (combine (first l) 
            (reduce base combine (rest l)))])) 

Using reduce we can define many plain list-processing functions as well as almost all the functions of figure . Here are two of them:

;; sum : (listof number) -> number
(define (sum l) (reduce 0 + l)) 

;; product : (listof number) -> number
(define (product l) (reduce 1 * l)) 

For sum, the base case always produces 0; adding the first item and the result of the natural recursion combines the values of the second clause. Analogous reasoning explains product.

To define sort, we need to define an auxiliary function first:

;; sort : (listof number) -> (listof number)
(define sort 
  (local ((define (insert an alon) 
            (cond 
              [(empty? alon) (list an)] 
              [else (cond 
                      [(> an (first alon)) (cons an alon)] 
                      [else (cons (first alon) (insert an (rest alon)))])]))) 
    (reduce empty insert)))