PS5: Iterate Until Done
 Due: 6pm Friday, October 28.

Notes:
 Solo Problem 1 part d on
prefixes
was changed toweightedsuffixes
on Mon. Oct. 24. The previousprefixes
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.
 Solo Problem 1 part d on
 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 smallstep derivations and Racket code using a fixedwidth 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
yourAccountNameps5solo.rkt
also appear in your Google Doc (so that I can comment on them)  Drop a copy of your
yourAccountNameps5solo.rkt
in your~/cs251/drop/ps05
drop folder on cs.wellesley.edu.
 Be sure that all function definitions in
 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 smallstep derivation.
 For Problems 3 through 5:
 Drop a copy of your
yourAccountNameps5.rkt
file in your~/cs251/drop/ps05
drop folder on cs.wellesley.edu.  Be sure that all function definitions in
yourAccountNameps5.rkt
also appear in your Google Doc (so that I can comment on them)
 Drop a copy of your
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
yourAccountNameps5solo.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 higherorder list operations (e.g.,
foldr
,foldrternop
,map
)

You may use this
mapcons
helper function in your definitions:(define (mapcons x ys) (map (curry cons x) ys))
 The only builtin Racket list operators you may use in your definitions are:
null
,null?
,cons
,list
,append
,first
,second
,third
, andrest
. (You may also use any Racket math or logic operators, such as+
,max
, etc.)

(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 withzip
, 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))

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

(7 points) Using
foldr
, define a functionsummaxsquareEvens
that takes a list of integers its single argument and returns a triple (i.e., a threeelement 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).> (summaxsquaresEvens '(9 2 8 5 4 7 1 6 3)) '(45 9.0 (4 64 16 36)) > (summaxsquaresEvens '(2 8 5 4 7 1 6 3)) '(36 8.0 (4 64 16 36)) > (summaxsquaresEvens '(8 5 4 7 1 6 3)) '(34 8.0 (64 16 36)) > (summaxsquaresEvens '(5 4 7 1 6 3)) '(26 7.0 (16 36)) > (summaxsquaresEvens '(9 2 8 5 4 7 1 6 3)) '(15 5.0 (4 64 16 36)) > (summaxsquaresEvens (append (range 1 101 7) (range 201 0 2))) '(10951 201.0 (64 484 1296 2500 4096 6084 8464))
Your
summaxsquareEvens
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 (summaxsquaresEvens ints) (foldr ; put expression 1 here ; put expression 2 here ints))

(8 points) This new Solo Problem 1 part d on
weightedsuffixes
was posted on on Mon. Oct. 24. It replaces the previousprefixes
problem, which is now an extra credit problem.A lengthn suffix of a list is a list containing its last n elements in the same relative order. For example:
 The length0 suffix of
'(5 8 4)
is'()
 The length1 suffix of
'(5 8 4)
is'(4)
 The length2 suffix of
'(5 8 4)
is'(8 4)
 The length3 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 namedweightedsuffixes
, which is assumed to take a list of numbers. The result ofweightedsuffixes
is a list similar to that returned bysuffixes
except that each nonempty sublist in the result ofweightedsuffixes
is the result of scaling all numbers in the corresponding nonempty sublist in the result ofsuffixes
by its first element. (The empty sublist insuffixes
yields the empty sublist inweightedsuffixes
).For example,
(weightedsuffixes '(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)
by7
(4 10 16 8)
is the result of scaling(2 5 8 4)
by2
(25 40 20)
is the result of scaling(5 8 4)
by5
(64 32)
is the result of scaling(8 4)
by8
(16)
is the result of scaling(4)
by4
()
is the sublist in the result ofweightedsuffixes
that corresponds to the sublist()
in the result ofsuffixes
Here are more examples of
weightedsuffixes
, the last two of which illustrate negative numbers:> (weightedsuffixes (range 3 8)) '((9 12 15 18 21) (16 20 24 28) (25 30 35) (36 42) (49) ()) > (weightedsuffixes (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) ()) > (weightedsuffixes '(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) ()) > (weightedsuffixes (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
foldrternop
to definedweightedsuffixes
. Your definition should flesh out the following skeleton:(define (weightedsuffixes nums) (foldrternop ; put expression 1 here ; put expression 2 here nums))
Your definition may also use
map
.  The length0 suffix of
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:

p_{1} → e_{1}; … ; p_{n} → e_{n}; e_{n+1} is similar to the Racket expression
(if
p_{1}e_{1}
…
(if
p_{n}e_{n}
e_{n+1}
)
…)
. 
⟨e_{1}, …, e_{n}⟩ denotes the sequence of the n values of the expressions e_{1}, … e_{n}. φ 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.

[f_{1}, …, f_{n}] is a functional form denoting a sequence of n functions, f_{1} through f_{n}. The application rule for this functional form is [f_{1}, …, f_{n}] : x = ⟨f_{1} : x, … , f_{n} : x⟩ — i.e., the result of applying a sequence of n functions to an object x is an nelement 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.

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

(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 points) In Sections 6, 7, and 9 of the paper, Backus discusses three problems/defects with von Neumann languages. Summarize them.

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

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

(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 smallstep algebralike steps.
3. Compositional Programming (18 points)
Consider the following sumnestedfilteredcubes
function:
(define (sumnestedfilteredcubes 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

(12 points) Consider the following helper functions:
(define (id x) x) (define (o f g) (λ (x) (f (g x)))) (define (oall 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
sumnestedfilteredcubes
using compositions of combinators, which are expressions that denote functions without using explicitlambda
s. 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 sumofsquaresofoddsuptocomposed (λ (n) (foldr + 0 (map (λ (x) (expt x 2)) (filter (λ (i) (= 1 (remainder i 2))) (range 1 (+ 1 n))))))) > (sumofsquaresofoddsuptocomposed 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
oall
.(define sumofsquaresofoddsuptocomposed2 (oall (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)) ))) > (sumofsquaresofoddsuptocomposed2 9) 165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2
Now we can use
curry2
andcurry3
to remove the outermost lambdas.(define sumofsquaresofoddsuptocomposed3 (oall (list (((curry3 foldr) +) 0) ((curry2 map) (λ (x) (expt x 2))) ((curry2 filter) (λ (i) (= 1 (remainder i 2)))) ((curry2 range) 1) ((curry2 +) 1) ))) > (sumofsquaresofoddsuptocomposed3 9) 165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2
Now we use
flip2
ando
to prepare the remaining lambdas for removal(define sumofsquaresofoddsuptocomposed4 (oall (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) ))) > (sumofsquaresofoddsuptocomposed4 9) 165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2
Finally we use
curry2
to eliminate the remaining lambdas:(define sumofsquaresofoddsuptocomposed5 (oall (list (((curry3 foldr) +) 0) ((curry2 map) ((curry2 (flip2 expt)) 2)) ((curry2 filter) (o ((curry2 =) 1) ((curry2 (flip2 remainder)) 2))) ((curry2 range) 1) ((curry2 +) 1) ))) > (sumofsquaresofoddsuptocomposed 9) 165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2
Give a similar sequence of transformations that starts with
sumnestedfilteredcubes
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 explicitlambda
s:(define sumnestedfilteredcubescomposed (oall (list <fun_1> ... <fun_k>)))
Notes:

Liberally use helper functions as in the definition of
sumofsquaresofoddsuptocomposed
. If you can’t get rid of all explicitlambda
s, get rid of as many as you can. 
It is recommended that you start with a version
sumnestedfilteredcubescomposed
with explicitlambdas
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 (sumnestedfilteredcubescomposed))) (range 11)) '((0 . 0) (1 . 0) (2 . 8) (3 . 43) (4 . 78) (5 . 238) (6 . 614) (7 . 990) (8 . 1366) (9 . 2471) (10 . 3576))


(6 points) In mathematics, the nfold 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
(nfold n f)
that takes a nonnegative integern
and a unary functionf
and returns the nfold composition off
. In your definition, you may not use explicit recursion. There are many different ways to definenfold
without recursion! You are allowed to use higherorder functions we’ve studied (e.g.,map
,foldr
,foldl
,iterate
,iterateapply
,genlist
,genlistapply
) as well as standard Racket functions likerange
.Here are some examples of using
nfold
:(define (id x) x) (define (inc x) (+ x 1)) (define (dbl y) (* y 2)) > ((nfold 2 inc) 0) 2 > ((nfold 17 inc) 100 117 > ((nfold 3 dbl) 1) 8 > ((nfold 2 (o inc dbl)) 5) 23 > ((nfold 2 (o dbl inc)) 5) 26 > ((nfold 17 id) 42) 42
4. Iterating with foldl
and iterate
(12 points)

(5 points) A naive approach to evaluating a polynomial like x^{4} + 5x^{3} + 4x^{2} + 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 thepolyeval
function:(define (polyeval coeffs x) (foldl {combining function} {initial value} coeffs))
For example:
> (polyeval (list 1 5 4 7 2) 3) 275 > (polyeval (list 1 5 4 7 2) 0) 2 > (polyeval (list 1 5 4 7 2) 1) 19 > (polyeval (list 1 5 4 7 2) 10) 15472 ;; Use map to test a bunch of inputs in parallel > (map ((curry2 polyeval) (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! > (polyeval (list 1 0 1 0 1 0) 2) 42 > (polyeval (list 1 1 1 1 1 0 1 1) 2) 251 ;; Or to convert hex to decimal: > (polyeval (list 6 1) 16) 97 > (polyeval (list 1 7 4 9) 16) 5961

(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
oriterateapply
from lecture to define a function(bits n)
that takes a nonnegative integern
and returns a list of the bits for the binary representation ofn
. 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
anditerateapply
(define (iterate next done? finalize state) (if (done? state) (finalize state) (iterate next done? finalize (next state)))) (define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))

Handle an input of 0 as a special case.

As noted above, you can use
polyeval
to test your results!
 Here are the definitions of
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+1diff):
result.append((start, start+diff))
return result

(2 points) The
pairs
function generates a list of pairs of integers related to inputn
, in a very particular order. Carefully describe in English the output list of pairs in terms ofn
. 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 thepairs
function correctly based on your description, without seeing the original Python definition. 
(6 points) Define a Racket function
pairshof
that has the same inputoutput behavior as the Pythonpairs
function but is expressed in terms of nestings of higher order list functions likefoldr
andmap
in conjunction with standard list operators likeappend
andrange
. (``hof” means higherorder function). Do not usefilter
,foldl
,genlist
,genlistapply
,iterate
, oriterateapply
in this part. Also, a Python pair(v1, v2)
should be represented as the dotted pair conscell(v1 . v2)
in Racket. 
(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
pairsgenlist
that has the same inputoutput behavior as the Pythonpairs
function but is defined usinggenlist
by fleshing out the missing expressions in curly braces in the following skeleton:(define (pairsgenlist n) ; Assume is n a positive integer (genlist {next function goes here} {done? function goes here} {keepDoneValue? boolean goes here} {seed goes here}))

(10 points) Define a Racket function
pairsiter
that has the same inputoutput behavior as the Pythonpairs
function but is expressed iteratively in terms of one or more tailrecursive functions. Unlike the Pythonpairs
function and Racketpairsgenlist
function, which add pairs from the front of the list to the end, yourpairsiter
implementation should add pairs from the end of the list to the beginning.Notes:

You should not use
iterate
oriterateapply
in this problem! Instead, you should define one or more tailrecursive functions specialized for this particular problem. 
You should not perform any list reversals in your
pairsiter
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
pairsiter
function need not itself be recursive; it can call one or more tailrecursive 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 viacons
. Therefore, in this problem, you should start with an empty list and add elements from the last pair backwards. E.g., for(pairsiter 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
(pairsiter 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 tailrecursive 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 thestart
. 
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> (pairsoutertail (pairsinnertail ...) ...))
the call to
pairsoutertail
is a tail call, but the the call topairsinnertail
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 weightedsuffixes
.

(5 points) A lengthn prefix of a list is a list containing its first n elements in the same relative order. For example:
 The length0 prefix of
'(5 8 4)
is'()
 The length1 prefix of
'(5 8 4)
is'(5)
 The length2 prefix of
'(5 8 4)
is'(5 8)
 The length3 prefix of
'(5 8 4)
is'(5 8 4)
Using
foldr
andmapcons
, define a functionprefixes
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))
 The length0 prefix of

(5 points) The
suffixes
function is defined in Solo Problem 1 part d. Here, usefoldr
to definesuffixes
. Your definition should flesh out the following skeleton:(define (suffixes xs) (foldr ; put expression 1 here ; put expression 2 here xs))

(12 points) In Solo Problem 1 part d you were asked to define the
weightedsuffixes
function in terms offoldrternop
. It is possible, but challenging, to defineweightedsuffixes
in terms offoldr
instead. As in the definition ofsortedfoldr?
Extra Credit problem from PS4, the result ofweightedsuffixes
needn’t be the direct result offoldr
; it’s OK to transform the result offoldr
to get the result ofweightedsuffixes
. That is, your definition ofweightedsuffixes
should have them form:(define (weightedsuffixes nums) (let {[foldrresult (foldr ; put expression 1 here ; put expression 2 here nums)]} ; put expression 3 here that transforms foldrresult ))
Extra Credit: Church Numerals (25 points)
This problem is optional. You should only attempt it after completing all the other problems.
The curried nfold
operator cnfold
, defined below has some interesting properties.
(define cnfold (curry2 nfold))
(define twice (cnfold 2))
(define thrice (cnfold 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 (cnfold 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.

(10 points) In the following questions suppose that
a
andb
are nonnegative integers andf
is a unary function. Justify your answer to each question.(1)
(o (nfold a f) (nfold b f))
is equivalent to(nfold p f)
for what numberp
?(2)
(o (cnfold a) (cnfold b))
is equivalent to(cnfold q)
for what numberq
?(3)
((cnfold a) (cnfold b))
is equivalent to(cnfold r)
for what numberr
? 
(5 points) Define a function
inc
that takes as its argument a Church numeral forn
and returns the Church numeral forn+1
. That is, for anyn
,(inc (cnfold n))
should return a Church numeral equivalent to(cnfold (+ n 1))
. 
(10 points) Define a function
dec
that takes as its argument a Church numeral forn
and returns the Church numeral forn1
; in the special case wheren
is0
, it should return the Churchn numeral for0
.