• Due: Friday, Oct. 19 (with grace period through the end of Sun. Oct. 21)
  • Notes:
    • This pset has a total of 100 points.
    • This pset contains a solo problem worth 35 points that has several subproblems
    • By Fri. Oct. 12, you will have seen in lecture almost all material that is needed for this pset.
    • The problems needn’t be done in order. Feel free to jump around.

  • Times from Spring ‘18 (in hours, n=29)**

    Times Problem 1 Problem 2 Problem 3 Total
    average time (hours) 2.0 2.1 4.2 8.0
    median time (hours) 2.0 2.0 4.0 8.0
    25% took more than 2.0 2.5 5.0 9.3
    10% took more than 3.6 3.0 6.0 11.0
  • Submission:
    • In your yourFullName CS251 Fall 2018 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 for Extra Credit Problem 2, 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 and 3 (and any extra credit problems you submit):
      • Write all your Racket code in a single file yourAccountName-ps5.rkt.
      • Drop a copy of your yourAccountName-ps5.rkt files in your ~/cs251/drop/ps05 drop folder on cs.wellesley.edu.
      • If you do Extra Credit Problem 2b, write your Python code in a single file yourAccountName-ps5.py and also drop this 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 (35 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 eight 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))

  • You may also use map directly in any of these problems.

  • Unless otherwise stated in a subproblem, 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. You may not use any form of list reversal in any of your solutions.

  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 must 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 must 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-squaresEvens 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 definition must 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 must flesh out the following skeleton:

    (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 must flesh out the following skeleton:

    (define (suffixes xs)
  (foldr ; combining function goes here.
         ; null value goes here. 
         xs))

  6. (5 points) In this part, 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) ())

    Use foldr-ternop to define weighted-suffixes. Your definition must 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)))))

    • Recall that you may not use any helper functions. But you may use map.

  7. (4 points) In this part, you will give an alternative definition of the keepBiggerThanNext function from Slide 23 in the lecture on Higher Order List Functions. Recall that keepBiggerThanNext takes a list of numbers and returns a new list that keeps all numbers (in their same relative order in the input list) that are bigger than the next number in the input list. It never keeps the last number.

     > (keepBiggerThanNext '(9 5 8 4 7 3 6 1 2))
 '(9 8 7 6)

 > (keepBiggerThanNext  '(6 0 4 7 1 5 3 9 8 2))
 '(6 7 5 9 8)

 > (keepBiggerThanNext (range 0 100))
 '()

 > (keepBiggerThanNext (append (range 0 100) (range 80 90)))
 '(99)

 > (keepBiggerThanNext '(8))
 '()

 > (keepBiggerThanNext '())
 '()

    Flesh out the following definition of a function skeleton that uses foldr to define keepBiggerThanNext. You must use exactly this skeleton:

    (define (keepBiggerThanNext nums)
  (foldr ; combining function goes here
         ; null value goes here
         (if (null? nums) '() (zip nums (rest nums)))))

    Notes:

    • The skeleton of this definition is different than the definition of keepBiggerThanNext using foldr from Slide 21 in the lecture on Higher Order List Functions. The definition in Slide 21 applies foldr directly to nums, in which case it is necessary for it to return a duple (two-element list) of (1) the next number and (2) the resulting list from below. In contrast, in this part you are asked to write a definition that applies foldr to a list derived from nums and directly returns the desired list.

    • Recall that the definition of zip is:

      (define (zip xs ys)
  (if (or (null? xs) (null? ys))
      '()
      (cons (cons (first xs) (first ys))
            (zip (rest xs) (rest ys)))))

  8. (5 points) Using foldr-ternop, define a function keepBiggerThanSomeFollowing that takes a list of numbers and returns a new list that keeps all numbers (in their same relative order in the input list) that are bigger than some number that follows them in the input list. It never keeps the last number.

     > (keepBiggerThanSomeFollowing  '(6 0 4 7 1 5 3 9 8 2))
 '(6 4 7 5 3 9 8)

 > (keepBiggerThanSomeFollowing '(9 5 8 4 7 3 6 1 2))
 '(9 5 8 4 7 3 6)

 > (keepBiggerThanSomeFollowing (range 0 100))
 '()

 > (keepBiggerThanSomeFollowing (append (range 0 100) (range 80 90)))
 '(81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99)

 > (keepBiggerThanSomeFollowing '(8))
 '()

 > (keepBiggerThanSomeFollowing '())
 '()

    Flesh out the following definition of a function skeleton that uses foldr-ternop to define keepBiggerThanSomeFollowing. You must use exactly this skeleton:

    (define (keepBiggerThanSomeFollowing nums)
  (foldr-ternop ; ternary combining function goes here.
                ; null value goes here. 
                nums))

    Note: You may use the following exists? function from PS4:

    (define (exists? pred xs)
  (and (not (null? xs))
       (or (pred (first xs))
           (exists? pred (rest xs)))))

2. Iterating with genlist-apply, foldl and iterate-apply (25 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)))))

    Note: Your seed in this problem should be the initial step/number duple, and your next function should take the current duple to the next duple.

  2. (7 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-iterate-apply num)
  (iterate-apply ; can used iterate instead if you prefer; see note below
      ; 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))))

    Notes:

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

    • In order to leverage the naming capabilities of iterate-apply, it is strongly recommend that your state in this problem be represented by a list with three variables:

      • The current step number

      • The current number

      • A reversed list of all previously generated duples, not including the current step number and number.

    • If you instead want only a single state variable that is the reversed list of all duples so far (including the current step number and number), then iterate-apply actually gets in the way and you should just use iterate instead.

  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. (8 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 = two-element list (v1 v2) in Racket.

    Notes: The idea here is to re-express aspects of the Python nested loop in the functional list-processing style. In particular:

    • For a given difference, how can you generate a list of all the starting values of duples with that difference? How would you express the computation “collect all the duples that have this difference”?

    • Suppose you start with a list of differences. What could you do with every difference to generate the list of duples with that difference? How would you express the computation “collect all the lists of lists of duples for this input list of differences”?

    • Given a list of list of duples, how can you transform this to a list of all the duples? You can’t use a helper function, but you can use foldr.

  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 cannot 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-inner-tail are internally defined tail-recursive functions.

    Notes:

    • The idea here is to re-express the key aspects of the original Python nested loops via tail recursion. In particular:

      • A call to pairs-outer-tail should mean “generate the duples with this difference, add them to list of duples generated so far, and then do the same with the remaining differences.”

      • A call to pairs-inner-tail should mean “generate the duple with this start value and the current difference, add it to list of duples generated so far, then continue with the rest of the start values for this difference, and then do the same with the remaining differences.”

      • In Python, a loop automatically continues unless you exit it early with break or return. In contrast, when using tail recursion to express a loop in Racket, the iteration continues only if you explicitly call the corresponding tail recursive function; otherwise, the loop terminates.

    • 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: As in Problem 3e, just naming a function to end in -tail does not make it tail recursive! In order to be tail recursive, all calls of your tail recursive functions must not be subexpressions of other function calls. E.g. in the code

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

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

Extra Credit Problem 1: Using foldr to define keepBiggerThanSomeFollowing (8 points)

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

In Solo Problem 1 part g you were asked to define the keepBiggerThanSomeFollowing function in terms of foldr-ternop. It is possible, but challenging, to define keepBiggerThanSomeFollowing in terms of a single foldr instead. As in the definition of sorted-foldr? Extra Credit problem from PS4, the result of keepBiggerThanSomeFollowing can’t be the direct result of foldr; it’s necessary to transform the result of foldr to get the result of keepBiggerThanSomeFollowing.

In this case, your definition of keepBiggerThanSomeFollowing should have the exact form:

(define (keepBiggerThanSomeFollowing nums)
  (second 
    (foldr ; combining function goes here
           ; null value goes here
           nums)))

Notes:

  • Other than the one foldr required by the above skeleton, you are not allowed to any additional foldrs in any of your expressions.

  • Other than the single reference to nums in the above skeleton, you are not allowed to reference nums again.

  • Your solution must be a linear-time algorithm to earn extra credit points. In particular, calling exists (which is itself linear-time) on every suffix of nums is a quadratic-time algorithm.

Extra Credit Problem 2: List Processing with Tail Recursion and Loops (20 points)

Note: In previous semesters, this was a required problem, but this semester it is an optional extra credit problem. In Fall ‘17, this problem had an average time of 1.43 hours a median time of 1.38 hours, and a max time of 2.5 hours.

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