CS 251: Solo Assignment B

Dueish: Wed Nov 18
Notes:
- This is a solo assignment. You must complete all parts of this assignment entirely on your own without help from any other person and without consulting any resources other than course materials or Racket documentation. You may ask Lyn for clarification, but not for help.
- You can do all problems on this assignment based on material you learned for PS2. Be sure to study the solutions to PS2 before doing this assignment.
- This assignment has 30 solo points.
How to Start Solo Assignment B

Follow the instructions in the GDoc CS251-F20-T2 Pset Submission Instructions for creating your SOLO-B Google Doc. Put all written answers and a copy of all code into this SOLO-B GDoc.
Submission:
- For all parts of all problems, include all answers (including the small-step derivation and all Racket code) in your SOLO-B GDoc. Please format your big/small-step derivation in Problem 1 and your Racket function definitions in Problem 2 so that they’re easy to read. Format all derivations and code using a fixed-width font (Courier New or Consolas). You use a small font size if that helps.
- For Problem 1 (Alternative If Semantics), include your explanation and your small-step derivation in your GDoc.
- For Problem 2 (Recursive List Functions)
  - Be sure that all function definitions in yourAccountName-solo-b-functions.rkt also appear in your Google Doc (so that I can comment on them)
  - Drop a copy of your yourAccountName-solo-b-functions.rkt in your ~/cs251/drop/solo-b drop folder on cs.wellesley.edu.

1. Alternative If Semantics (5 points)

The small-step reduction rules for if expressions in Racket are

(if V_test E_then E_else) ⇒ E_then, if V_test is a value that is not #f [if nonfalse]
(if #f E_then E_else) ⇒ E_else [if false]

Lois Reasoner thinks that the reduction of if expressions should be changed to:

(if V_test V_then V_else) ⇒ V_then, if V_test is a value that is not #f [if nonfalse Lois]
(if #f V_then V_else) ⇒ V_else [if false Lois]

These differ from the actual rules by requiring that all three subexpressions E_test, E_then, and E_false of (if E_test E_then E_false) are first evaluated to values before the if expression can be simplified.

Explain that Lois’s alternative semantics for if are a bad idea. In particular, consider the sum-between function from PS2:

(define sum-between
  (lambda (lo hi)
    (if (> lo hi)
        0
        (+ lo (sum-between (+ lo 1) hi)))))

Use Lois’s semantics for if in a small-step semantics derivation for the evaluation of (sum-between 2 3) to explain what happens. Use λ_sb as an abbreviation for the lambda expression that sum-between names. You needn’t show every step, but at the very least should show lines in which the redex is λ_sb applied to two values.

2. Recursive List Functions (25 points)

In this problem you will define three recursive functions on lists. Some ground rules:

Define all of your functions in a new file named yourAccountName-solo-b-functions.rkt that you create in Dr. Racket.
You should use explicit recursion on lists in all of your definitions.
Unlike in PS2 Problem 4, you are not required to explicitly show the Divide/Conquer/Glue steps for the list recursive functions you defined. Nevertheless, as always, you are strongly encouraged to use these steps as part of thinking about the problems and developing your solutions.
You should not use any higher-order list operations (e.g., map, filter, foldr, foldl, iterate, or genlist) in this problem.
The only built-in Racket list operators you may use in your definitions are: null, null?, cons, list, append, first, second, third, and rest. (You may also use any Racket math or logic operators, such as +, max, etc.)
You should use Racket’s let construct to avoid evaluating an expression more than once.
In this problem, you should define and use the following map-cons helper function:
```
(define (map-cons x yss)
  (if (null? yss)
      null
      (cons (cons x (first yss)) (map-cons x (rest yss)))))
```
You may use this map-cons helper function in any part of this problem where you find it useful.
Other than the above map-cons function, you should not use any other helper functions in this problem except for the one helper function specified in 1d weighted-suffixes.

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

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

(8 points) Define a function sum-max-squaresEvens that takes a list of integers its single argument and returns a triple (i.e., a three-element list) whose three elements are (1) the sum of the numbers in the list; (2) the maximum of the numbers in the list and (3) a list of the squares of all the even numbers in the list (maintaining relative order).
```
 > (sum-max-squaresEvens '(9 2 8 5 4 7 1 6 3))
 '(45 9.0 (4 64 16 36))
 > (sum-max-squaresEvens '(2 8 5 4 7 1 6 3))
 '(36 8.0 (4 64 16 36))
 > (sum-max-squaresEvens '(8 5 4 7 1 6 3))
 '(34 8.0 (64 16 36))
 > (sum-max-squaresEvens '(5 4 7 1 6 3))
 '(26 7.0 (16 36))
 > (sum-max-squaresEvens '(-9 2 -8 5 4 -7 1 -6 3))
 '(-15 5.0 (4 64 16 36))
 > (sum-max-squaresEvens '(-6 -3 -10 -5 -8))
 '(-32 -3.0 (36 100 64))
 > (sum-max-squaresEvens (append (range 1 101 7) (range 201 0 -2)))
 '(10951 201.0 (64 484 1296 2500 4096 6084 8464))
```
Notes:
- Your sum-max-squaresEvens 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.
- Depending on how you determine the maximum, the result might display as a floating point number (as in 9.0) or as an integer (as in 9).
(5 points) Suppose that we represent a set in Racket as a list without duplicates. Define a function subsets that takes as its single argument a set and returns a list of all subsets of a given set. The subsets within the result list 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).
(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) ())
```
Note: Recall that you cannot use the higher-order map function here. So, in this problem, in addition to weighted-suffixes, you will need to define a recursive list helper function that implements the mapping pattern to scale all elements in a list of numbers by a given scaling factor.