CSE 413 -- Assignment 3 -- Higher-Order Functions

Due at the beginning of lecture, Monday, April 26, 1999. You should hand in

A printout of the Scheme source code for your program.
A console transcript demonstrating that your program works properly on a variety of input data. If you implement any extensions to the basic problem, be sure to demonstrate them.

In Scheme, we can define a function that yields the sum of the elements of a list as follows:
```
    (define (sumlist x)
       (if (null? x)
       0
       (+ (car x) (sumlist (cdr x)))))`
  
```
A function to calculate the product of the elements in a list looks very similar, the only difference is the function used in the calculation and the identity element (0 or 1) that is the base case.
```
    (define (prodlist x)
       (if (null? x)
       1
       (* (car x) (prodlist (cdr x)))))
```
Both of these functions combine the first element in the list with the result of combining all of the elements to the right.

(a) Implement a higher-order function fold-right that combines the elements in a list as does sumlist and prodlist, except that the operation (+ or *) and the base case (0 or 1) should be parameters. The result of evaluating
```
     (fold-right + 0 '(1 2 3 4 5))
```
should be 15. Evaluating
```
     (fold-right * 1 '(1 2 3 4 5))
```
should give 120.

(b) Give new definitions of sumlist and prodlist using fold-right.

(c) In normal infix notation, fold-right evaluates the expression
```
     (x op (x op (x op (...(x op id)...))))
```
(here x represents the list elements). Give the definition of a related function fold-left that works in the opposite direction
```
     ((((...(id op x)...) op x) op x) op x)
```
(d) What property should op satisfy so that fold-right and fold-left will produce the same values for any list argument?
An interesting feature of the Smalltalk programming language is that standard control structures, like C's for, are implemented as library functions, not as built-in parts of the language. Instead, these control structures are implemented by calling a function closure repeatedly for each of the successive values of the iteration variable. The current value of the iteration expression is an argument to the function each time it is called. Using Scheme syntax, execution of
```
     (for lo hi block)
```
executes (block n) repeatedly, with n taking on values from lo to hi successively. The effect is the same as executing the loop
```
     for each value of n from lo to hi
          (block n)
```
For example, execution of
```
     (for 1 5 (lambda (n) (display n)))
```
should display the numbers 1 2 3 4 5.

(a) Give a definition of function for that works as described above. Give some examples to show that it works.

(b) Define a function (sum-range lo hi) that uses for to yield the sum of the numbers from lo to hi. Execution of, for example, (sum-range 5 17) should have the same effect as the following procedural pseudo-code.
```
     sum := 0;
     for each value of n from 5 to 17
          sum := sum + n;
     return sum;
```
Hints: You may find it useful to include some local bindings (let, lambda, or something similar) in your definition of sum-range. You also may find set! or other functions with side effects to be very useful.

Thought question (not to be turned in): How would you implement the loop while as a closure-style control structure like for?