PS5: Iterate Until Done
 Dueish: 11:59pm Friday, Oct 27.
Because I won’t be close to having your psets through PS04 graded by Thu. Oct 26, there will not be any penalty for submitting PS05 many days later than Fri. Oct. 27. However, PS06 (due Fri. Nov. 3, covering sexpression trees and PostFix) will be posted on Fri. Oct. 27 and PS07 (due Fri. Nov. 10, covering introductory SML programmgin) will be posted on Fri. Nov. 3, so it’s important not to get too far behind on your CS251 psets!  Notes:
 This pset has a total of 115 points.
 This pset contains a solo problem worth 27 points that has several subproblems
 The problems needn’t be done in order. Feel free to jump around.
 Submission:
 In your yourFullName CS251 Fall 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 Python 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 (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 several 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.)

(4 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 ; combining function goes here. ; null value goes here. pairs))

(4 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)
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 ; combining function goes here. ; null value goes here. xs))
 The length0 prefix of

(5 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 ; combining function goes here. ; null value goes here. ints))

(4 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 ; combining function goes here. ; null value goes here. set))
Keep in mind that your function needs to produce only one of the potential solutions like those shown above.

(4 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)
Define 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) ())
Your definition should flesh out the following skeleton:
(define (suffixes xs) (foldr ; combining function goes here. ; null value goes here. xs))
 The length0 suffix of

(6 points) In this problem, you will define a function related to
suffixes
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 ; ternary combining function goes here. ; null value goes here. nums))
Notes:

Recall that the definition of foldrternop is:
(define (foldrternop ternop nullvalue xs) (if (null? xs) nullvalue (ternop (first xs) (rest xs) (foldrternop ternop nullvalue (rest xs)))))

Your definition may also use
map
.
2. Iterating with genlistapply
, foldl
and iterateapply
(23 points)
In this problem, you will define several functions with an iterative flavor in yourAccountNameps5.rkt
.

(5 points) A Collatz sequence is a seqence of nonnegative integers in which the rule for generating
the next element from a current element n > 1 is: if n is even, the next number is n/2.
 if n is odd, the next number is 3n+1.
The Collatz conjecture (still unproven) is that the Collatz sequence starting at any positive integer ends with 1 after a finite number of steps.
Define a function
collatzgenlistapply
that, given a starting number n generates a list of duples (2element lists) for the Collatz sequence starting with n in which each duple has (1) the current step number (starting with 0) (2) the element of the Collatz sequence for the current step.> (collatzgenlistapply 7) '((0 7) (1 22) (2 11) (3 34) (4 17) (5 52) (6 26) (7 13) (8 40) (9 20) (10 10) (11 5) (12 16) (13 8) (14 4) (15 2) (16 1))
Your definition should have this exact form:
(define (collatzgenlistapply num) (genlistapply ; next function goes here. ; done? function goes here. ; keepDoneValue? boolean value goes here ; seed = initial duple goes here ))
where the definition of
genlistapply
is:(define (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply next seed)))))

(6 points) Define a function
collatziterateapply
with the same inputoutput behavior ascollatzgenlistapply
, but whose definition has the exact form(define (collatzgenlistapply num) (iterateapply ; next function goes here ; done? function goes here ; finalize function goes here ; initial state goes here ))
where the definition of
iterateapply
is:(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))
Note:
 Do not use
snoc
orappend
to add a duple to the end of a list. Why? When done repeatedly, it leads to quadratic running times. Instead, cons duples to the front of a list and reverse the list at the very end.
 Do not use

(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 exact skeleton for thepolyeval
function:(define (polyeval coeffs x) (foldl ; combining function goes here. ; initial value goes here 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
iterateapply
(defined above) 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!
Your definition should have this exact form:
(define (bits num) ; Assume num is a nonnegative integer (iterateapply ; next function goes here. ; done? function goes here ; finalize function goes here ; initial state goes here ))
Notes:

Handle an input of 0 as a special case.

You should not use
snoc
,append
, or list reversal in your definition. 
As noted above, you can use
polyeval
to test your results!

3. Pair Generation (40 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 a duple = 2element list(v1 v2)
in Racket. 
(7 points) Recall the
genlistapply
function presented in lecture for generating lists:(define (genlistapply next done? keepDoneValue? seed) (if (apply done? seed) (if keepDoneValue? (list seed) null) (cons seed (genlistapply next done? keepDoneValue? (apply next seed)))))
In the file
yourAccountNameps5.rkt
, define a Racket functionpairsgenlistapply
that has the same inputoutput behavior as the Pythonpairs
function but is defined usinggenlistapply
by fleshing out the missing expressions denoted by comments in the following skeleton:(define (pairsgenlistapply n) ; Assume is n a positive integer (genlistapply ; next function goes here ; done? function goes here ; keepDoneValue? boolean goes here ; first duple goes here ))
Note:

In this definition, you should not focus on generating lists of all duples with the same difference, and then appending those lists together. That approach cannotx be implemented by fleshing out the required skeleton. Instead, you should focus on answering the following questions:

What is the first duple?

How do you generate the next duple from the current duple? (There is a regular case and a special case.)

How do you know when you’re done generating duples?



(7 points) Recall the
iterateapply
function from lecture for expressing iterations:(define (iterateapply next done? finalize state) (if (apply done? state) (apply finalize state) (iterateapply next done? finalize (apply next state))))
Define a Racket function
pairsiterateapply
that has the same inputoutput behavior as the Pythonpairs
function but is defined usingiterateapply
by fleshing out the missing expressions denoted by comments in the following skeleton:(define (pairsiterateapply n) ; Assume is n a positive integer (iterateapply ; next function goes here ; done? function goes here ; finalize function goes here ; initial state goes here ))
Notes:

In this function you should not use
snoc
,append
, orreverse
on any lists. You should only usecons
to extend a list. Why? Because repeatedsnoc
ing leads to quadratic running times. How? By constructing the desired output list in reverse, starting with the last duple and working your way back to the first duple. 
It is helpful to use iteration tables involving concrete examples to help you define your iteration. Here is the beginning of one possible iteration table for
pairsiterapply
.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 … … … While state variables
diff
andstart
may are helpful for thinking about the problem, they are not strictly necessary, since they can be deduced from the first pair inpairsSoFar
. You may choose to include or omit such state variables from your solution.


(8 points) Define a pair of Racket functions
pairsiter
andpairstail
in whichpairsiter
has the the same inputoutput behavior as the Pythonpairs
function but is implemented by calling apairstail
function that performs the iteration. Like thepairsiterateapply
function,pairstail
should add duples from the end of the list to the beginning.Your definitions should have this exact form:
(define (pairsiter num) (pairstail ... args go here ...)) (define (pairstail ... params go here ...) ; body in which any call to pairstail must be a tail call )
Notes:

The sample iteration table shown for
pairsiterapply
is helpful here, too. 
As in
pairsiterateapply
, you should not usesnoc
,append
, or perform any list reversals in yourpairsiter
definition. 
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> (append (pairstail ...) ...))
the call to
pairstail
is not a tail call (because it is a subexpression of the call toappend
).


(8 points) Define Racket function
pairsiternested
that has the the same inputoutput behavior as the Pythonpairs
function but is implemented using the following exact form:(define (pairsiternested n) (define (pairsoutertail ...) (define (pairsinnertail ...) ...) ...) (pairsoutertail ...))
where
pairsoutertail
andpairsintertail
are internally defined tailrecursive functions.Notes:

As in
pairsiterapply
andpairsiter
, you are not allowed to usesnoc
,append
, or any form of list reversal in this definition. 
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).

4. 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: Using foldr
to define weightedsuffixes
(12 points)
This problem is optional. You should only attempt it after completing all the other problems.
In Solo Problem 1 part e you were asked to define the weightedsuffixes
function in terms of foldrternop
. It is possible, but challenging, to define weightedsuffixes
in terms of a single foldr
instead. As in the definition of sortedfoldr?
Extra Credit problem from PS4, the result of weightedsuffixes
can’t be the direct result of foldr
; it’s necessary to transform the result of foldr
to get the result of weightedsuffixes
.
In this case, your definition of weightedsuffixes
should have the exact form:
(define (weightedsuffixes nums)
(map second (foldr ; combining function goes here
; null value goes here
nums)))
Other than the one foldr
required by the above skeleton, you are not allowed to any additional foldr
s in any of your expressions.