Restrictions

1. You must work on this homework with your assigned partner.
2. You must use either ISL (recommended) or ISL with lambda.

The List Data Definition

You should use the following data design for lists. You can copy it verbatim or just refer to [List-of X]. We will know that you’re refering to this block of code.

;; A [List-of X] is one of
;; - '()
;; - (cons X [List-of X])
;; Interpretation: A list of elements of type X.

;; list-template : [List-of X] -> ?
(define (list-template alist)
  (cond
    [(empty? alist) ...]
    [(cons? alist) (... (first alist) (list-template (rest alist)) ...)]))

(define EX-STRING-LIST (cons "a" (cons "b" '())))
(define EX-NUM-LIST (cons 1 (cons 2 (cons 3 '()))))
(define EX-LIST-LIST (cons (cons 1 (cons 20 '())) (cons (cons 2 '()) '())))

Bouncing Balls

This problem relies on the following data design, which you should copy verbatim.

(define-struct ball (x y vx vy))
;; A Ball is a (make-ball Number Number Number Number)
;; Interpretation: A ball with position (x, y) and velocity (vx, vy)

;; ball-template : Ball -> ?
(define (ball-template b)
  (... (ball-x b) ... (ball-y b) ... (ball-vx b) ... (ball-vy b) ...))

(define EX-STATIONARY-BALL (make-ball 100 200 0 0))
(define EX-BALL-MOVING-HORZ (make-ball 100 200 10 0))
(define EX-BALL-MOVING-VERT (make-ball 100 200 0 10))
(define EX-BALL-MOVING-DIAG (make-ball 100 200 10 10))

Design a function called animate-balls that consumes a list of balls, a height, and a width, and animates the balls moving around in a window of the given dimensions. The balls should bounce of the sides of the window but may go through each other. You may assume that all the balls start within the window.

Hint: Keep in mind that balls can go out of window within a time step. You might need to model these as collisions with the wall during that time step.

Not graded: for fun and challenge, you can make sure the balls do not collide with each other.

List Processing Functions

1. Design the function interleave, that takes two list of numbers and produces a list of their items, alternating from each list. If the lists have different lengths, just finish with all the remaining items of the longer list.

2. Design the function prime-factors that consumes a positive integer and produces a list of the prime factors of that integer in ascending order (including duplicates). You may assume that the input is a positive integer.

   Example: (check-expect (prime-factors 16) (list 2 2 2 2))

3. Design the function powerlist which returns all possible sublists of a list of numbers. A sublist of a list is any list whose items appear in the same relative order that they do in the initial list and all of the items appear in the initial list. Assume the initial list given to powerlist contains no duplicates.

4. Design the function intersection, which given a non-empty list of list of numbers returns the numbers that appear in every sublist. Assume each inner list does not repeat numbers. Note that while the outer list is non-empty, inner lists may be empty.

5. Design the function earliest, which takes a non-empty list of strings and a function (that takes two strings and outputs a Boolean, and indicates whether or not the first string comes “before” the second one). The earliest function should output the string that comes earliest in the non-empty list according to the given function.

   Then, use earliest to define three other functions:

   a. One that produces the string that comes earliest lexicographically (i.e., which would come first in a dictionary). Hint: string<? is quite useful.

   b. One that produces the string that comes last lexicographically.

   b. One that produces the last string in the non empty list.

Building Abstractions 1

Consider the three functions below (we have deliberately omitted tests):

;; hello-everyone: [List-of String] -> [List-of String]
;; Greets everyone in the list.
(define (hello-everyone los)
  (cond
    [(empty? los) '()]
    [(cons? los) (cons (string-append "Hello, " (first los) "!")
                       (hello-everyone (rest los)))]))

;; words-until-period: [List-of String] -> [List-of String]
;; Produces the words in the list up to the first period.
(define (words-until-period los)
  (cond
    [(empty? los) '()]
    [(cons? los) 
     (if (string=? (first los) ".")
         '()
         (cons (first los) (words-until-period (rest los))))]))

;; starting-positive-numbers : [List-of Number] -> [List-of Number]
;; Produces the prefix of positive numbers in the list.
(define (starting-positive-numbers lon)
  (cond
    [(empty? lon) '()]
    [(cons? lon)
     (if (<= (first lon) 0)
         '()
         (cons (first lon) (starting-positive-numbers (rest lon))))]))

1. It is possible to design a list abstraction that can be used to simplify two of the three functions defined above. Design that list abstraction and name it hw2-ba1.

2. Use the list abstraction you designed in Part A to rewrite the functions above that you can.

Building Abstractions 2

Consider the following purpose statements and tests:

1. Given a list of names, produces two strings for each string NAME.

   (check-expect (hello-goodbye '()) '())
   (check-expect
     (hello-goodbye (cons "Alice" (cons "Bob" '())))
     (cons "Hello Alice!" (cons "Goodbye Alice!" (cons "Hello Bob!" (cons "Goodbye Bob!" '())))))
   

2. Given a list of numbers, produces a list with two numbers for each number x: (* 2 x) and (* 4 x).

   (check-expect (double-double '()) '())
   (check-expect (double-double (cons 10 (cons 20 '())))
                 (cons 20 (cons 40 (cons 40 (cons 80 '())))))
   

3. Given a list of strings, produces a list with two numbers for each string: the length, followed by half the length.

   (check-expect (string-length-length '()) '())
   (check-expect (string-length-length (cons "Hello" '()))
                 (cons 5 (cons 2.5 '())))
   

Design a list abstraction (following the list template) with name hw2-ba2, then use that abstraction to design the three functions above.