The reduction and zipping functions work on lists, like map and filter from Chapter 15.

16.1.  Reduction
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

List reduction is useful when we need somehow to 'boil down' a list to a 'single value'. The boiling is done with a binary function, as illustrated in Figure 16.1.

Figure 16.1    Left and right reduction of a list. Left reduction is - quite naturally - shown to the left, and right reduction to the right.

The intuitive idea of reduction will probably be more clear when we meet examples in Table 16.1 below.

Examples of left and right reduction are given in the table below. Be sure to understand the difference between left and right reduction, when the function, with which we reduce, is not commutative.

(reduce-left - '(1 2 3 4 5))

-13

(reduce-right - '(1 2 3 4 5))

3

(reduce-left string-append (list "The" " " "End"))

"The End"

(reduce-left append 
  (list (list 1 2 3) (list 'a 'b 'c)))

(1 2 3 a b c)

16.2.  The reduction functions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We will now implement the reduction functions introduced above in Section 16.1. Both right reduction and left reduction will be implemented, not least because they together illustrate a good point about iterative and tail recursive processing of lists. The explanations of this is found in the captions of Program 16.1 and Program 16.2.

1
2
3
4
5

(define (reduce-right f lst)
  (if (null? (cdr lst))
      (car lst)
      (f (car lst) 
         (reduce-right f (cdr lst)))))

1
2
3
4
5
6
7

(define (reduce-left f lst)
  (reduce-help-left f (cdr lst) (car lst)))

(define (reduce-help-left f lst res)
  (if (null? lst)
      res
      (reduce-help-left f (cdr lst) (f res (car lst)))))

In summary, right reduction is easy to program with a recursive function. The reason is that we can reduce the problem to (f (car lst) X), where X a right reduction of (cdr lst) with f. The right reduction of (cdr lst) is smaller problem than the original problem, and therefore we eventually meet the case where the list is trivial (in this case, a single element list).

The left reduction combines the elements one after the other, iteratively. First we calculate (f (car el) (cadr el)), provided that the list is of length 2 or longer. Let us call this value Y. Next (f Y (caddr el)) is calculated, and so on in an iterative way. We could easily program this with a simple loop control structure, like a for loop.

16.3.  Accumulation
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In this section we introduce a variation of reduction, which allows us also to reduce the empty list. We chose to use the word accumulation for this variant.

It also turns out that the accumulation function is slightly more useful than reduce-left and reduce-right from Section 16.2. The reason is that we control the type of the parameter init to accumulate-right in Program 16.3. Because of that, the signature of the accumulate function becomes more versatile than the signatures of reduce-left and reduce-right. Honestly, this is not easy to spot in Scheme, whereas in languages like Haskell and ML, it would have been more obvious.

Below we show the function accumulate-right, which performs right accumulation. In contrast to reduce-right from Program 16.1accumulate-right also handles the extreme case of the empty list. If the list is empty, we use the explicitly passed init value as the result.

1
2
3
4

(define (accumulate-right f init lst)
  (if (null? lst)
      init
      (f (car lst) (accumulate-right f init (cdr lst)))))

The table below shows a few examples of right accumulation, in the sense introduced above.

(accumulate-right - 0 '())

0

(accumulate-right - 0 '(1 2 3 4 5))

3

(accumulate-right append '()
  (list (list 1 2 3) (list 'a 'b 'c)))

(1 2 3 a b c)

16.4.  Zipping
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The zipping function is named after a zipper, as known from pants and shirts. The image below shows the intuition behind a list zipper.

Figure 16.2    Zipping two lists with the function z. The head of the resulting list is (z e i f i), where the element e i comes from the first list, and f i comes from the other.

We implement the zipping function in the following section.

16.5.  The zipping function
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The zip function in Program 16.4 takes two lists, which are combined element for element. As a precondition, it is assumed that both input list have the same size.

1
2
3
4
5
6

(define (zip z lst1 lst2)
  (if (null? lst1)
      '()
      (cons 
        (z (car lst1) (car lst2))
        (zip z (cdr lst1) (cdr lst2)))))

Below we show examples of zipping with the zip function. For comparison, we also show an example that involves string-merge, which we discussed in Section 11.7.

(zip cons '(1 2 3) '(a b c))

((1 . a) (2 . b) (3 . c))

(apply string-append
 (zip 
  string-append
  '("Rip" "Rap" "Rup")
  '(", " ", and " "")))

"Rip, Rap, and Rup"

(string-merge 
  '("Rip" "Rap" "Rup") '(", " ", and "))

"Rip, Rap, and Rup"