CSE 413 -- Assignment 3 -- Solutions

  1. In Scheme, we can define a function that yields the sum of the elements of a list as follows:
    2.     (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.

    SOLUTION :
         (define (fold-right  op  id lst)
                     (if (null? lst) id
                         (op (car lst) (fold-right op id (cdr lst)))
                     ) ; end of if
         ) ; end of define

    (b) Give new definitions of sumlist and prodlist using fold-right.
     SOLUTION :
             (define (sumlist lst)
            (fold-right + 0 lst))
        (define (prodlist lst)
            (fold-right * 1 lst))
        (Others : append-list was discussed extensively in the mailing list )
        (define (append-list  lst)
            (fold-right append '() lst))
     

    (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
    SOLUTION :
    ;;;  this is easiest to define with an "accumulator" kind of definition using a       ;;;  helper function..
    (define (fold-left  op  id  lst )
      (fold-list-helper op id lst id )
    ;; the helper : Here we just accumulate the result in the accum argument, and return ;; it when we reach the end of the list (base case). This results in the first  element of the list being applied before the second, and so on, adhering exactly
    ;; to the structure
    ;;    (((...(id op x1)...) op xn-2) op xn-1) op xn)
    ;;; where  (x1  x2  ....  xn-1 xn) was the original list lst..
    ;; notice that the ORDER  of  application is not changed compared to fold-right
    ; only WHICH operation HAPPENS first changes.

    (define (fold-list-helper op id lst accum)
                    (if (null? lst)  accum
                            (fold-list-helper  op id  (cdr lst) (op accum (car x)))))

    ;; an alternative solution to fold-left  is to just keep accumulating into the "id"
    (define (fold-left  op id lst)
             (if (null? lst) id
                      (fold-left (op id (car lst)) (cdr lst))))

    (d) What property should op satisfy so that fold-right and fold-left will produce the same values for any list argument?

     SOLUTION:
     Commutativity is essential. That's why fold-left and fold-right don't give the same answer with - or /.
      +, * and append are commutative, so their fold-left and fold-right list implementations give the same answer. Strictly speaking, the correct answer is
    "associative and commutative with respect to id".
     

  2. 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
    3.      (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.

    SOLUTION:
      (define (for lo hi block)
               (if (< lo hi)
                   (begin (block lo) (for (+ lo 1) hi block))
                   (if (= lo hi) (block lo) ;; causes return of last value
                   ); by leaving this out, the return value is unspecified if (lo > hi)
               ); end of outer if
       ) ; end of define

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

     SOLUTION:
    ;; NOTE : let* only lets the first definition to be used in the
    ;;        second definition:    Here sum is defined and used
    ;;        immediately in the next definition.
    ;; (Basically a shorthand for a nested let ..)

           (let*  ((sum  0)
                       ((block n)  (begin (set! sum (+ sum n)) sum))
                      );; end of let definitions
                 (for  5  17 block) ;; will return sum automatically
              )