PS5: Iterate Until Done
 Due: 11:59pm Wednesday, March 15.
 Notes:
 This pset contains a solo problem worth 23 points.
 The problems needn’t be done in order. Feel free to jump around.
 Submission:
 In your yourFullName CS251 Spring 2017 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 and Pytbon code) in your PS5 google doc. Format Racket and Python 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 Problems 2 through 5:
 Write all your Racket code in a single file
yourAccountNameps5.rkt
and all your Python code in a single fileyourAccountNameps5.py
.  Drop a copy of your
yourAccountNameps5.rkt
andyourAccountNameps5.py
files in your~/cs251/drop/ps05
drop folder on cs.wellesley.edu.  Be sure that all function definitions in
yourAccountNameps5.rkt
andyourAccountNameps5.py
also appear in your Google Doc (so that I can comment on them)
 Write all your Racket code in a single file
1. Solo Problem: Folding (23 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
,car
,cdr
,list
,append
,first
,second
,third
, andrest
. (You may also use any Racket math or logic operators, such as+
,max
, etc.)

(5 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))

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

(6 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))

(7 points) 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. nfold Composition (10 points)
In mathematics, the composition of unary functions f and g, writen f ◦g is the unary function such that (f ◦g)(x) = f(g(x)).
We can define a composition function o
in Racket as follows:
(define (o f g)
(λ (x) (f (g x))))
Here are some examples of composition:
(define (inc y) (+ y 1))
(define (dbl z) (* z 2))
> ((o inc dbl) 10)
21
> ((o dbl inc) 10)
22
> ((o inc inc) 10)
12
> ((o dbl dbl) 10)
40
The identity function id
is the identity of the composition operator:
(define (id x) x)
> ((o inc id) 10)
11
> ((o id inc) 10)
11
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 id.
In this problem, you will define in a file yourAccountNameps5.rkt
a Racket function (nfold n f)
that takes a nonnegative integer n
and a unary function f
and returns the nfold composition of f
. In your definition, you may not use explicit recursion. There are many different ways to define nfold
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 like range
.
Here are some examples of using nfold
:
> ((nfold 2 inc) 0)
2
> ((nfold 17 inc) 100)
117
> ((nfold 3 dbl) 1)
8
> ((nfold 4 (curry + 3)) 0)
12
> ((nfold 4 (curry * 3)) 1)
81
> ((nfold 2 (o inc dbl)) 5)
23
> ((nfold 2 (o dbl inc)) 5)
26
> ((nfold 17 id) 42)
42
3. Iterating with foldl
and iterate
(12 points)
In this problem, you should define the specified functions polyeval
and bits
in yourAccountNameps5.rkt
.

(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 coefficients. 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 ;; Hey, can use polyeval to convert a sequence of decimal digits to decimal ... > (polyeval (list 1 5 4 7 2) 10) 15472 ;; .. or to convert binary digits 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 digits to decimal (writing 10 for A, 11 for B, etc): > (polyeval (list 6 1) 16) 97 > (polyeval (list 15 11) 16) ; FB in hex 251 > (polyeval (list 1 7 4 9) 16) 5961 ;; Can 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)

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

4. Pair Generation (30 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

(4 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 (in a general way, not giving examples) and (2) exactly what order the pairs 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.Here are snippets of poor specifications similar to ones that students have submitted in past semesters, with suggestions on how to make them better.

“The
pairs
function generates a list of pairs. The second number of the pairs goes from 0 to n, then repeats from 1 to n, and so on until n (included). Each of these numbers in a repetition are enumerated starting from 0, and starts over from 0 at a new repetition. The enumeration is the first number of a pair.” This description is vague, hard to understand, and too closely tied to the algorithm and does not clearly say what the pairs are or how they are ordered. 
”
(pairs n)
generates all possible pairs of numbers between 0 and n.”
Not true!(pairs 3)
does not generate the pair(2.5 . 1.5)
even though 2.5 and 1.5 are numbers between 0 and 3. In a pair (a . b) generated by(pairs n)
, what kind of numbers must a and b be? What are the relationships between 0, a, b, and n? 
“The pairs are sorted like this:
Ex. [(0,1), (1,2),...(n1,n), (0, 2), … (n2, n), … (0, n)]"
Defining the order of pairs by example is not acceptable. Define the order in a much more rigorous way. If you have pairs (a1 . b1) and (a2 . b2), what determines which one comes before the other?


(6 points) In the file
yourAccountNameps5.rkt
, define a Racket functionpairshof
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. 
(8 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)))))
In the file
yourAccountNameps5.rkt
, define a Racket functionpairsgenlist
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}))

(12 points) In the file
yourAccountNameps5.rkt
, define a Racket functionpairsiter
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. 
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 … … … 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. This can be done by defining two toplevel functions
pairsiter
andpairstail
(define (pairsiter n) (pairstail ...)) (define (pairstail ...) ...)
or by defining
pairstail
as a local function withinpairsiter
(define (pairsiter n) (define (pairstail ...) ...) (pairstail ...))
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
. Such functions could all be defined at toplevel(define (pairsiter n) (pairsoutertail ...)) (define (pairsoutertail ...) ...) (define (pairsinnertail ...) ...)
or could be defined in a nested way
(define (pairsiter n) (define (pairsoutertail ...) (define (pairsinnertail ...) ...) ...) (pairsoutertail ...))

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

5. List Processing with Tail Recursion and Loops (25 points)
One or more tailrecursive functions can be used to describe iterations that have complex termination and/or continuation conditions that are challenging to express with traditional looping constructs. In this problem we describe a complex iteration and then ask you (1) to flesh out a collection of tail recursive functions in Racket that implements it and (2) to write an equivalent loop in Python.
The iteration is invoked by a function process
that takes one argument, which is a list of integers. If the list contains any elements other than integers, the behavior of process
is unspecified. The elements of the list are processed left to right as follows:

Processing starts in add mode. In this mode each integer encountered is added to an accumulator that is initially 0, and the final value of the accumulator is return when the end of the list is reached. So in this mode,
(process ints)
just sums the integers inints
. For example:> (process (list 1 2 3 4 5)) 15 ; 1 + 2 + 3 + 4 + 5 > (process (list 1 7 2 9)) 19 ; 1 + 7 + 2 + 9

If the integer
42
is encountered in add mode, processing of the list immediately stops, and the answer accumulated so far is returned. For example:> (process (list 1 2 3 4 5 42 6 7)) 15 > (process (list 1 2 3 42 4 5 42 6 7)) ; only leftmost 42 matters 6 > (process (list 42 1 2 3 4 5 6 7)) 0

If a negative integer i is encountered in add mode, processing enters subtract mode, in which subsequent numbers are subtracted from the accumulator until another occurrence of same negative integer i is encountered, at which point processing switches back to add mode. The values of i for entering and leaving subtract mode do not affect the accumulator. If the end of the list is encountered before the matching i is found, the result of the accumulator is returned. In subtract mode, negative integers other than i are added to the accumutor and 42 does not end the computation but is simply subtracted from the accumulator. For example:
> (process (list 1 2 3 17 4 5 17 6 7)) 10 ; 1 + 2 + 3 + 4 + 5 + 6 + 7 > (process (list 1 2 1 4 6 1 7 8 5 9 5 10 11)) 20 ; 1 + 2 + 4 + 6 + 7 + 8 + 9 + 10 + 11 > (process (list 1 2 3 1 4 5 6 1 7 8 5 9)) 7 ; 1 + 2 + 3 + 4 + (5) + 6 + 7 + 8 + 9 (sequence ends before matching 5 encounterd) > (process (list 1 2 1 4 42 5 1 6 7)) 35 ; 1 + 2 + 4 + 42 + 5 + 6 + 7

If the integer
0
is encountered in add mode, call the very next integer the skip value, and let a be the absolute value of the skip value. The next a integers after the skip value will be ignored, as if they aren’t there, and the values after these will be processed in add mode. Any occurrence of ‘42’, ‘0’, or a negative number in the next a integers will have no effect. If the list ends before processing the skip value after a0
or before processing alla
values after the skip value, the final value of the accumulator is returned. Note that0
has no special effect in subtract mode, only add mode. For example:> (process (list 4 5 0 2 6 7 8 9)) 26 ; skips 0 2 6 7, so treated like (process (list 4 5 8 9)) > (process (list 7 2 0 3 6 1 8 5 0 4 9 10)) 14 ; skips 0 3 6 1 8 and 0 4 9 10, so treated like (process (list 7 2 5)) > (process (list 7 3 0)) 10 ; skips 0, so treated like (process (list 7 3)) > (process (list 7 3 0 4 1 0 8 42 5 1 4 9)) 2 ; skips 0 4 1 0 8 42, so treated like (process (list 7 3 5 1 4 9))

(10 points) Below is the skeleton for a collection of tailrecursive functions in Racket that implements the
process
function described above. In the fileyourAccountNameps5.rkt
, flesh out the missing parts in curly braces so thatprocess
behaves correctly.(define (process ints) (addmode 0 ints)) (define (addmode ans ints) (if (null? ints) ans (let ((fst (first ints)) (rst (rest ints))) (cond [(< fst 0) (subtractmode fst ans rst)] [(= fst 0) (skipmodestart ans rst)] {Add a clause to handle 42 here} [else {Process the remaining elements in add mode}])))) (define (subtractmode end ans ints) {Subtract elements in ints until negative integer end is encountered, and then switch back to add mode. If ints runs out, return ans.} (define (skipmodestart ans ints) (if (null? ints) ans (skipmode (abs (first ints)) ans (rest ints)))) (define (skipmode numberofelementstoskip ans ints) {Skip the specified number of elements in ints one at a time, and then return to add mode. If ints runs out, return ans.}
Notes:

Your
process
function should work for very large lists. E.g.> (process (range 43 1000000)) 499999499097 > (process (range 43 4000000)) 7999997999097 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17) (range 1 43))) 42 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17 42) (range 1 43))) 903 > (process (append (range 43 1000000) (list 17) (range 0 1000000) (list 17 0 42) (range 1 50))) 581
Racket may run out of memory for very large arguments to
range
, but that’s because very large lists created byrange
take a lot of memory storage. Theprocess
function itself should require constant stack space, so should work on arbitrarily large lists. 
You should test your resulting function on all of the above test cases to verify that it works correctly. You can do this by copying the following code into your Racket program and executing
(testall)
:(define (testcase expected nums) (let ((ans (process nums))) (if (= ans expected) (display (stringappend "process passed test with answer " (number>string expected) "\n")) (display (stringappend "*** ERROR: process got" (number>string ans) "but expected" (number>string expected) "\n"))))) (define (testall) (testcase 15 '(1 2 3 4 5)) (testcase 19 '(1 7 2 9)) (testcase 15 '(1 2 3 4 5 42 6 7)) (testcase 6 '(1 2 3 42 4 5 42 6 7)) (testcase 0 '(42 1 2 3 4 5 6 7)) (testcase 10 '(1 2 3 17 4 5 17 6 7)) (testcase 20 '(1 2 1 4 6 1 7 8 5 9 5 10 11)) (testcase 7 '(1 2 3 1 4 5 6 1 7 8 5 9)) (testcase 35 '(1 2 1 4 42 5 1 6 7)) (testcase 26 '(4 5 0 2 6 7 8 9)) (testcase 14 '(7 2 0 3 6 1 8 5 0 4 9 10)) (testcase 10 '(7 3 0)) (testcase 2 '(7 3 0 4 1 0 8 42 5 1 4 9)) (testcase 499999499097 (range 43 1000000)) (testcase 7999997999097 (range 43 4000000)) (testcase 42 (append (range 43 1000000) '(17) (range 0 1000000) '(17) (range 1 43))) (testcase 903 (append (range 43 1000000) '(17) (range 0 1000000) '(17 42) (range 1 43))) (testcase 581 (append (range 43 1000000) '(17) (range 0 1000000) '(17 0 42) (range 1 50))) )


(15 points) In the file
yourAccountNameps5.py
, implement the sameprocess
function in Python, where it will take a Python list as an argument. The body ofprocess
should include a singlewhile
orfor
loop that performs the iteration performed by the functionsaddmode
,subtractmode
,skipmodestart
andskipmode
in the Racket version. Since a function like Racket’srest
would be prohibitively expensive in Python (taking Θ(n) rather than Θ(1) time for a list of length n), instead use list indexing (or afor
loop) to process the integers in the list from left to right. Your Python function should work like the Racket function, even on large integers:In [16]: process(range(43, 1000000)) Out[16]: 499999499097 In [17]: process(range(43, 4000000)) Out[17]: 7999997999097 In [18]: process(range(43, 1000000) + [17] + range(0,1000000) + [17] + range(1,43)) Out[18]: 42 In [20]: process(range(43, 1000000) + [17] + range(0,1000000) + [17, 42] + range(1,43)) Out[20]: 903 In [21]: process(range(43, 1000000) + [17] + range(0,1000000) + [17, 0, 42] + range(1,50)) Out[21]: 581
Add the following code to your Python file and use
testAll()
to test all the test cases from above.def testCase(expected, nums): ans = process(nums) if expected == ans: print "process passed test with answer", expected else: print "*** ERROR: process got", ans, "but expected", expected def testAll(): testCase(15, [1,2,3,4,5]) testCase(19, [1,7,2,9]) testCase(15, [1,2,3,4,5,42,6,7]) testCase(6, [1,2,3,42,4,5,42,6,7]) testCase(0, [42,1,2,3,4,5,6,7]) testCase(10, [1,2,3,17,4,5,17,6,7]) testCase(20, [1,2,1,4,6,1,7,8,5,9,5,10,11]) testCase(7,[1,2,3,1,4,5,6,1,7,8,5,9]) testCase(35, [1,2,1,4,42,5,1,6,7]) testCase(26, [4,5,0,2,6,7,8,9]) testCase(14, [7,2,0,3,6,1,8,5,0,4,9,10]) testCase(10, [7,3,0]) testCase(2,[7,3,0,4,1,0,8,42,5,1,4,9]) testCase(499999499097, range(43, 1000000)) testCase(7999997999097, range(43, 4000000)) testCase(42, range(43, 1000000) + [17] + range(0,1000000) + [17] + range(1,43)) testCase(903, range(43, 1000000) + [17] + range(0,1000000) + [17, 42] + range(1,43)) testCase(581, range(43, 1000000) + [17] + range(0,1000000) + [17, 0, 42] + range(1,50))
Extra Credit: More Folding (22 points)

(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 of a singlefoldr
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 the form:(define (weightedsuffixes nums) (let {[foldrresult (foldr ; put expression1 here ; put expression2 here nums)]} ; put expression3 here that transforms foldrresult ))
Note that only a single foldr
can be used, so there cannot be a foldr
in expression1, expression2, or expression3.
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 Church numeral for0
.