Homework #9

Assigned: April 7
Due: April 14, 4:30pm


  1. (10 points) The Fibonacci series

    0, 1, 1, 2, 3, 5, 8, 13, 21, ...

    begins with the numbers 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two Fibonacci numbers.

    The Fibonacci series occurs in nature and, in particular, describes a form of a spiral. The ratio of the successive Fibonacci numbers converges on a constant value of 1.618.... This number, too, repeatedly occurs in nature and has been called the golden ratio or the golden mean. Humans tend to find the golden mean aesthetically pleasing. Architects often design windows, rooms, and buildings with a golden mean length/width ratio.

    Define a function fibonacci in Haskell, using only one tail call, which takes a non-negative integer n and returns the nth Fibonacci number. Your definition of fibonacci must execute in O(n) time. You may define one helper function, but it also must use only one tail call. Do not use more than five lines of code. Your function must be invocable as follows:
    Main> fibonacci 0
    0
    Main> fibonacci 1
    1
    Main> fibonacci 2
    1
    Main> fibonacci 3
    2
    Main> fibonacci 4
    3
    Main> fibonacci 5
    5
    Main> fibonacci 6
    8
    Main> fibonacci 7
    13
    Main> fibonacci 8
    21
    Main> fibonacci 20
    6765
    
  2. (10 points) Use call/cc to define a while loop in Scheme without recursion:
    (define mywhile
       (lambda (condition body)
          ...))
    
    You can demonstrate that your while loop is correct by using it to print the numbers from 0 to 9 (one per line) without recursion:
    (define i 0)
    (mywhile '(< i 10) '(begin
       (write i)
       (newline)
       (set! i (+ i 1))))
    

    We will award 5 points extra credit to any student who can define mywhile without using assignment (i.e., set!).

  3. (10 points) Re-write the Scheme definition of the product procedure developed in class without call/cc, retaining the feature that no multiplications are performed if any of the list elements are zero. Do not use continuation-passing style. Moreover, the call stack must only grow to the length of the list plus one (for the original function) once, not more than once.

  4. (10 points) Define a function gcd* in Scheme using continuation-passing style. The function takes only a non-empty list of positive, non-zero integers and a continuation (in that order) and returns the greatest common divisor of those integers. During computation of the gcd, if a 1 is encountered in the list, break out of the function immediately with 1, without returning through any of the recursive calls. Use only tail recursion.

  5. (10 points) Read Paul Graham's essay Beating the Averages and write a 250 word commentary on it. Be clear and concise in your prose.

  6. (5 points) Read M. Swaine's article It's Time to Get Good at Functional Programming from Dr. Dobb's Journal and write a 100 word commentary on it. Be clear and concise in your prose.


Return Home