• Due: 6pm Friday, October 28.

  • Notes:

    • Solo Problem 1 part d on prefixes was changed to weighted-suffixes on Mon. Oct. 24. The previous prefixes problem has become part of a new extra credit problem.
    • This pset contains a solo problem worth 27 points.
    • This pset has 112 total points.
    • The problems needn’t be done in order. Feel free to jump around.
  • Submission:
    • In your yourFullName CS251 Fall 2016 Folder, create a Google Doc named yourFullName CS251 PS5.
    • At the top of your yourFullName CS251 PS5 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
    • For all parts of all problems, include all answers (including Racket code) in your PS5 google doc. Format small-step derivations and Racket code using a fixed-width font, like Consolas or Courier New. You can use a small font size if that helps.
    • For Problem 1 (Solo Problem: Folding)
      • Be sure that all function definitions in yourAccountName-ps5-solo.rkt also appear in your Google Doc (so that I can comment on them)
      • Drop a copy of your yourAccountName-ps5-solo.rkt in your ~/cs251/drop/ps05 drop folder on cs.wellesley.edu.
    • For Problem 2:
      • Include the English answers to parts a through f in your PS5 google doc.
      • For part g, show a nicely formatted version of your small-step derivation.
    • For Problems 3 through 5:
      • Drop a copy of your yourAccountName-ps5.rkt file in your ~/cs251/drop/ps05 drop folder on cs.wellesley.edu.
      • Be sure that all function definitions in yourAccountName-ps5.rkt also appear in your Google Doc (so that I can comment on them)

1. Solo Problem: Folding (27 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

In this problem you will define four functions via folding operators. Some notes:

  • Define all of your functions in a new file named yourAccountName-ps5-solo.rkt that you create in Dr. Racket.
  • You have seen most of these functions before in PS4 in the context of explicit recursion. But in this problem:
    • You should not use explicit recursion on lists in any of your definitions.
    • You should use higher-order list operations (e.g., foldr, foldr-ternop, map)

  • You may use this map-cons helper function in your definitions:

    (define (map-cons x ys)
  (map (curry cons x) ys))
  • The only built-in Racket list operators you may use in your definitions are: null, null?, cons, list, append, first, second, third, and rest. (You may also use any Racket math or logic operators, such as +, max, etc.)

  1. (6 points) Using foldr, define a function (unzip pairs) that takes a list of pairs (cons cells) and returns a list of two lists that, if zipped together with zip, would yield the original pairs.

    > (unzip '((1 . 5) (2 . 6) (3 . 7) (4 . 8)))
'((1 2 3 4) (5 6 7 8))

> (unzip (zip (list 1 2 3 4) (list 5 6 7 8)))
'((1 2 3 4) (5 6 7 8))
 
> (unzip (list))
'(() ())

    Your definition should flesh out the following skeleton:

    (define (unzip pairs)
  (foldr ; put expression 1 here
         ; put expression 2 here
         pairs))

  2. (6 points) Suppose that we represent a set in Racket as a list without duplicates. Using foldr, define a function (subsets set) that returns a list of all subsets of a given set. The subsets within this can be in any order, but the order of elements within each set should have the same relative order as in set.

    For example here are some of the (huge number of) possible answers for (subsets '(3 1 2)), any single one of which would be considered correct:

    '(() (1) (2) (3) (1 2) (3 1) (3 2) (3 1 2))
'((3 1 2) (3 2) (3 1) (1 2) (3) (2) (1) ())
'(() (2) (1) (1 2) (3) (3 2) (3 1) (3 1 2))  
'((3 1 2) () (3 1) (2) (3) (1 2) (1) (3 2))

    However, lists containing subsets like (2 1), (1 3), (3 2 1), or (1 2 3) could not be solutions, since the elements of these subsets are not in the same relative order as in (3 1 2).

    Your definition should flesh out the following skeleton, and may use other higher-order operators and standard list combiners (e.g. append), but may not use any form of list reversal.

    (define (subsets set)
  (foldr ; put expression 1 here
         ; put expression 2 here
         set))

    Keep in mind that your function needs to produce only one of the potential solutions like those shown above.

  3. (7 points) Using foldr, define a function sum-max-squareEvens that takes a list of integers its single argument and returns a triple (i.e., a three-element list) whose three elements are (1) the sum of the numbers in the list; (2) the maximum of the numbers in the list and (3) a list of the squares of all the even numbers in the list (maintaining relative order).

     > (sum-max-squaresEvens '(9 2 8 5 4 7 1 6 3))
 '(45 9.0 (4 64 16 36))
 > (sum-max-squaresEvens '(2 8 5 4 7 1 6 3))
 '(36 8.0 (4 64 16 36))
 > (sum-max-squaresEvens '(8 5 4 7 1 6 3))
 '(34 8.0 (64 16 36))
 > (sum-max-squaresEvens '(5 4 7 1 6 3))
 '(26 7.0 (16 36))
 > (sum-max-squaresEvens '(-9 2 -8 5 4 -7 1 -6 3))
 '(-15 5.0 (4 64 16 36))
 > (sum-max-squaresEvens (append (range 1 101 7) (range 201 0 -2)))
 '(10951 201.0 (64 484 1296 2500 4096 6084 8464))

    Your sum-max-squareEvens function should make a single pass over the input list to produce the output triple. I.e., you should not have separate recursions for calculating each of the three parts.

    Your definition should flesh out the following skeleton:

    (define (sum-max-squaresEvens ints)
  (foldr ; put expression 1 here
         ; put expression 2 here
         ints))

  4. (8 points) This new Solo Problem 1 part d on weighted-suffixes was posted on on Mon. Oct. 24. It replaces the previous prefixes problem, which is now an extra credit problem.

    A length-n suffix of a list is a list containing its last n elements in the same relative order. For example:

    • The length-0 suffix of '(5 8 4) is '()
    • The length-1 suffix of '(5 8 4) is '(4)
    • The length-2 suffix of '(5 8 4) is '(8 4)
    • The length-3 suffix of '(5 8 4) is '(5 8 4)

    Based on this definition, imagine a function suffixes that takes a list as its single argument and returns a list of all of its suffixes ordered from longest to shortest. For example:

     > (suffixes '(5 8 4))
 '((5 8 4) (8 4) (4) ())  
 > (suffixes '(2 5 8 4))
 '((2 5 8 4) (5 8 4) (8 4) (4) ())
 > (suffixes '(7 2 5 8 4))
 '((7 2 5 8 4) (2 5 8 4) (5 8 4) (8 4) (4) ())
 > (suffixes (range 1 11))
 '((1 2 3 4 5 6 7 8 9 10)
   (2 3 4 5 6 7 8 9 10)
   (3 4 5 6 7 8 9 10)
   (4 5 6 7 8 9 10)
   (5 6 7 8 9 10)
   (6 7 8 9 10)
   (7 8 9 10)
   (8 9 10)
   (9 10)
   (10)
   ())

    In this problem, you are not asked to define suffixes, but are instead asked to define a related function named weighted-suffixes, which is assumed to take a list of numbers. The result of weighted-suffixes is a list similar to that returned by suffixes except that each nonempty sublist in the result of weighted-suffixes is the result of scaling all numbers in the corresponding nonempty sublist in the result of suffixes by its first element. (The empty sublist in suffixes yields the empty sublist in weighted-suffixes).

    For example, (weighted-suffixes '(7 2 5 8 4)) returns '((49 14 35 56 28) (4 10 16 8) (25 40 20) (64 32) (16) ()) because:

    • (49 14 35 56 28) is the result of scaling (7 2 5 8 4) by 7
    • (4 10 16 8) is the result of scaling (2 5 8 4) by 2
    • (25 40 20) is the result of scaling (5 8 4) by 5
    • (64 32) is the result of scaling (8 4) by 8
    • (16) is the result of scaling (4) by 4
    • () is the sublist in the result of weighted-suffixes that corresponds to the sublist () in the result of suffixes

    Here are more examples of weighted-suffixes, the last two of which illustrate negative numbers:

     > (weighted-suffixes (range 3 8))
 '((9 12 15 18 21) (16 20 24 28) (25 30 35) (36 42) (49) ())

 > (weighted-suffixes (range 1 11))
 '((1 2 3 4 5 6 7 8 9 10)
   (4 6 8 10 12 14 16 18 20)
   (9 12 15 18 21 24 27 30)
   (16 20 24 28 32 36 40)
   (25 30 35 40 45 50)
   (36 42 48 54 60)
   (49 56 63 70)
   (64 72 80)
   (81 90)
   (100)
   ())
    
 > (weighted-suffixes '(-2 6 1 -3 -8 4 7 -5))
 '((4 -12 -2 6 16 -8 -14 10)
   (36 6 -18 -48 24 42 -30)
   (1 -3 -8 4 7 -5)
   (9 24 -12 -21 15)
   (64 -32 -56 40)
   (16 28 -20)
   (49 -35)
   (25)
   ())

 > (weighted-suffixes (range -3 4))
 '((9 6 3 0 -3 -6 -9) (4 2 0 -2 -4 -6) (1 0 -1 -2 -3) (0 0 0 0) (1 2 3) (4 6) (9) ())

    In this problem, use foldr-ternop to defined weighted-suffixes. Your definition should flesh out the following skeleton:

    (define (weighted-suffixes nums)
  (foldr-ternop ; put expression 1 here
                ; put expression 2 here
                nums))

    Your definition may also use map.

2. Backus’s Paper (30 points)

This problem is about John Backus’s 1977 Turing Award Lecture: Can Programming be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs. His paper can be found here.

You should begin this problem by reading Sections 1–11 and 15–16 of this paper. (Although Sections 12–14 are very interesting, they require more time than I want you to spend on this problem.)

Section 11.2 introduces the details of the FP language. Backus uses many notations that may be unfamiliar to you. For example:

  • p1 → e1; … ; pn → en; en+1 is similar to the Racket expression (if p1e1… (if pnenen+1) … ).

  • ⟨e1, …, en⟩ denotes the sequence of the n values of the expressions e1, … en. φ denotes the empty sequence. Because FP is dynamically typed, such sequences can represent both tuples and lists from Python and OCaml.

  • The symbol ⊥ (pronounced “bottom”) denotes the value of an expression that doesn’t terminate (i.e., it loops infinitely) or terminates with an error.

  • If f is a function and x is an object (atom or sequence of objects), then f : x denotes the result of applying f to x.

  • [f1, …, fn] is a functional form denoting a sequence of n functions, f1 through fn. The application rule for this functional form is [f1, …, fn] : x = ⟨f1 : x, … , fn : x⟩ — i.e., the result of applying a sequence of n functions to an object x is an n-element sequence consisting of the results of applying each of the functions in the function sequence to x.

Consult Lyn if you have trouble understanding Backus’s notation.

Answer the following questions about Backus’s paper. Your answers should be concise but informative.

  1. (2 points) One of the reasons this paper is well-known is that in it Backus coined the term “von Neumann bottleneck”. Describe what this is and its relevance to the paper.

  2. (2 points) Many programming languages have at least two syntactic categories: expressions and statements. Backus claims that expressions are good but statements are bad. Explain his claim.

  3. (3 points) In Sections 6, 7, and 9 of the paper, Backus discusses three problems/defects with von Neumann languages. Summarize them.

  4. (3 points) What are applicative languages and how do they address the three problems/defects mentioned by Backus for von Neumann languages?

  5. (2 points) The FP language Backus introduces in Section 11 does not support abstraction expressions like Racket’s lambda. Why did Backus make this decision in FP?

  6. (6 points) Backus wrote this paper long before the development of Java and Python. Based on his paper, how do you think he would evaluate these two languages?

  7. (12 points) Consider the following FP definition:

    Def F ≡ α/+ ◦ αα× ◦ αdistl ◦ distr ◦ [id, id]

    What is the value of F⟨2, 3, 5⟩? Show the evaluation of this expression in a sequence of small-step algebra-like steps.

3. Compositional Programming (18 points)

Consider the following sum-nested-filtered-cubes function:

(define (sum-nested-filtered-cubes n)
  (foldr + 0
         (map (λ (row)
                (foldr + 0
                       (filter (λ (cubed) (>= (remainder cubed 10) 5))
                               (map (λ (n) (expt n 3))
                                    row))))
              (map (λ (i) (range 1 (+ i 1)))
                   (range 1 (+ n 1))))))

Given a nonnegative input n, it calculates

  1. (12 points) Consider the following helper functions:

    (define (id x) x)
(define (o f g) (λ (x) (f (g x))))
(define (o-all funs) (foldr o (λ (x) x) funs))
(define (curry2 binop) (λ (x) (λ (y) (binop x y))))
(define (curry3 ternop) (λ (x) (λ (y) (λ (z) (ternop x y z)))))
(define (flip2 binop) (λ (x y) (binop y x)))

    Using such functions, we can express nested invocations like those in sum-nested-filtered-cubes using compositions of combinators, which are expressions that denote functions without using explicit lambdas. For example, here is a definition for a function that sums the squares of odd integers from 1 up to (and including) a given limit:

    (define sum-of-squares-of-odds-up-to-composed
  (λ (n)
    (foldr + 0
       (map (λ (x) (expt x 2))
            (filter (λ (i) (= 1 (remainder i 2)))
                    (range 1 (+ 1 n)))))))

> (sum-of-squares-of-odds-up-to-composed 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    We cam now transform this in a sequence of steps into a definition that does not use any lambdas. First, however, we will iintroduce a bunch of lambdas so that we can express the nested expressions above in terms of o-all.

    (define sum-of-squares-of-odds-up-to-composed2
  (o-all (list (λ (squares) (foldr + 0 squares))
               (λ (odds) (map (λ (x) (expt x 2)) odds))
               (λ (ints) (filter (λ (i) (= 1 (remainder i 2))) ints))
               (λ (hi) (range 1 hi))
               (λ (n) (+ 1 n))
               )))

> (sum-of-squares-of-odds-up-to-composed2 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    Now we can use curry2 and curry3 to remove the outermost lambdas.

    (define sum-of-squares-of-odds-up-to-composed3
  (o-all (list (((curry3 foldr) +) 0)
               ((curry2 map) (λ (x) (expt x 2)))
               ((curry2 filter) (λ (i) (= 1 (remainder i 2))))
               ((curry2 range) 1)
               ((curry2 +) 1)
               )))

> (sum-of-squares-of-odds-up-to-composed3 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    Now we use flip2 and o to prepare the remaining lambdas for removal

    (define sum-of-squares-of-odds-up-to-composed4
  (o-all (list (((curry3 foldr) +) 0)
               ((curry2 map) (λ (x) ((flip2 expt) 2 x)))
               ((curry2 filter) (o (λ (k) (= 1 k)) (λ (i) ((flip2 remainder) 2 i))))
               ((curry2 range) 1)
               ((curry2 +) 1)
               )))

> (sum-of-squares-of-odds-up-to-composed4 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    Finally we use curry2 to eliminate the remaining lambdas:

    (define sum-of-squares-of-odds-up-to-composed5
  (o-all (list (((curry3 foldr) +) 0)
               ((curry2 map) ((curry2 (flip2 expt)) 2))
               ((curry2 filter) (o ((curry2 =) 1) ((curry2 (flip2 remainder)) 2)))
               ((curry2 range) 1)
               ((curry2 +) 1)
               )))

> (sum-of-squares-of-odds-up-to-composed 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

    Give a similar sequence of transformations that starts with sum-nested-filtered-cubes and ends with a definition that has the following pattern, where each of the functions <fun_1> through <fun_k> is expressed without using any explicit lambdas:

    (define sum-nested-filtered-cubes-composed
  (o-all (list <fun_1> 
               ...
               <fun_k>)))

    Notes:

    • Liberally use helper functions as in the definition of sum-of-squares-of-odds-up-to-composed. If you can’t get rid of all explicit lambdas, get rid of as many as you can.

    • It is recommended that you start with a version sum-nested-filtered-cubes-composed with explicit lambdas and remove one at a time, checking that the resulting definition behaves like the original after each removal. For example, to test on inputs between 0 and 10 inclusive:

      > (map (λ (n) (cons n (sum-nested-filtered-cubes-composed))) (range 11))
'((0 . 0) (1 . 0) (2 . 8) (3 . 43) (4 . 78) (5 . 238) (6 . 614) (7 . 990) (8 . 1366) (9 . 2471) (10 . 3576))

  2. (6 points) In mathematics, the n-fold composition of a function f, written f n is f composed with itself n times. Thus, f 2 = f ◦ f, f 3 = f ◦ f ◦ f, and so on. Note that f 1 = f, and f 0 = the identity function.

    Define a Racket function (n-fold n f) that takes a nonnegative integer n and a unary function f and returns the n-fold composition of f. In your definition, you may not use explicit recursion. There are many different ways to define n-fold without recursion! You are allowed to use higher-order functions we’ve studied (e.g., map, foldr, foldl, iterate, iterate-apply, genlist, genlist-apply) as well as standard Racket functions like range.

    Here are some examples of using n-fold:

    (define (id x) x)
(define (inc x) (+ x 1))
(define (dbl y) (* y 2))

> ((n-fold 2 inc) 0)
2

> ((n-fold 17 inc) 100
117

> ((n-fold 3 dbl) 1)
8

> ((n-fold 2 (o inc dbl)) 5)
23

> ((n-fold 2 (o dbl inc)) 5)
26

> ((n-fold 17 id) 42) 
42

4. Iterating with foldl and iterate (12 points)

  1. (5 points) A naive approach to evaluating a polynomial like x4 + 5x3 + 4x2 + 7x + 2 at input like 3 is to independently raise 3 to the powers 4, 3, 2, 1, 0, multiply each of the 5 coefficients by the 5 powers and finally add the results:

    1*(3*3*3*3) + 5*(3*3*3) + 4*(3*3) + 7*3 + 2*1 
= 1*81 + 5*27 + 4*9 + 21 + 2
= 81 + 135 + 36 + 21 + 2
= 275

    But there is a more efficient approach, known as Horner’s method, that uses only (n + 1) multiplications and (n + 1) additions that calculates the result as:

    ((((0*3 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2
= ((((0 + 1)*3 + 5)*3 + 4)*3 + 7)*3 + 2
= (((1*3 + 5)*3 + 4)*3 + 7)*3 + 2
= (((3 + 5)*3 + 4)*3 + 7)*3 + 2
= ((8*3 + 4)*3 + 7)*3 + 2
= ((24 + 4)*3 + 7)*3 + 2
= (28*3 + 7)*3 + 2
= (84 + 7)*3 + 2
= 91*3 + 2
= 273 + 2
= 275

    Horner’s method for polynomial evaluation is remarkably simple to express using foldl on the lists of coeffcients. Show this by completing the following skeleton for the poly-eval function:

    (define (poly-eval coeffs x)
  (foldl {combining function} 
         {initial value}
         coeffs))

    For example:

    > (poly-eval (list 1 5 4 7 2) 3)
275

> (poly-eval (list 1 5 4 7 2) 0)
2 

> (poly-eval (list 1 5 4 7 2) 1)
19 

> (poly-eval (list 1 5 4 7 2) 10)
15472

;; Use map to test a bunch of inputs in parallel
> (map ((curry2 poly-eval) (list 1 5 4 7 2)) (range 11))
'(2 19 88 275 670 1387 2564 4363 6970 10595 15472)

;; Hey, can use this to convert binary numbers to decimal!
> (poly-eval (list 1 0 1 0 1 0) 2)
42

> (poly-eval (list 1 1 1 1 1 0 1 1) 2)
251

;; Or to convert hex to decimal:
> (poly-eval (list 6 1) 16)
97

> (poly-eval (list 1 7 4 9) 16)
5961

  2. (7 points) The iterative process of converting a decimal number to a sequence of binary bits is illustrated by the following iteration table for the conversion of the decimal number 38 to binary bits:

    num bits Notes
    38 ()  
    19 (0) 38 mod 2 = 0
    9 (1 0) 19 mod 2 = 1
    4 (1 1 0) 9 mod 2 = 1
    2 (0 1 1 0) 4 mod 2 = 0
    1 (0 0 1 1 0) 2 mod 2 = 0
    0 (1 0 0 1 1 0) 1 mod 2 = 1

    Based on this idea, use either iterate or iterate-apply from lecture to define a function (bits n) that takes a nonnegative integer n and returns a list of the bits for the binary representation of n. For example:

    > (bits 46)
'(1 0 1 1 1 0)

> (bits 251)
  '(1 1 1 1 1 0 1 1)

> (bits 1729)
'(1 1 0 1 1 0 0 0 0 0 1)

> (bits 1)
'(1)

> (bits 0)
'(0) ; Special case!

    Notes:

    • Here are the definitions of iterate and iterate-apply
    (define (iterate next done? finalize state)
  (if (done? state)
      (finalize state)
      (iterate next done? finalize (next state))))

(define (iterate-apply next done? finalize state)
  (if (apply done? state)
      (apply finalize state)
      (iterate-apply next done? finalize (apply next state))))

    • Handle an input of 0 as a special case.

    • As noted above, you can use poly-eval to test your results!

5. Pair Generation (25 points)

Consider the following Python pairs function, whose single argument n you may asssume is a positive integer

def pairs(n): # Assume n is a positive integer
    result = []
    for diff in range (1, n+1):
        for start in range(0, n+1-diff):
            result.append((start, start+diff))
    return result

  1. (2 points) The pairs function generates a list of pairs of integers related to input n, in a very particular order. Carefully describe in English the output list of pairs in terms of n. Do not describe the Python code or algorithm that generates the pairs. Instead, specify (1) exactly what pairs are in the output list and (2) exactly what order they are in. Your description must be precise enough that someone else could implement the pairs function correctly based on your description, without seeing the original Python definition.

  2. (6 points) Define a Racket function pairs-hof that has the same input-output behavior as the Python pairs function but is expressed in terms of nestings of higher order list functions like foldr and map in conjunction with standard list operators like append and range. (``hof” means higher-order function). Do not use filter, foldl, genlist, genlist-apply, iterate, or iterate-apply in this part. Also, a Python pair (v1, v2) should be represented as the dotted pair cons-cell (v1 . v2) in Racket.

  3. (7 points) Recall the genlist function presented in lecture for generating lists:

    (define (genlist next done? keepDoneValue? seed)
  (if (done? seed)
      (if keepDoneValue? (list seed) null)
      (cons seed
            (genlist next done? keepDoneValue? (next seed)))))

    Define a Racket function pairs-genlist that has the same input-output behavior as the Python pairs function but is defined using genlist by fleshing out the missing expressions in curly braces in the following skeleton:

    (define (pairs-genlist n) ; Assume is n a positive integer
  (genlist {next function goes here}
           {done? function goes here}
           {keepDoneValue? boolean goes here}
           {seed goes here}))

  4. (10 points) Define a Racket function pairs-iter that has the same input-output behavior as the Python pairs function but is expressed iteratively in terms of one or more tail-recursive functions. Unlike the Python pairs function and Racket pairs-genlist function, which add pairs from the front of the list to the end, your pairs-iter implementation should add pairs from the end of the list to the beginning.

    Notes:

    • You should not use iterate or iterate-apply in this problem! Instead, you should define one or more tail-recursive functions specialized for this particular problem.

    • You should not perform any list reversals in your pairs-iter definition.

    • There are many solution approaches, but some involve more than one tail recursive function. (Two nested loops in the Python pairs function naturally correspond to a pair of mutually recursive tail recursive functions.)

    • The pairs-iter function need not itself be recursive; it can call one or more tail-recursive functions.

    • The Python nested loop solution builds the list of pairs from the first pair forward because in Python it is most natural to add elements to the end of a list accumulator via .append. However, in Racket, it is most natural to add elements to the beginning of a list via cons. Therefore, in this problem, you should start with an empty list and add elements from the last pair backwards. E.g., for (pairs-iter 5), you should first add the pair '(0 . 5) to the empty list '(), then add '(1 . 5) to the list '((0 . 5)), then add '(0 . 4) to the list '((1 . 5) (0 . 5)), and so on.

    • It is helpful to use iteration tables involving concrete examples to help you define your tail recursive function(s). Here is the beginning of an iteration table that is inspired by a nested loop solution for (pairs-iter 5):

      n diff start pairsSoFar
      5 5 0 ()
      5 4 1 ((0 . 5))
      5 4 0 ((1 . 5) (0 . 5))
      5 3 2 ((0 . 4) (1 . 5) (0 . 5))
      5 3 1 ((2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 3 0 ((1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 2 3 ((0 . 3) (1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 2 2 ((3 . 5) (0 . 3) (1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 … … ((3 . 5) (0 . 3) (1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))

      One way to go from the above iteration table to a tail-recursive function is to have a single tail recursive function with arguments that have the names of the columns.

      Another way to go from the above iteration table is to develop two mutually recursive tail recursive functions that each use some of the names of the columns as arguments. E.g., an outer tail recursive function would be responsible for decrementing the diff, while an inner tail recursive function would be responsible for decrementing the start.

    • IMPORTANT: Just naming a function to end in -tail does not make it tail recursive! In order to be tail recursive, all calls of your tail recursive functions must not be subexpressions of other function calls. E.g. in the code

      (if <test>
    <then> 
    (pairs-outer-tail (pairs-inner-tail ...) ...))

      the call to pairs-outer-tail is a tail call, but the the call to pairs-inner-tail is not a tail call (because it is a subexpression of another call.

Extra Credit: More Folding (22 points)

This new optional extra credit problem was posted on Mon. Oct. 24. It includes (part a) the original Solo Problem 1 part d prefixes function that has been replaced by weighted-suffixes.

  1. (5 points) A length-n prefix of a list is a list containing its first n elements in the same relative order. For example:

    • The length-0 prefix of '(5 8 4) is '()
    • The length-1 prefix of '(5 8 4) is '(5)
    • The length-2 prefix of '(5 8 4) is '(5 8)
    • The length-3 prefix of '(5 8 4) is '(5 8 4)

    Using foldr and map-cons, define a function prefixes that takes a list as its single argument and returns a list of all of its prefixes ordered from shortest to longest. For example:

     > (prefixes '(5 8 4))
 '(() (5) (5 8) (5 8 4))
 > (prefixes '(2 5 8 4))
 '(() (2) (2 5) (2 5 8) (2 5 8 4))
 > (prefixes '(7 2 5 8 4))
 '(() (7) (7 2) (7 2 5) (7 2 5 8) (7 2 5 8 4))
 > (prefixes (range 0 11))
 '(()
   (0)
   (0 1)
   (0 1 2)
   (0 1 2 3)
   (0 1 2 3 4)
   (0 1 2 3 4 5)
   (0 1 2 3 4 5 6)
   (0 1 2 3 4 5 6 7)
   (0 1 2 3 4 5 6 7 8)
   (0 1 2 3 4 5 6 7 8 9)
   (0 1 2 3 4 5 6 7 8 9 10))

    Your definition should flesh out the following skeleton:

    (define (prefixes xs)
  (foldr ; put expression 1 here
         ; put expression 2 here
         xs))

  2. (5 points) The suffixes function is defined in Solo Problem 1 part d. Here, use foldr to define suffixes. Your definition should flesh out the following skeleton:

    (define (suffixes xs)
  (foldr ; put expression 1 here
         ; put expression 2 here
         xs))

  3. (12 points) In Solo Problem 1 part d you were asked to define the weighted-suffixes function in terms of foldr-ternop. It is possible, but challenging, to define weighted-suffixes in terms of foldr instead. As in the definition of sorted-foldr? Extra Credit problem from PS4, the result of weighted-suffixes needn’t be the direct result of foldr; it’s OK to transform the result of foldr to get the result of weighted-suffixes. That is, your definition of weighted-suffixes should have them form:

    (define (weighted-suffixes nums)
  (let {[foldr-result (foldr ; put expression 1 here
                             ; put expression 2 here
                             nums)]}
    ; put expression 3 here that transforms foldr-result
    ))

Extra Credit: Church Numerals (25 points)

This problem is optional. You should only attempt it after completing all the other problems.

The curried n-fold operator cn-fold, defined below has some interesting properties.

(define cn-fold (curry2 n-fold))
(define twice (cn-fold 2))
(define thrice (cn-fold 3))

> ((twice inc) 0)
2

> ((thrice inc) 0)
3

> ((twice dbl) 1)
4

> ((thrice dbl) 1)
8

In Church’s λ-calculus, it turns out that a function equivalent to (cn-fold n) can be used to represent the nonnegative integer n. As you can see above, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.

  1. (10 points) In the following questions suppose that a and b are nonnegative integers and f is a unary function. Justify your answer to each question.

    (1) (o (n-fold a f) (n-fold b f)) is equivalent to (n-fold p f) for what number p?

    (2) (o (cn-fold a) (cn-fold b)) is equivalent to (cn-fold q) for what number q?

    (3) ((cn-fold a) (cn-fold b)) is equivalent to (cn-fold r) for what number r?

  2. (5 points) Define a function inc that takes as its argument a Church numeral for n and returns the Church numeral for n+1. That is, for any n, (inc (cn-fold n)) should return a Church numeral equivalent to (cn-fold (+ n 1)).

  3. (10 points) Define a function dec that takes as its argument a Church numeral for n and returns the Church numeral for n-1; in the special case where n is 0, it should return the Churchn numeral for 0.