• Dueish: Wed Nov 25. For the purposes of the two-day grace period, the days of Thanksgiving Break do not count, so you have until the Tue after Thanksgiving break to turn this in without any explanation. However, it’s in your best interest to get as much of this done before break as you can.

  • 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 PS3. Be sure to study the solutions to PS3 before doing this assignment.

    • This assignment has 38 solo points.

  • How to Start Solo Assignment C

    Follow the instructions in the GDoc CS251-F20-T2 Pset Submission Instructions for creating your SOLO-C Google Doc. Put all written answers and a copy of all code into this SOLO-C GDoc.

  • Submission:

    • For all parts of all problems, include all answers (including the small-step derivation and all Racket code) in your SOLO-C 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 (Composition Semantics), include your small-step derivation in your GDoc.
    • For Problem 2 (Recursive List Functions)
      • Be sure that all function definitions in yourAccountName-solo-c-functions.rkt also appear in your Google Doc (so that I can comment on them)
      • Drop a copy of your yourAccountName-solo-c-functions.rkt in your ~/cs251/drop/solo-c drop folder on cs.wellesley.edu.

1. Composition Semantics (7 points)

Consider the following Racket functions, which also appear in PS4 Problem 2:

(define o (λ (f g) (λ (x) (f (g x)))))
(define inc (λ (y) (+ y 1)))
(define dbl (λ (z) (* z 2)))

Recall that o is the function composition operator. (BTW, SML has a built-in infix o operator for function composition that means the same thing.)

Use the rules of small-step semantics to show a derviation of all steps in evaluating the expression ((o inc dbl) 10). As you did in PS3 Problem 1, (1) use curly braces to show the redex in each step and (2) show the justification for each step in square brackets.

2. Folding (31 points)

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

  • Define all of your functions in a new file named yourAccountName-solo-c-functions.rkt that you create in Dr. Racket. Copy the following helper function definitions to the beginning of your file:

    (define (map-cons x ys)
  (map (curry cons x) ys))

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

(define (exists? pred xs)
  (and (not (null? xs))
       (or (pred (first xs))
           (exists? pred (rest xs)))))
    
(define (foldr-ternop ternop null-value xs)
  (if (null? xs)
      null-value
      (ternop (first xs)
              (rest xs)
              (foldr-ternop ternop null-value (rest xs)))))

    You may use these helper fuctions in your definitions.

  • You have seen many of these functions before in Solo Assignment B in the context of explicit recursion. But in this problem:
    • You must not use explicit recursion on lists in any of your definitions.
    • You must use higher-order list operations (e.g., foldr, foldr-ternop, map)
    • You must not define any functions other than (1) the four helper functions defined above and (2) the seven required functions below.
  • Unless otherwise stated in a subproblem, the only built-in Racket list operators you may use in your definitions are: null, null?, cons, car, cdr, list, append, first, second, third, and rest. You may also use any Racket math or logic operators, such as +, max, etc. You must not use any form of list reversal in any of your solutions.

  1. (4 points) Using foldr, define a function (unzip pairs) that takes a list of pairs (cons cells) and returns a list of two lists that, if zipped together with zip, would yield the original pairs.

    > (unzip '((1 . 5) (2 . 6) (3 . 7) (4 . 8)))
'((1 2 3 4) (5 6 7 8))

> (unzip (zip (list 1 2 3 4) (list 5 6 7 8)))
'((1 2 3 4) (5 6 7 8))
 
> (unzip (list))
'(() ())

    Your definition must flesh out the following skeleton:

    (define (unzip pairs)
  (foldr ; combining function goes here.
         ; null value goes here. 
         pairs))

  2. (4 points) A length-n prefix of a list is a list containing its first n elements in the same relative order. For example:

    • The length-0 prefix of '(5 8 4) is '()
    • The length-1 prefix of '(5 8 4) is '(5)
    • The length-2 prefix of '(5 8 4) is '(5 8)
    • The length-3 prefix of '(5 8 4) is '(5 8 4)

    Define a function prefixes that takes a list as its single argument and returns a list of all of its prefixes ordered from shortest to longest. For example:

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

    Your definition must flesh out the following skeleton:

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

  3. (5 points) Using foldr, define a function sum-max-squaresEvens that takes a list of integers its single argument and returns a triple (i.e., a three-element list) whose three elements are (1) the sum of the numbers in the list; (2) the maximum of the numbers in the list and (3) a list of the squares of all the even numbers in the list (maintaining relative order).

     > (sum-max-squaresEvens '(9 2 8 5 4 7 1 6 3))
 '(45 9.0 (4 64 16 36))
 > (sum-max-squaresEvens '(2 8 5 4 7 1 6 3))
 '(36 8.0 (4 64 16 36))
 > (sum-max-squaresEvens '(8 5 4 7 1 6 3))
 '(34 8.0 (64 16 36))
 > (sum-max-squaresEvens '(5 4 7 1 6 3))
 '(26 7.0 (16 36))
 > (sum-max-squaresEvens '(-9 2 -8 5 4 -7 1 -6 3))
 '(-15 5.0 (4 64 16 36))
 > (sum-max-squaresEvens (append (range 1 101 7) (range 201 0 -2)))
 '(10951 201.0 (64 484 1296 2500 4096 6084 8464))

    Your definition must flesh out the following skeleton:

    (define (sum-max-squaresEvens ints)
  (foldr ; combining function goes here.
         ; null value goes here. 
         ints))

  4. (4 points) Suppose that we represent a set in Racket as a list without duplicates. Using foldr, define a function (subsets set) that returns a list of all subsets of a given set. The subsets within this can be in any order, but the order of elements within each set should have the same relative order as in set.

    For example here are some of the (huge number of) possible answers for (subsets '(3 1 2)), any single one of which would be considered correct:

    '(() (1) (2) (3) (1 2) (3 1) (3 2) (3 1 2))
'((3 1 2) (3 2) (3 1) (1 2) (3) (2) (1) ())
'(() (2) (1) (1 2) (3) (3 2) (3 1) (3 1 2))  
'((3 1 2) () (3 1) (2) (3) (1 2) (1) (3 2))

    However, lists containing subsets like (2 1), (1 3), (3 2 1), or (1 2 3) could not be solutions, since the elements of these subsets are not in the same relative order as in (3 1 2).

    Your definition must flesh out the following skeleton:

    (define (subsets set)
  (foldr ; combining function goes here.
         ; null value goes here. 
         set))

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

  5. (4 points) A length-n suffix of a list is a list containing its last n elements in the same relative order. For example:

    • The length-0 suffix of '(5 8 4) is '()
    • The length-1 suffix of '(5 8 4) is '(4)
    • The length-2 suffix of '(5 8 4) is '(8 4)
    • The length-3 suffix of '(5 8 4) is '(5 8 4)

    Define a function suffixes that takes a list as its single argument and returns a list of all of its suffixes ordered from longest to shortest. For example:

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

    Your definition must flesh out the following skeleton:

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

  6. (5 points) In this part, you will define a function related to suffixes named weighted-suffixes, which is assumed to take a list of numbers. The result of weighted-suffixes is a list similar to that returned by suffixes except that each nonempty sublist in the result of weighted-suffixes is the result of scaling all numbers in the corresponding nonempty sublist in the result of suffixes by its first element. (The empty sublist in suffixes yields the empty sublist in weighted-suffixes).

    For example, (weighted-suffixes '(7 2 5 8 4)) returns '((49 14 35 56 28) (4 10 16 8) (25 40 20) (64 32) (16) ()) because:

    • (49 14 35 56 28) is the result of scaling (7 2 5 8 4) by 7
    • (4 10 16 8) is the result of scaling (2 5 8 4) by 2
    • (25 40 20) is the result of scaling (5 8 4) by 5
    • (64 32) is the result of scaling (8 4) by 8
    • (16) is the result of scaling (4) by 4
    • () is the sublist in the result of weighted-suffixes that corresponds to the sublist () in the result of suffixes

    Here are more examples of weighted-suffixes, the last two of which illustrate negative numbers:

     > (weighted-suffixes (range 3 8))
 '((9 12 15 18 21) (16 20 24 28) (25 30 35) (36 42) (49) ())

 > (weighted-suffixes (range 1 11))
 '((1 2 3 4 5 6 7 8 9 10)
   (4 6 8 10 12 14 16 18 20)
   (9 12 15 18 21 24 27 30)
   (16 20 24 28 32 36 40)
   (25 30 35 40 45 50)
   (36 42 48 54 60)
   (49 56 63 70)
   (64 72 80)
   (81 90)
   (100)
   ())
    
 > (weighted-suffixes '(-2 6 1 -3 -8 4 7 -5))
 '((4 -12 -2 6 16 -8 -14 10)
   (36 6 -18 -48 24 42 -30)
   (1 -3 -8 4 7 -5)
   (9 24 -12 -21 15)
   (64 -32 -56 40)
   (16 28 -20)
   (49 -35)
   (25)
   ())

 > (weighted-suffixes (range -3 4))
 '((9 6 3 0 -3 -6 -9) (4 2 0 -2 -4 -6) (1 0 -1 -2 -3) (0 0 0 0) (1 2 3) (4 6) (9) ())

    Use foldr-ternop to define weighted-suffixes. Your definition must flesh out the following skeleton:

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

    Note: Recall that you may not define any new helper functions. But you may use map.

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

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

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

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

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

 > (keepBiggerThanSomeFollowing '(8))
 '()

 > (keepBiggerThanSomeFollowing '())
 '()

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

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

    Note: You may use the following exists? function from PS3 that you defined at the top of your yourAccountName-solo-c-functions.rkt file.

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