CS 251: PS4: Iterate Until Done

Clarifications shown in magenta.
Dueish: Fri Mar 12
Notes:
- This pset has a total of 110 points.
- As with all regular psets, you can work on this problem in a two-person team or as an individual, but partnering is strongly recommended. You need to work with a different partner than you did in your previous two partnerships. Use this Pset Partner Doc to find a partner and record your partnership.
- The problems needn’t be done in order. Feel free to jump around.
- Problems 1 through 3 depend on the iteration material covered in Lecs 14 and 15.
- Most, if not all, of the material you will need to define the SML functions in Problem 4 will be covered in Lecs 16 and 27 (including associated asynchronous videos). In Problem 4 you are asked to translate Racket functions you already understand into SML, so the focus is on SML syntax and type-checking, not on problem solving using SML. In later psets, you will leverage SML’s features for new kinds of programming problems.

Times from some previous semesters (in which all students worked individually; partnering may reduce times)

Times	Problem 1	Problem 2	Problem 3	Problem 4	Total
average time (hours)	2.1	0.6	4.2	3.5	10.4
median time (hours)	2.0	0.5	4.0	3.5	10.0
25% took more than	2.5	0.7	5.0	4.0	12.2
10% took more than	3.0	1.0	6.0	5.4	15.4

How to Start PS4

Follow the instructions in the GDoc CS251-S21-T3 Pset Submission Instructions for creating your PS4 Google Doc. Put all written answers and a copy of all code into this PS4 GDoc. If you are working with a partner, only one of you needs to create this document, but you should link it from both of your List Docs. <
Submission:
- For all parts of all problems, include all answers (code, English explanations, etc.) in your PS4 google doc. Please format your Racket and SML code using a fixed-width font, like Consolas or Courier New, and format it so that it’s easy to read. You can use a small font size if that helps.
- For Problems 1, 2 and 3 (Racket functions):
  - Write all your Racket code in a single file yourAccountName-ps4-iter.rkt.
  - Include all your new function definitions from yourAccountName-ps4-iter.rkt in your PS4 GDoc (so graders can comment on them)
  - Drop a copy of your yourAccountName-ps4-iter.rkt files in your ~/cs251/drop/ps04 drop folder on cs.wellesley.edu.
- For Problems 4 (SML functions):
  - Write all your SML code in a single file ~/cs251/sml/ps4/yourAccountName-ps4-holo.sml on your csenv-s20 appliance.
  - Include all your new function definitions from yourAccountName-ps4-holo.sml in your PS4 GDoc (so graders can comment on them)
  - Drop a copy of your ~/cs251/sml/ps4/yourAccountName-ps4-holo.sml file from your csenv-s20 appliance in your ~/cs251/drop/ps04 drop folder on cs.wellesley.edu by executing the following in a terminal window on your csenv-s20 appliance: (replacing all occurrences of gdome by your cs account username):
```
scp ~/cs251/sml/ps4/gdome-ps4-holo.sml gdome@cs.wellesley.edu:/students/gdome/cs251/drop/ps04
```
- If you are working with a partner, only one of you should drop the .rkt and .sml files. However, both partners should do this: At the top of your PS4 doc and in the PS4 entry in your List Doc, indicate the account name of the drop folder in which the .rkt and .sml file have been dropped.
- If you do any Extra Credit problems, see the submission details in each problem.

1. Iterating with `genlist-apply`, `foldl` and `iterate-apply` (24 points)

Begin this problem by creating a Racket file yourAccountName-ps4-iter.rkt beginning with the following definitions:

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

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

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

You will use this file for all the Racket functions you define in Problems 1, 2, and 3.

(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; indeed, a very famous open problem) 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 must 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 must be the initial step/number duple, and your next function must take the current duple to the next duple.
(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 (using Racket’s efficient built-in reverse function).
- 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.

(5 points) A naive approach to evaluating a polynomial like x⁴ + 5x³ + 4x² + 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 ((curry poly-eval) (list 1 5 4 7 2)) (range 11))
'(2 19 88 275 670 1387 2564 4363 6970 10595 15472)

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

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

Based on this idea, use 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 38)
'(1 0 0 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 must 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 must not use snoc, append, or list reversal in your definition.
As noted above, you can use poly-eval to test your results!

2. n-fold Composition (10 points)

As explained in Lec 13 Higher-order List functions (Part 3), 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ⁿ is f composed with itself n times. Thus, f² = f ◦ f, f³ = f ◦ f ◦ f, and so on. Note that f¹ = f, and f⁰ = the identity function id.

In this problem, you will define in your existing file named yourAccountName-ps4-iter.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. 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

(4 points) The pairs function generates a list of pairs related to the input n, in a very particular order. In this part you will rigorously specify the output list of pairs in terms of n without describing the Python code or the algorithm that generates the pairs.

i. (2 points) First, precisely describe what pairs (a, b) can appear in the output list of the pairs function. Exactly what kind of mathematical entitities are a and b? How are a and b related to each other and to n? Are there any other constraints on their values?

ii. (2 points) Suppose that (a1, b1) and (a2, b2) are two pairs in the output list of the pairs function. Specify precisely the conditions under which (a1, b1) can appear at some position in the list before (a2, b2).
(6 points) In the file yourAccountName-ps4-iter.rkt, define a Racket function pairs-hof that has the same input-output behavior as the Python pairs function but is expressed in the list transformation style (see Lec 13, part 3) in terms of nestings of the higher order list functions foldr and map in conjunction with standard list operators like append and range. (hof means higher-order function).

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:
- In pairs-hof, the only higher-order functions you should use are foldr and map. (curry is also allowable, but is not required.) You should not use filter, foldl, genlist, genlist-apply, iterate, or iterate-apply.
- You should not use any helper functions or recursion in your solution.
- You should not use reverse or any other form of list reversal in your solution.
- 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.
(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-ps4-iter.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
      '(0 1) ; 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:
  - How do you generate the next duple from the current duple? (There is a regular case and a special case.)
  - How do you know when you’re done generating duples?

(7 points) Recall the 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
      (list n ; initial diff
            0 ; initial start
            '() ; initial pairs-so-far
            )
      ))

Notes:

In this function definition, you must 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.
In this function definition, you must also not use foldr or any other higher-order list operations.

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.

(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 must 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 must not use snoc, append, or perform any list reversals in your pairs-iter definition, and you must not use foldr or any higher-order list functions.
- 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).
(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:
  - Calling pairs-outer-tail corresponds to starting the next iteration of the outer loop on the next diff value. So a call to pairs-outer-tail should mean “generate the duples with this diff value, add them to list of duples generated so far, and then do the same with the remaining diff values.”
  - Calling pairs-inter-tail corresponds to starting the next iteration of the inner loop on the next start value. A call to pairs-inner-tail should mean “generate the duple with this start value and the current diff value, add it to list of duples generated so far, then continue with the rest of the start values for this diff value, and then do the same with the remaining diff values.”
  - Each of these functions should take only the parameters that are changing for the corresponding loop. E.g.,
    - pairs-outer-tail should not take n as a parameter, since it doesn't change in the outer loop
    - pairs-inner-loop should not take n nor diff as parameters, since these don't change in the inner loop.
  - If the outer loop is done executing, pairs-outer-tail should return the final list of pairs. Otherwise it should start the inner loop by calling pairs-inner-tail with appropriate arguments.
  - If the inner inner loop is done executing, it should start the next iteration of the outer loop by calling pairs-outer-tail with appropriate arguments. So pairs-outer-tail and pairs-inner-tail should be mutually recursive.
  - 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, and you must not use foldr or any higher-order list functions.
- 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).

4. Higher-order List Operators in SML (36 points)

In this problem, you will revisit several of the higher-order list operators we have studied in Racket in the context of SML. Since you are already familiar with these operators, your focus in this problem is on SML syntax and type-checking, rather than on the operators themselves.

range, digitsToDecimal, cartesianProduct, partition (12 points). Translate the following Racket functions range, digits->decimal, cartesian-product, and partition into corresponding SML functions named range, digitsToDecimal, cartesianProduct, and partition functions:
```
(define (range lo hi)
  (if (<= hi lo)
      null
      (cons lo (range (+ 1 lo) hi))))

(define (digits->decimal digits)
  (foldl (λ (digit sum) (+ (* 10 sum) digit))
         0
         digits))

(define (cartesian-product xs ys)
  (foldr (λ (x subres) (append (map (λ (y) (cons x y)) ys)  subres))
         null 
         xs))  

(define (partition pred xs)
  (foldr (λ (x two-lists) 
           (if (pred x) 
               (list (cons x (first two-lists)) (second two-lists))
               (list (first two-lists) (cons x (second two-lists)))))
         (list '() '())
         xs))
```
For example:
```
val range = fn : int -> int -> int list
val digitsToDecimal = fn : int list -> int
val cartesianProduct = fn : 'a list -> 'b list -> ('a * 'b) list
val partition = fn : ('a -> bool) -> 'a list -> 'a list * 'a list

- range 0 10;
val it = [0,1,2,3,4,5,6,7,8,9] : int list

- range 3 8;
val it = [3,4,5,6,7] : int list

- range 5 5;
val it = [] : int list

- range 1 100;
val it = [1,2,3,4,5,6,7,8,9,10,11,12,...] : int list

- Control.Print.printLength := 100;

- val it =
  [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,
   29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,
   54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,
   79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99] : int list

- digitsToDecimal [2, 5, 1]
val it = 251 : int

- digitsToDecimal [1, 7, 2, 9]
val it = 1729 : int

- digitsToDecimal (range 0 10);
val it = 123456789 : int

- digitsToDecimal  []
val it = 0 : int

- cartesianProduct [1,2,3,4] ["a", "b", "c"];
val it =
  [(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c"),
   (4,"a"),(4,"b"),(4,"c")] : (int * string) list

- cartesianProduct ["a", "b", "c"] [1,2,3,4];
val it =
  [("a",1),("a",2),("a",3),("a",4),("b",1),("b",2),("b",3),("b",4),("c",1),
   ("c",2),("c",3),("c",4)] : (string * int) list

- partition (fn x => x mod 2 = 0) [4, 2, 7, 8, 5, 1, 9, 3, 6];
val it = ([4,2,8,6],[7,5,1,9,3]) : int list * int list

- partition (fn x => x < 4) [4, 2, 7, 8, 5, 1, 9, 3, 6];
val it = ([2,1,3],[4,7,8,5,9,6]) : int list * int list

- partition (fn x => x > 0) [4, 2, 7, 8, 5, 1, 9, 3, 6];
val it = ([4,2,7,8,5,1,9,3,6],[]) : int list * int list
```
Notes: (Read ALL of these notes before proceeding with Problem 3a!)
- You should do all your SML programming in Emacs within the csenv-s20 virtual machine appliance or on tempest = cs.wellesley.edu. (If you wish to use tempest, contact Lyn about setting up the CS251 git repository in your tempest account.)
- It is strongly recommended that you learn (or review) Emacs, especially the keyboard shortcuts, before continuing with this problem. Start by taking the Emacs tour. Then do the Emacs tutorial, which you can run in Emacs via C-h t or M-x help-with-tutorial. Also consult the CS251 Emacs notes. The 2-page GNU Emacs Reference Card is also an exceptionally handy reference when learning Emacs keyboard commands.
- Review these notes on Using the SML/NJ REPL (Read-Eval-Print Loop) in Emacs, as well as the related slide in Lec 19 Introduction to SML. In particular, you should not run the SML repl in a Terminal window. Instead, create an SML interpreter within a *sml* buffer in Emacs. Then you can use M-p and M-n to avoid retyping your test expressions.
- In this and the following parts of this problem, write all of your SML code in a new file named yourAccountName-ps4-holo.sml that is within a new directory named ~/cs251/sml/ps4 folder on your csenv-s20 virtual machine. In particular, your workflow should be as follows:
  1. Create a new directory named ~/cs251/sml/ps4 from scratch as follows: ~~~ cd ~/cs251/sml mkdir ps4 ~~~
  2. Create a new file ~/cs251/sml/ps4/yourAccountName-ps4-holo.sml in Emacs by using the C-x C-f keyboard shortcut or the menu item File>Visit New File.
  3. Every time you change the file yourAccountName-ps4-holo.sml and want to test your changes in a *sml* SML interpreter butter, use the C-c C-b keyboard shortcut (followed by a return if prompted in the mini-buffer at the bottom of the screen) or the menu item SML>Process>Send Buffer. You may need to scroll down to the bottom of the *sml* buffer to see what has been loaded. These steps create a new *sml* buffer is created if one does not exist; otherwise, the existing *sml* buffer is reused.
- In all SML functions you define in this part and the remaining parts, your functions must have the exact SML name and the exact SML type specified in the problem description. (Lyn will test all your functions with an automatic test suite, which won’t workf if these conditions aren’t satisfied. There will be point penalties if Lyn has to manually edit your functions in order to test them.)
- In all of your SML programming, do not use #1, #2, etc. to extract tuple components or List.hd, List.tl, or List.null to decompose and test lists. Instead, use pattern matching on tuples and lists, as illustrated in examples from the SML lectures. (List.tl and List.null are permissible in some situations, but #1, #2, and List.hd should never be used.)
- Because hyphens are not allowed in SML identifiers, you should translate all hyphens in Racket identifiers either to underscores (so-called ``snake case’’) or camel case (in which new words after the first are capitalized). E.g., cartesian-product in Racket becomes cartesian_product or cartesianProduct in SML. Here and below, other name changes are also required due to limitations in SML identifiers; e.g., -> in digits->decimal is converted to To. In cases where I have already translated the function names for you, use exactly those names (so that they will work with my automated testing program for your SML functions).
- Liberally and carefully use explicit parentheses for grouping expressions in SML. Many type errors in SML programs come from unparenthesized epxressions that are parsed in ways unexpected by the programmer. In Lyn’s experience, missing or misplaced parens are the most common source of type errors for students learning to program in SML, so always check parens when debugging type errors.
- foldr, foldl, map, and List.filter are all built into SML:
```
val foldr = fn: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val foldl = fn: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
val map = fn: ('a -> 'b) -> 'a list -> 'b list

- List.filter;
val it = fn : ('a -> bool) -> 'a list -> 'a list
```
  Note that List.filter requires the explicit module prefix List., while the other functions do not. Go figure!
- Racket’s append translates to SML’s infix @ operator, but when you want to pass it as an argument to a first-class function you write it as op@.
- In this entire problem (not just this part) some instances of Racket’s cons will translate to SML’s infix list-prepending operator ::, while others will translate to the tupling notation (<exp1>, <exp2>) for pair creation. Reason about SML types to figure out which to use when. SML’s type checker will yell at you if you get it wrong.
- In this entire problem (not just this part) some instances of Racket’s list will translate to SML’s lists while others will translate to SML’s tuples. Again, reason about SML types to figure out which to use when.
- Control.Print.printLength controls how many list elements are displayed; after this number, ellipses are used. For example:
```
- Control.Print.printLength := 5;
val it = () : unit

- range 0 20;
val it = [0,1,2,3,4,...] : int list

- Control.Print.printLength := 20;
val it = () : unit

- range 0 20;
val it = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19] : int list
```
  Another such control is Control.Print.printDepth, which controls printing in nested lists.

allContainMultiple, keepBiggerThanNextV1, foldrTernop, and keepBiggerThanNextV2 (12 points) Translate the following Racket functions all-contain-multiple?, keep-bigger-than-next-v1, foldr-ternop, and keep-bigger-than-next-v2 into corresponding SML functions named doAllContainMultple, keepBiggerThanNextV1, foldrTernop, and keepBiggerThanNextV2:

(define (all-contain-multiple? m nss)
  (forall? (lambda (ns)
             (exists? (lambda (n) (= (remainder n m) 0))
                      ns))
            nss))

(define (keep-bigger-than-next-v1 nums)
  (if (null? nums)
      '()
       (map car (filter (λ (pair) (> (car pair) (cdr pair)))
                        (zip nums (rest nums))))))

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

(define (keep-bigger-than-next-v2 nums)
  (foldr-ternop (λ (fstNum rstNums bigs)
                  (if (null? rstNums)
                      '()
                      (if (> fstNum (first rstNums))
                          (cons fstNum bigs)
                          bigs)))
                '()
                nums))

For example:

val doAllContainMultiple = fn : int -> int list list -> bool
val keepBiggerThanNextV1 = fn : int list -> int list
val foldrTernop = fn : ('a * 'a list * 'b -> 'b) -> 'b -> 'a list -> 'b
val keepBiggerThanNextV2 = fn : int list -> int list

- doAllContainMultiple 5 [[17,10,2],[25],[3,8,5]];
val it = true : bool

- doAllContainMultiple 2 [[17,10,2],[25],[3,8,5]];
val it = false : bool

- doAllContainMultiple 3 [];
val it = true : bool

- keepBiggerThanNextV1 [6, 1, 4, 7, 2, 5, 9, 8, 3];
val it = [6,7,9,8] : int list

- keepBiggerThanNextV1 [9,7,8,6,4,5,3,1,2];
val it = [9,8,6,5,3] : int list

- keepBiggerThanNextV1 (range 0 20);
val it = [] : int list

- keepBiggerThanNextV2 [6, 1, 4, 7, 2, 5, 9, 8, 3];
val it = [6,7,9,8] : int list

- keepBiggerThanNextV2 [9,7,8,6,4,5,3,1,2];
val it = [9,8,6,5,3] : int list

- keepBiggerThanNextV2 (range 0 20);
val it = [] : int list

Notes:

SML includes the following analogs of forall?, exists?, and zip that you should use in your definitions:

- List.all;
val it = fn : ('a -> bool) -> 'a list -> bool

- List.exists;
val it = fn : ('a -> bool) -> 'a list -> bool

- ListPair.zip;
val it = fn : 'a list * 'b list -> ('a * 'b) list

Because SML does not allow ? in identifiers, Racket names containing ? need to be be transformed, as in all-contain-multiple? to doAllContainMultiple.
The List. and ListPair. indicate that these functions come from modules. Here is documentation on the List module, and here is documentation on the ListPair module.
In keepBiggerThanNext and foldrTernop, rather than using List.null nums or nums = [] to check for an empty list and List.hd and List.tl to extract the parts of a list, you should instead use pattern patching to to distinguish empty and nonempty lists and find the parts of a nonempty list. Here’s a simple example that illustrates such pattern matching:
```
fun mapScale factor [] = []
  | mapScale factor (num::nums) = (factor * num) :: (mapScale factor nums)
```

(12 points) genlist, partialSumsTable, iterate, and fibPairs (12 points). Translate the following Racket functions genlist-apply, partial-sums-table, iterate-apply, and fib-pairs functions into SML functions namded genlist, partialSumsTable, iterate, and fibPairs:

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

(define (partial-sums-table ns)
  (genlist-apply (λ (nums ans)
                   (list (rest nums) (+ (first nums) ans)))
                 (λ (nums ans) (null? nums))
                 #t              
                 (list ns 0)))

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

(define (fib-pairs threshold)
  ;; returns a list of pairs (a, b) used to calculate Fibonacci iteratively
  ;; until b is greater than or equal to the given threshold
  (iterate-apply (λ (a b pairs) (list b (+ a b) (cons (cons a b) pairs)))
                 (λ (a b pairs) (>= b threshold))
                 (λ (a b pairs) (reverse (cons (cons a b) pairs)))
                 '(0 1 ())))

For example:

val genlist = fn : ('a -> 'a) -> ('a -> bool) -> bool -> 'a -> 'a list
val partialSumsTable = fn : int list -> (int list * int) list
val iterate = fn : ('a -> 'a) -> ('a -> bool) -> ('a -> 'b) -> 'a -> 'b
val fibPairs = fn : int -> (int * int) list

- genlist (fn n => n * 2) (fn n => n > 1000) true 1;
val it = [1,2,4,8,16,32,64,128,256,512,1024] : int list

- genlist (fn n => n * 2) (fn n => n > 1000) false 1;
val it = [1,2,4,8,16,32,64,128,256,512] : int list

- partialSumsTable [7, 2, 5, 8, 4];
val it =
  [([7,2,5,8,4],0),([2,5,8,4],7),([5,8,4],9),([8,4],14),([4],22),([],26)]
  : (int list * int) list

- partialSumsTable (range 1 11);
val it =
  [([1,2,3,4,5,6,7,8,9,10],0),([2,3,4,5,6,7,8,9,10],1),([3,4,5,6,7,8,9,10],3),
   ([4,5,6,7,8,9,10],6),([5,6,7,8,9,10],10),([6,7,8,9,10],15),([7,8,9,10],21),
   ([8,9,10],28),([9,10],36),([10],45),([],55)] : (int list * int) list

(* Return the first sum of powers of 3 that's greater than 100 *)
- iterate (fn (power, sum) => (3*power, power+sum))
=         (fn (power, sum) => sum > 100)
=         (fn (power, sum) => sum)
=         (1, 0);
val it = 121 : int (* = 1 + 3 + 9 + 27 + 81 *)

- fibPairs 10;
val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13)] : (int * int) list

- fibPairs 50;
val it = [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55)]
  : (int * int) list

- fibPairs 100;
val it =
  [(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34),(34,55),(55,89),
   (89,144)] : (int * int) list

Notes:

SML does not allow ? in identifiers, so translate done? to is_done or isDone and similarly with keepDoneValue?
Translate Racket’s reverse to SML’s List.rev.
Use pattern matching on tuples when translating the (λ (nums ans) ...) and (λ (a b pairs) ...) functions; you should not use #1, #2, or #3 in any of your definitions. Translate these to (fn (nums,ans) => ...) and (fn (a,b,pairs) => ...). Because of SML’s built-in pattern matching, in SML it is unnecessary to have a separate function like Racket’s genlist-apply and iterate-apply (as distinct from genlist and iterate) in SML since the function arguments in SML’s genlist and iterate can already do pattern matching.

In SML, there is no need to distinguish Racket’s genlist and genlist-apply or to explicitly translate Racket’s apply function. In Racket, they are distinguished because apply provides a crude form of pattern matching when the state happens to be list. But in SML, pattern matching can be used with any function call.

For example, consider this function from Lec 15:

(define (fact-iterate-apply n)
  (iterate-apply
    (λ (num prod)
      (list (- num 1) (* num prod))    
    (λ (num prod) (<= num 0))
    (λ (num prod) prod)
    (list n 1)))

Here’s its translation into SML using iterate:

fun factIterateApply n =  
    iterate (fn (num, prod) => (num-1, prod*n))
            (fn (num, prod) => num < 0)   
            (fn (num, prod) => prod)          
            (n, 1)

Extra Credit Problem 1: Simplifying Inside Lambdas (9 points)

The small-step evaluation rules we have studied do not perform any evaluation of subexpressions inside the body of a lambda expression. The body is only ``opened up’’ for evaluation when the lambda expression is applied to argument values, at which point the argument values are substituted for the parameters in the body, and evaluation of the body proceeds.

However, it is possible to perform limited simplification of subexpressions inside the body of a lambda expression for purposes of optimization. Such simplifications can also make the body of a lambda expression easier to understand.

For example, consider the expression

(λ (w) 
  ((λ (x y) (+ (* x x) (* y y)))
   (+ 1 2) w))

According to our small-step evaluation rules, this is a value, and cannot be reduced more.

However, there are simplifications inside (λ (w) ...) we can perform that will not change its meaning:

We can simplify (+ 1 2) to 3. Performing an operation on two operand values within a function body is called constant folding. This yields the simplified expression:
```
(λ (w) 
  ((λ (x y) (+ (* x x) (* y y)))
   3 w))
```
We can apply the function (λ (x y) ...) to the values 3 and w, where for the purposes of simplification we will extend the set of values to include identifiers (w in this case). This yields the simplified expression. We’ll call this simplification value propagation.
```
(λ (w) (+ (* 3 3) (* w w)))
```
Finally we can perform one more constant folding step to yield
```
(λ (w) (+ 9 (* w w)))
```
This final lambda expression is much easier to understand than the original. Furthermore, the simplification steps we have performed avoid evaluation steps that would otherwise need to be performed later, so the simplification steps are actually optimizations that can improve the efficiency of the function (assuming it would be called more than once).

We will use the curvy arrow ↝ to indicate simplification steps within lambda bodies, as distinct from evaulation steps designated by ⇒. So the simplification steps shown above can be written:

(λ (w) 
  ((λ (x y) (+ (* x x) (* y y))) 
   (+ 1 2) w))
↝ (λ (w) 
    ((λ (x y) (+ (* x x) (* y y))) 
     3 w))
↝ (λ (w) (+ (* 3 3) (* w w)))
↝ (λ (w) (+ 9 (* w w)))

In this problem you will explore some of the benefits and limitations of such simplifications.

(2 points) We will call a simplification step within a lambda expression safe if (1) it does not change the meaning of the function denoted by the lambda or (2) the simplified function does not do more work than the unsimplified one when called. Otherwise it is unsafe.

Even in simplification, substitution can only be performed when lambda expressions are applied to values, not to arbitrary expressions. Using the following expressions, show that substituting arbitrary expressions for lambda parameters in the lambda body can be unsafe:
- (λ (a) ((λ (b) (* b b)) (+ a a)))
- (λ (c) ((λ (d) (+ c 1)) (/ 1 0)))

(5 points) We have studied functions like the following in lecture:

(define curry2 (λ (binop) (λ (y) (λ (z) (binop y z)))))
(define uncurry2 (λ (curried-binop) (λ (a b) ((curried-binop a) b))))
(define flip2 (λ (binop) (λ (s t) (binop t s))))
(define o (λ (f g) (λ (x) (f (g x)))))

The goal in this subproblem is to understand the meaning of this mystery function:

(define mystery (uncurry2 (o (curry2 map) (curry2 (flip2 -)))))

We will begin by applying evaluation steps until we can’t get any further:

(uncurry2 (compose (curry2 map) (curry2 (flip2 -))))

# Replace uncurry2, o, curry2, and flip by definitions
⇒* ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
    ((λ (f g) (λ (x) (f (g x))))
     ((λ (binop) (λ (y) (λ (z) (binop y z)))) map)
     ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2)))) # Rename y & z to y2 and z2 for clarity
      ((λ (binop) (λ (s t) (binop t s))) -))))

# Apply (λ (binop) (λ (y) (λ (z) (binop y z)))) to map
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2))))
     ((λ (binop) (λ (s t) (binop t s))) -))))

# Apply (λ (binop) (λ (s t) (binop t s))) to -
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    ((λ (binop) (λ (y2) (λ (z2) (binop y2 z2))))
     (λ (s t) (- t s)))))

# Apply (λ (binop) (λ (y2) ...)) to (λ (s t) (- t s))
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop a) b)))
   ((λ (f g) (λ (x) (f (g x))))
    (λ (y) (λ (z) (map y z)))
    (λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2)))))

# Apply (λ (f g) ...) to (λ (y) ...) and (λ (y2) ...)
⇒ ((λ (curried-binop) (λ (a b) ((curried-binop 
                                 a) 
                                b)))
   (λ (x) ((λ (y) (λ (z) (map y z)))
           ((λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2))) x))))

# Apply (λ (curried-binop) ...) to (λ (x) ...) 
⇒ (λ (a b) (((λ (x) ((λ (y) (λ (z) (map y z)))
                     ((λ (y2) (λ (z2) ((λ (s t) (- t s)) y2 z2))) x)))
              a) 
            b))

Evaluation steps get us partway toward our goal, but leave us with a complicated mess that is very difficult to understand! But you can use the simplification steps described above to further simplify it into something that is understandable.

Being very careful, start with the last expression in the evaluation sequence and apply one simplification step at a time until you cannot simplify the function any more. You should end up with a function that is very easy to understand. In addition to producing the simplified function expression, explain in English what the function does.

(2 points) If simplifications within lambda expressions are so helpful, why don’t we always apply them as part of evaluation? There is a good reason. Based on the following example, explain why simplifying the body of lambda expressions is not allowed in small-step evaluation:
```
(λ (n) 
  (if (> n 0) 
      (+ n 1)
      ((λ (y) (y y)) (λ (z) (+ 1 (z z))))))
```

Extra Credit Problem 2: Compositional Programming (10 points)

Consider the following sum-nested-filtered-cubes function:

(define (sum-nested-filtered-cubes n)
  (foldr + 0
         (map (λ (row)
                (foldr + 0
                       (filter (λ (cubed) (>= (remainder cubed 10) 5))
                               (map (λ (n) (expt n 3))
                                    row))))
              (map (λ (i) (range 1 (+ i 1)))
                   (range 1 (+ n 1))))))

Given a nonnegative input n, it calculates

$\sum_{i=1}^n\sum_{k=1}^{i}(k^3 \;\textrm{s.t}\;k^3\;\textrm{ends in a digit}\;\geq 5)$

(2 points) Many functions can be express by nesting invocations of higher-order functions like foldr, map, and filter. Below is an example. Explain in English what the sum-nested-filtered-cubes function does. Do not explain in words the Racket code or algorithm. Rather, given input n, describe the output in declarative terms, like you might see in a contract for the sum-nested-filtered-cubes function without seeing its implementation.

It may be helpful to use the mathematical notation for summation in your solution. For example, the following notation means the sum of the squares of all integers i between 1 and 10:
$\sum_{i=1}^{10}i^2$

(10 points) Consider the following helper functions:

(define (id x) x)
(define (o f g) (λ (x) (f (g x))))
(define o-all (lambda funs (foldr o (λ (x) x) funs))) ; uses a "rest arg" explained in Lec 13
(define (flip2 binop) (λ (x y) (binop y x)))

Using such functions in conjunction with Racket’s curry function, we can express nested invocations like those in sum-nested-filtered-cubes using compositions of combinators, which are expressions that denote functions without using explicit lambdas. For example, here is a definition for a function that sums the squares of odd integers from 1 up to (and including) a given limit:

(define sum-of-squares-of-odds-up-to-composed
  (λ (n)
    (foldr + 0
       (map (λ (x) (expt x 2))
            (filter (λ (i) (= 1 (remainder i 2)))
                    (range 1 (+ 1 n)))))))

> (sum-of-squares-of-odds-up-to-composed 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

We cam now transform this in a sequence of steps into a definition that does not use any lambdas. First, however, we will introduce a bunch of lambdas so that we can express the nested expressions above in terms of o-all.

(define sum-of-squares-of-odds-up-to-composed2
  (o-all (λ (squares) (foldr + 0 squares))
         (λ (odds) (map (λ (x) (expt x 2)) odds))
         (λ (ints) (filter (λ (i) (= 1 (remainder i 2))) ints))
         (λ (hi) (range 1 hi))
         (λ (n) (+ 1 n))
         ))

> (sum-of-squares-of-odds-up-to-composed2 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

Now we can use curry to remove the outermost lambdas.

(define sum-of-squares-of-odds-up-to-composed3
  (o-all (curry foldr + 0)
         (curry2 map (λ (x) (expt x 2)))
         (curry filter (λ (i) (= 1 (remainder i 2))))
         (curry range 1)
         (curry + 1)
         )))

> (sum-of-squares-of-odds-up-to-composed3 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

Now we use flip2 and o to prepare the remaining lambdas for removal

(define sum-of-squares-of-odds-up-to-composed4
  (o-all (curry foldr + 0)
         (curry map (λ (x) ((flip2 expt) 2 x)))
         (curry filter (o (λ (k) (= 1 k)) (λ (i) ((flip2 remainder) 2 i))))
         (curry range 1)
         (curry + 1)
         ))

> (sum-of-squares-of-odds-up-to-composed4 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

Finally we use curry to eliminate the remaining lambdas:

(define sum-of-squares-of-odds-up-to-composed5
  (o-all (curry foldr + 0)
         (curry map (curry (flip2 expt) 2))
         (curry filter (o (curry = 1) (curry (flip2 remainder) 2)))
         (curry range 1)
         (curry + 1)
         ))

> (sum-of-squares-of-odds-up-to-composed 9)
165 ; 1^2 + 3^2 + 5^2 + 7^2 + 9^2

Give a similar sequence of transformations that starts with sum-nested-filtered-cubes and ends with a definition that has the following pattern, where each of the functions <fun_1> through <fun_k> is expressed without using any explicit lambdas:

(define sum-nested-filtered-cubes-composed
  (o-all <fun_1> 
         ...
         <fun_k>))

Notes:

Liberally use helper functions as in the definition of sum-of-squares-of-odds-up-to-composed. If you can’t get rid of all explicit lambdas, get rid of as many as you can.
It is recommended that you start with a version sum-nested-filtered-cubes-composed with explicit lambdas and remove one at a time, checking that the resulting definition behaves like the original after each removal. For example, to test on inputs between 0 and 10 inclusive:
```
> (map (λ (n) (cons n (sum-nested-filtered-cubes-composed))) (range 11))
'((0 . 0) (1 . 0) (2 . 8) (3 . 43) (4 . 78) (5 . 238) (6 . 614) (7 . 990) (8 . 1366) (9 . 2471) (10 . 3576))
```

Extra Credit Problem 3: Church Numerals (19 points)

Although this problem is worth a significant number of extra credit points, it is conceptually challenging. But it can be a lot of fun, especially if you’re mathematically inclined.

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

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

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

> ((twice add1) 0)
2

> ((thrice add1) 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 will see below, you can even do arithmetic on these representations! In fact, these representations are called Church numerals for this reason.

(6 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?
(3 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)). You are not allowed to use Racket integers or arithmetic on integers in your definition of inc. For example, it would be easy to define inc as
```
(define (inc churchNum)
  (cn-fold (+ 1 ((churchNum (lambda (x) (+ x 1))) 0))))
```
but this kind of definition is prohibited.
(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. As in the previous part, you are not allowed to use Racket integers or arithmetic on integers in your definition of dec.

Extra Credit Problem 4: List Processing with Tail Recursion and Loops (15 points)

Note: In some 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))
```

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

(10 points) In the file yourAccountName-ps4.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))

1. Iterating with genlist-apply, foldl and iterate-apply (24 points)

2. n-fold Composition (10 points)

3. Pair Generation (40 points)

4. Higher-order List Operators in SML (36 points)

Extra Credit Problem 1: Simplifying Inside Lambdas (9 points)

Extra Credit Problem 2: Compositional Programming (10 points)

Extra Credit Problem 3: Church Numerals (19 points)

Extra Credit Problem 4: List Processing with Tail Recursion and Loops (15 points)

1. Iterating with `genlist-apply`, `foldl` and `iterate-apply` (24 points)