• 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 s-expression 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 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 Problems 2 through 5:
      • Write all your Racket code in a single file yourAccountName-ps5.rkt and all your Python code in a single file yourAccountName-ps5.py.
      • Drop a copy of your yourAccountName-ps5.rkt and yourAccountName-ps5.py files in your ~/cs251/drop/ps05 drop folder on cs.wellesley.edu.
      • Be sure that all function definitions in yourAccountName-ps5.rkt and yourAccountName-ps5.py 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 several 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, car, cdr, list, append, first, second, third, and rest. (You may also use any Racket math or logic operators, such as +, max, etc.)

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

  2. (4 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)

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

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

  4. (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 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 ; 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.

  5. (4 points) 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)

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

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

    Notes:

    • Recall that the definition of foldr-ternop is:

      (define (foldr-ternop ternop null-value xs)
  (if (null? xs)
      null-value
      (ternop (first xs)
              (rest xs)
              (foldr-ternop ternop null-value (rest xs)))))

    • Your definition may also use map.

2. Iterating with genlist-apply, foldl and iterate-apply (23 points)

In this problem, you will define several functions with an iterative flavor in yourAccountName-ps5.rkt.

  1. (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 collatz-genlist-apply that, given a starting number n generates a list of duples (2-element 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.

    > (collatz-genlist-apply 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 (collatz-genlist-apply num)
  (genlist-apply ; next function goes here.
                 ; done? function goes here.
                 ; keepDoneValue? boolean value goes here
                 ; seed = initial duple goes here
                 ))

    where the definition of genlist-apply is:

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

  2. (6 points) Define a function collatz-iterate-apply with the same input-output behavior as collatz-genlist-apply, but whose definition has the exact form

    (define (collatz-genlist-apply num)
  (iterate-apply ; next function goes here
                 ; done? function goes here 
                 ; finalize function goes here
                 ; initial state goes here
                 ))

    where the definition of iterate-apply is:

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

    Note:

    • Do not use snoc or append 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.

  3. (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 coefficients. Show this by completing the following exact skeleton for the poly-eval function:

    (define (poly-eval coeffs x)
  (foldl ; combining function goes here.
         ; initial value goes here
         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 

;; Hey, can use poly-eval to convert a sequence of decimal digits to decimal ... 
> (poly-eval (list 1 5 4 7 2) 10)
15472

;; .. or to convert binary digits 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 digits to decimal (writing 10 for A, 11 for B, etc): 
> (poly-eval (list 6 1) 16)
97

> (poly-eval (list 15 11) 16) ; FB in hex
251

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

;; Can 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)

  4. (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 iterate-apply (defined above) 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!

    Your definition should have this exact form:

    (define (bits num) ; Assume num is a nonnegative integer
  (iterate-apply ; 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 poly-eval 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+1-diff):
            result.append((start, start+diff))
    return result

  1. (4 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 (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 the pairs 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),...(n-1,n),
     (0, 2), … (n-2, 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?

  2. (6 points) In the file yourAccountName-ps5.rkt, 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 a duple = 2-element list (v1 v2) in Racket.

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

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

    In the file yourAccountName-ps5.rkt, define a Racket function pairs-genlist-apply that has the same input-output behavior as the Python pairs function but is defined using genlist-apply by fleshing out the missing expressions denoted by comments in the following skeleton:

    (define (pairs-genlist-apply n) ; Assume is n a positive integer
  (genlist-apply ; 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?

  4. (7 points) Recall the iterate-apply function from lecture for expressing iterations:

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

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

    (define (pairs-iterate-apply n) ; Assume is n a positive integer
  (iterate-apply ; 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, or reverse on any lists. You should only use cons to extend a list. Why? Because repeated snocing 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 pairs-iter-apply.

      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 and start may are helpful for thinking about the problem, they are not strictly necessary, since they can be deduced from the first pair in pairsSoFar. You may choose to include or omit such state variables from your solution.

  5. (8 points) Define a pair of Racket functions pairs-iter and pairs-tail in which pairs-iter has the the same input-output behavior as the Python pairs function but is implemented by calling a pairs-tail function that performs the iteration. Like the pairs-iterate-apply function, pairs-tail should add duples from the end of the list to the beginning.

    Your definitions should have this exact form:

    (define (pairs-iter num)
  (pairs-tail ... args go here ...))

(define (pairs-tail ... params go here ...)
  ; body in which any call to pairs-tail must be a tail call
  )

    Notes:

    • The sample iteration table shown for pairs-iter-apply is helpful here, too.

    • As in pairs-iterate-apply, you should not use snoc, append, or perform any list reversals in your pairs-iter 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 (pairs-tail ...) ...))

      the call to pairs-tail is not a tail call (because it is a subexpression of the call to append).

  6. (8 points) Define Racket function pairs-iter-nested that has the the same input-output behavior as the Python pairs function but is implemented using the following exact form:

    (define (pairs-iter-nested n)
  (define (pairs-outer-tail ...)
    (define (pairs-inner-tail ...)
      ...)
     ...)
  (pairs-outer-tail ...))

    where pairs-outer-tail and pairs-inter-tail are internally defined tail-recursive functions.

    Notes:

    • As in pairs-iter-apply and pairs-iter, you are not allowed to use snoc, 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> 
    (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).

4. List Processing with Tail Recursion and Loops (25 points)

One or more tail-recursive 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 in ints. 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 a 0 or before processing all a values after the skip value, the final value of the accumulator is returned. Note that 0 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))

  1. (10 points) Below is the skeleton for a collection of tail-recursive functions in Racket that implements the process function described above. In the file yourAccountName-ps5.rkt, flesh out the missing parts in curly braces so that process behaves correctly.

    (define (process ints)
  (add-mode 0 ints))

(define (add-mode ans ints)
  (if (null? ints)
      ans
      (let ((fst (first ints))
            (rst (rest ints)))
        (cond [(< fst 0) (subtract-mode fst ans rst)]
              [(= fst 0) (skip-mode-start ans rst)]
              {Add a clause to handle 42 here}
              [else {Process the remaining elements in add mode}]))))

 (define (subtract-mode 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 (skip-mode-start ans ints)
    (if (null? ints)
        ans
        (skip-mode (abs (first ints)) ans (rest ints))))

 (define (skip-mode number-of-elements-to-skip 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 by range take a lot of memory storage. The process 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 (test-all):

      (define (test-case expected nums)
  (let ((ans (process nums)))
    (if (= ans expected)
        (display (string-append "process passed test with answer " (number->string expected) "\n"))
        (display (string-append "*** ERROR: process got"
                                (number->string ans)
                                "but expected"
                                (number->string expected)
                                "\n")))))

(define (test-all)
    (test-case 15 '(1 2 3 4 5))
    (test-case 19 '(1 7 2 9))
    (test-case 15 '(1 2 3 4 5 42 6 7))
    (test-case 6 '(1 2 3 42 4 5 42 6 7))
    (test-case 0 '(42 1 2 3 4 5 6 7))
    (test-case 10 '(1 2 3 -17 4 5 -17 6 7))
    (test-case 20 '(1 2 -1 4 6 -1 7 8 -5 9 -5 10 11))
    (test-case 7 '(1 2 3 -1 4 -5 6 -1 7 8 -5 9))
    (test-case -35 '(1 2 -1 4 42 5 -1 6 7))
    (test-case 26 '(4 5 0 2 6 7 8 9))
    (test-case 14 '(7 2 0 3 6 1 8 5 0 4 9 10))
    (test-case 10 '(7 3 0))
    (test-case 2 '(7 3 0 4 -1 0 8 42 5 -1 4 9))
    (test-case 499999499097 (range 43  1000000))
    (test-case 7999997999097 (range 43  4000000))
    (test-case -42 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17) (range 1 43)))
    (test-case -903 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17  42) (range 1 43)))
    (test-case -581 (append (range 43  1000000) '(-17) (range 0 1000000) '(-17  0  42) (range 1 50)))
  )

  2. (15 points) In the file yourAccountName-ps5.py, implement the same process function in Python, where it will take a Python list as an argument. The body of process should include a single while or for loop that performs the iteration performed by the functions add-mode, subtract-mode, skip-mode-start and skip-mode in the Racket version. Since a function like Racket’s rest would be prohibitively expensive in Python (taking Θ(n) rather than Θ(1) time for a list of length n), instead use list indexing (or a for 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 weighted-suffixes (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 weighted-suffixes function in terms of foldr-ternop. It is possible, but challenging, to define weighted-suffixes in terms of a single foldr instead. As in the definition of sorted-foldr? Extra Credit problem from PS4, the result of weighted-suffixes can’t be the direct result of foldr; it’s necessary to transform the result of foldr to get the result of weighted-suffixes.

In this case, your definition of weighted-suffixes should have the exact form:

(define (weighted-suffixes 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 foldrs in any of your expressions.