• Due: 11:59pm Wednesday, March 15.
  • Notes:
    • This pset contains a solo problem worth 23 points.
    • The problems needn’t be done in order. Feel free to jump around.
  • Submission:
    • In your yourFullName CS251 Spring 2017 Folder, create a Google Doc named yourFullName CS251 PS5.
    • At the top of your yourFullName CS251 PS5 doc, include your name, problem set number, date of submission, and an approximation of how long each problem part took.
    • For all parts of all problems, include all answers (including Racket and Pytbon code) in your PS5 google doc. Format Racket and Python code using a 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 (23 points)

This is a solo problem. This means you must complete it entirely on your own without help from any other person and without consulting resources other than course materials or online documentation. You may ask Lyn for clarification, but not for help.

In this problem you will define four functions via folding operators. Some notes:

  • Define all of your functions in a new file named 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. (5 points) Using foldr, define a function (unzip pairs) that takes a list of pairs (cons cells) and returns a list of two lists that, if zipped together 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 ; put expression 1 here
         ; put expression 2 here
         pairs))

  2. (5 points) Suppose that we represent a set in Racket as a list without duplicates. Using foldr, define a function (subsets set) that returns a list of all subsets of a given set. The subsets within this can be in any order, but the order of elements within each set should have the same relative order as 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 ; put expression 1 here
         ; put expression 2 here
         set))

    Keep in mind that your function needs to produce only one of the potential solutions like those shown above.

  3. (6 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 ; put expression 1 here
         ; put expression 2 here
         ints))

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

    Based on this definition, imagine a function suffixes that takes a list as its single argument and returns a list of all of its suffixes ordered from longest to shortest. For example:

     > (suffixes '(5 8 4))
 '((5 8 4) (8 4) (4) ())  
 > (suffixes '(2 5 8 4))
 '((2 5 8 4) (5 8 4) (8 4) (4) ())
 > (suffixes '(7 2 5 8 4))
 '((7 2 5 8 4) (2 5 8 4) (5 8 4) (8 4) (4) ())
 > (suffixes (range 1 11))
 '((1 2 3 4 5 6 7 8 9 10)
   (2 3 4 5 6 7 8 9 10)
   (3 4 5 6 7 8 9 10)
   (4 5 6 7 8 9 10)
   (5 6 7 8 9 10)
   (6 7 8 9 10)
   (7 8 9 10)
   (8 9 10)
   (9 10)
   (10)
   ())

    In this problem, you are not asked to define suffixes, but are instead asked to define a related function 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 ; put expression 1 here
                ; put expression 2 here
                nums))

    Your definition may also use map.

2. n-fold Composition (10 points)

In mathematics, the composition of unary functions f and g, writen f ◦g is the unary function such that (f ◦g)(x) = f(g(x)).

We can define a composition function o in Racket as follows:

(define (o f g) 
  (λ (x) (f (g x))))

Here are some examples of composition:

(define (inc y) (+ y 1))
(define (dbl z) (* z 2))

> ((o inc dbl) 10)
21

> ((o dbl inc) 10)
22

> ((o inc inc) 10)
12

> ((o dbl dbl) 10)
40

The identity function id is the identity of the composition operator:

(define (id x) x)

> ((o inc id) 10)
11

> ((o id inc) 10)
11

The n-fold composition of a function f, written f n is f composed with itself n times. Thus, f 2 = f ◦ f, f 3 = f ◦ f ◦ f, and so on. Note that f 1 = f, and f 0 = the identity function id.

In this problem, you will define in a file yourAccountName-ps5.rkt a Racket function (n-fold n f) that takes a nonnegative integer n and a unary function f and returns the n-fold composition of f. In your definition, you may not use explicit recursion. There are many different ways to define n-fold without recursion! You are allowed to use higher-order functions we’ve studied (e.g., map, foldr, foldl, iterate, iterate-apply, genlist, genlist-apply) as well as standard Racket functions like range.

Here are some examples of using n-fold:

> ((n-fold 2 inc) 0)
2

> ((n-fold 17 inc) 100)
117

> ((n-fold 3 dbl) 1)
8

> ((n-fold 4 (curry + 3)) 0)
12

> ((n-fold 4 (curry * 3)) 1)
81

> ((n-fold 2 (o inc dbl)) 5)
23

> ((n-fold 2 (o dbl inc)) 5)
26

> ((n-fold 17 id) 42) 
42

3. Iterating with foldl and iterate (12 points)

In this problem, you should define the specified functions poly-eval and bits in yourAccountName-ps5.rkt.

  1. (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 skeleton for the poly-eval function:

    (define (poly-eval coeffs x)
  (foldl {combining function} 
         {initial value}
         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)

  2. (7 points) The iterative process of converting a decimal number to a sequence of binary bits is illustrated by the following iteration table for the conversion of the decimal number 38 to binary bits:

    num bits Notes
    38 ()  
    19 (0) 38 mod 2 = 0
    9 (1 0) 19 mod 2 = 1
    4 (1 1 0) 9 mod 2 = 1
    2 (0 1 1 0) 4 mod 2 = 0
    1 (0 0 1 1 0) 2 mod 2 = 0
    0 (1 0 0 1 1 0) 1 mod 2 = 1

    Based on this idea, use either iterate or iterate-apply from lecture 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!

    Notes:

    • Here are the definitions of iterate and iterate-apply

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

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

    • Handle an input of 0 as a special case.

    • As noted above, you can use poly-eval to test your results!

4. Pair Generation (30 points)

Consider the following Python pairs function, whose single argument n you may asssume is a positive integer:

def pairs(n): # Assume n is a positive integer
    result = []
    for diff in range (1, n+1):
        for start in range(0, n+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 the dotted pair cons-cell (v1 . v2) in Racket.

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

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

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

    (define (pairs-genlist n) ; Assume is n a positive integer
  (genlist {next function goes here}
           {done? function goes here}
           {keepDoneValue? boolean goes here}
           {seed goes here}))

  4. (12 points) In the file yourAccountName-ps5.rkt, define a Racket function pairs-iter that has the same input-output behavior as the Python pairs function but is expressed iteratively in terms of one or more tail-recursive functions. Unlike the Python pairs function and Racket pairs-genlist function, which add pairs from the front of the list to the end, your pairs-iter implementation should add pairs from the end of the list to the beginning.

    Notes:

    • You should not use iterate or iterate-apply in this problem! Instead, you should define one or more tail-recursive functions specialized for this particular problem.

    • You should not perform any list reversals in your pairs-iter definition.

    • The pairs-iter function need not itself be recursive; it can call one or more tail-recursive functions.

    • The Python nested loop solution builds the list of pairs from the first pair forward because in Python
      it is most natural to add elements to the end of a list accumulator via .append. However, in Racket, it
      is most natural to add elements to the beginning of a list via cons. Therefore, in this problem, you should
      start with an empty list and add elements from the last pair backwards. E.g., for (pairs-iter 5), you should
      first add the pair '(0 . 5) to the empty list '(), then add '(1 . 5) to the list '((0 . 5)), then add
      '(0 . 4) to the list '((1 . 5) (0 . 5)), and so on.

    • It is helpful to use iteration tables involving concrete examples to help you define your tail recursive function(s). Here is the beginning of an iteration table that is inspired by a nested loop solution for (pairs-iter 5):

      n diff start pairsSoFar
      5 5 0 ()
      5 4 1 ((0 . 5))
      5 4 0 ((1 . 5) (0 . 5))
      5 3 2 ((0 . 4) (1 . 5) (0 . 5))
      5 3 1 ((2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 3 0 ((1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 2 3 ((0 . 3) (1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 2 2 ((3 . 5) (0 . 3) (1 . 4) (2 . 5) (0 . 4) (1 . 5) (0 . 5))
      5 … … …

      One way to go from the above iteration table to a tail-recursive function is to have a single tail recursive function with arguments that have the names of the columns. This can be done by defining two top-level functions pairs-iter and pairs-tail

      (define (pairs-iter n)
  (pairs-tail ...))

(define (pairs-tail ...)
  ...)

      or by defining pairs-tail as a local function within pairs-iter

      (define (pairs-iter n)
  (define (pairs-tail ...)
    ...)
  (pairs-tail ...))

      Another way to go from the above iteration table is to develop two mutually recursive tail recursive functions that each use some of the names of the columns as arguments. E.g., an outer tail recursive function would be responsible for decrementing the diff, while an inner tail recursive function would be responsible for decrementing the start. Such functions could all be defined at top-level

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

(define (pairs-outer-tail ...)
  ...)

(define (pairs-inner-tail ...)
  ...)

      or could be defined in a nested way

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

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

5. 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: More Folding (22 points)

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

    Using foldr and map-cons, 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 ; put expression 1 here
         ; put expression 2 here
         xs))

  2. (5 points) The suffixes function is defined in Solo Problem 1 part d. Here, use foldr to define suffixes. Your definition should flesh out the following skeleton:

    (define (suffixes xs)
  (foldr ; put expression 1 here
         ; put expression 2 here
         xs))

  3. (12 points) In Solo Problem 1 part d 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 needn’t be the direct result of foldr; it’s OK to transform the result of foldr to get the result of weighted-suffixes. That is, your definition of weighted-suffixes should have the form:

    (define (weighted-suffixes nums)
  (let {[foldr-result (foldr ; put expression1 here 
                             ; put expression2 here
                             nums)]}
    ; put expression3 here that transforms foldr-result 
    ))

Note that only a single foldr can be used, so there cannot be a foldr in expression1, expression2, or expression3.

Extra Credit: Church Numerals (25 points)

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

The curried n-fold operator cn-fold, defined below has some interesting properties.

(define cn-fold (curry2 n-fold))
(define twice (cn-fold 2))
(define thrice (cn-fold 3))

> ((twice inc) 0)
2

> ((thrice inc) 0)
3

> ((twice dbl) 1)
4

> ((thrice dbl) 1)
8

In Church’s λ-calculus, it turns out that a function equivalent to (cn-fold n) can be used to represent the nonnegative integer n. As you can see above, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.

  1. (10 points) In the following questions suppose that a and b are nonnegative integers and f is a unary function. Justify your answer to each question.

    (1) (o (n-fold a f) (n-fold b f)) is equivalent to (n-fold p f) for what number p?

    (2) (o (cn-fold a) (cn-fold b)) is equivalent to (cn-fold q) for what number q?

    (3) ((cn-fold a) (cn-fold b)) is equivalent to (cn-fold r) for what number r?

  2. (5 points) Define a function inc that takes as its argument a Church numeral for n and returns the Church numeral for n+1. That is, for any n, (inc (cn-fold n)) should return a Church numeral equivalent to (cn-fold (+ n 1)).

  3. (10 points) Define a function dec that takes as its argument a Church numeral for n and returns the Church numeral for n-1; in the special case where n is 0, it should return the Church numeral for 0.