   Higher-order Functions
16.  Reduction and zipping

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

 16.1 Reduction 16.4 Zipping 16.2 The reduction functions 16.5 The zipping function 16.3 Accumulation

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.

 Reduction of a list by means of a binary operator transforms the list to a value in the range of the binary operator. 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.

 There is no natural value for reduction of the empty list. Therefore we assume as a precondition that the list is non-empty.

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.

 Expression Value `(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)`
 Table 16.1    Examples of reductions. The - left reduction of the list corresponds to calculating the expression (- (- (- (- 1 2) 3) 4) 5). The - right reduction of the list corresponds to calculating the expression (- 1 (- 2 (- 3 (- 4 5)))).

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.

 The function reduce-right is a straightforward recursive function The function reduce-left is a straightforward iterative function

```1
2
3
4
5
```
```(define (reduce-right f lst)
(if (null? (cdr lst))
(car lst)
(f (car lst)
(reduce-right f (cdr lst)))))```
 Program 16.1    The function reduce-right.

```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)))))```
 Program 16.2    The function reduce-left.

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 is not satisfactory that we cannot reduce the empty listWe remedy the problem by passing an extra parameter to the reduction functionsWe call this variant of the reduction functions for accumulation

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)))))```
 Program 16.3    The function accumulate-right.

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

 Expression Value `(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)`
 Table 16.2    Examples of right accumulations. The first row illustrates that we can accumulate the empty list. The second and third rows are similar to the second and third rows in Table 15.1.

 In relation to web programming we most often append accumulate lists and stringsaccumulate-right is part of the general LAML libraryDue to their deficiencies, the reduction functions are not used in LAML

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.

 Two equally long lists can be pair wise composed to a single list by means of zipping them 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)))))```
 Program 16.4    The function zip.

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.

 Expression Value `(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"`
 Table 16.3    Examples of zipping.

 Zip is similar to the function string-merge from the LAML general libraryHowever, string-merge handles lists of strings non-equal lengths, and it concatenates the zipped results

 Generated: Tuesday July 2, 2013, 09:15:36   