Lecture overview -- Keyboard shortcut: 'u'  Previous page: Reduction -- Keyboard shortcut: 'p'  Next page: Accumulation -- Keyboard shortcut: 'n'  Lecture notes - all slides and notes together  slide -- Keyboard shortcut: 't'  Help page about these notes  Alphabetic index  Course home  Lecture 2 - Page 28 : 35
Programming Paradigms
Recursion and Higher-order Functions
The reduction functions

The function reduce-right is a straightforward recursive function

The function reduce-left is a straightforward iterative function

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/reduction.scmThe function reduce-right.

Notice the fit between the composition of the list and the recursive pattern of the right reduction.

c:/Users/Kurt/Teaching-material/Pp-Scheme-17/notes/includes/reduction.scmThe function reduce-left.

There is a misfit between left reduction and the recursive composition of the list with heads and tails. However, an iterative process where we successively combine e1 and e2 (giving r1 as the result), r1 and e3 etc., is straightforward. As we have seen several times, this can be done by a tail recursive function, here reduce-help-left.

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)

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)))).

Go to exerciseQuantifier Functions