Higherorder Functions 
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 nonempty. 
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 
(reduceleft  '(1 2 3 4 5))  13 
(reduceright  '(1 2 3 4 5))  3 
(reduceleft stringappend (list "The" " " "End"))  "The End" 
(reduceleft 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 reduceright is a straightforward recursive function The function reduceleft is a straightforward iterative function 
1 2 3 4 5  (define (reduceright f lst) (if (null? (cdr lst)) (car lst) (f (car lst) (reduceright f (cdr lst)))))  

1 2 3 4 5 6 7  (define (reduceleft f lst) (reducehelpleft f (cdr lst) (car lst))) (define (reducehelpleft f lst res) (if (null? lst) res (reducehelpleft 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 is not satisfactory that we cannot reduce the empty list We remedy the problem by passing an extra parameter to the reduction functions We call this variant of the reduction functions for accumulation 
It also turns out that the accumulation function is slightly more useful than reduceleft and reduceright from Section 16.2. The reason is that we control the type of the parameter init to accumulateright in Program 16.3. Because of that, the signature of the accumulate function becomes more versatile than the signatures of reduceleft and reduceright. 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 accumulateright, which performs right accumulation. In contrast to reduceright from Program 16.1accumulateright 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 (accumulateright f init lst) (if (null? lst) init (f (car lst) (accumulateright f init (cdr lst)))))  

The table below shows a few examples of right accumulation, in the sense introduced above.
Expression  Value 
(accumulateright  0 '())  0 
(accumulateright  0 '(1 2 3 4 5))  3 
(accumulateright 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 strings accumulateright is part of the general LAML library Due 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)))))  

Below we show examples of zipping with the zip function. For comparison, we also show an example that involves stringmerge, which we discussed in Section 11.7.
Expression  Value 
(zip cons '(1 2 3) '(a b c))  ((1 . a) (2 . b) (3 . c)) 
(apply stringappend (zip stringappend '("Rip" "Rap" "Rup") '(", " ", and " "")))  "Rip, Rap, and Rup" 
(stringmerge '("Rip" "Rap" "Rup") '(", " ", and "))  "Rip, Rap, and Rup" 
Table 16.3 Examples of zipping. 
Zip is similar to the function stringmerge from the LAML general library However, stringmerge handles lists of strings nonequal lengths, and it concatenates the zipped results 