CS 2500 Honors Lab 7: Abstraction and Functions as Values

• Work in pairs
• Change roles often!
• Follow the design recipe for every problem.

Abstraction Over Values

Sometimes when we solve problems, we find that the solution to one problem looks a lot like the solution to another one. Check out these functions and data definition: (from now on we will leave out the definition for lists, and use the [listof X] notation)

;; A [listof Number] is one of
;;  -- empty
;;  -- (cons Number [listof Number])

;; lon-add2 : [listof Number] -> [listof Number]
;; Add two (2) to each element of the given list of numbers
(define (lon-add2 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 2)
                    (lon-add2 (rest lon)))]))


;; lon-add5 : [listof Number] -> [listof Number]
;; Add five (5) to each element of the given list of numbers
(define (lon-add5 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 5)
                    (lon-add5 (rest lon)))]))
    

Is it clear what each function does? You are hopefully asking "Why would you do that?!" since they are almost exactly the same.

Exercise 1:

Write a function named lon-add-n that abstracts both of the functions above, taking an extra argument, which is the number to be added to each element.

Note: Follow the recipe for abstraction...

Exercise 2:

Rewrite (recreate) both lon-add2 and lon-add5 using your more general function, and write a few tests for each to be sure they work as expected.

---

Abstraction Over Functions

As you've seen in class, functions in DrRacket (as in many other nice programming languages) are considered data just like 5 or (list 'hello). We can name them with defines, return them from and pass them to other functions, and even store them in structures.

Suppose we implemented this function:

;; lon-sub-n : [listof Number] Number -> [listof Number]
;; Subtract 'n' from each element of the given list of numbers
(define (lon-sub-n lon n) ...)
      

This looks like the function you just implemented right? Substitute - for + and they are actually the same. Substitution... Isn't that just what "plugging-in" does?

Exercise 3:

If you were to abstract these two functions into a single, more general one, What would be its contract?

Be Precise... you will need another arrow (->) in it.

Exercise 4:

Write the function, name it lon-do-n, that abstracts both of the functions, taking an extra argument, which is the function to be applied to each element and the given number.

Exercise 5:

Rewrite (or write) both lon-add-n and lon-sub-n using your more general function, and write a few tests for each to be sure they work as expected.

---

More Abstraction

Important: Change your DrRacket language level to “Intermediate Student with lambda” (and there was much rejoicing...). If local isn't familiar then please review Section 18 of HtDP.

Here's a function that returns a function:

;; add-n : ??
(define (add-n n)
  (local [(define (f m) (+ n m))]
    f))
    

If you get confused by all the variable names, then run "Check Syntax" and use your mouse to see how all of them interact.

Exercise 6:

Fill in its contract and give it a meaningful purpose statement... again, you need another arrow, right?

Exercise 7:

Write some tests for it. After you figure out the purpose, this should be easy.

Hint: In order to test a function that returns a function, you will have to apply the result to something, e.g.:

     ((add-n 5) 7) ;; => 12
          

If it makes you more comfortable, use a definition to name the function that is returned, then call that on an argument.

Exercise 8:

Review DrRacket's built-in abstract functions here. Use map to rewrite lon-add-n and lon-sub-n using add-n from above (remember, subtraction is like adding a negative number, right?). Use your check-expects from earlier to be sure your newly designed functions operate the same as before. Question: Do all the contracts match up accordingly?

---

DrRacket's "loop" functions

Remember all that stuff we did with lists and structural recursion? Well, DrRacket has built-in functions to help us write functions that deal with lists. (See here.)

For the functions below, remember that DrRacket has the functions odd? and even? built-in; both are (Number -> Boolean).

Exercise 9:

Design a function all-odd? that takes a [listof Number] and returns true if all the numbers in the list are odd, and false otherwise. Hint: use andmap.

Exercise 10:

Design the same function, call it all-odd-2?, but use ormap this time. Hint: if all the numbers are odd, then none of them are even, right?

Exercise 11:

Design the function between that takes two numbers (say low and high) and returns a list of all numbers from low to high-1 (inclusive). Use build-list.

Hint: The first argument to build-list is the length of the list that you want to build. The second argument is a function that takes an argument i and returns the item that you want to be at position i in the list (starting from 0!).

Exercise 12:

Using your function between, design the function evens that takes two numbers, and returns a list of all the even numbers in that range. Use filter.

Exercise 13:

Using foldr or foldl, implement the function sum that computes the sum of all the elements in a list of numbers.

Study this function definition:

;; minus-all : Number [listof Number] -> Number
;; Subtract all the numbers in the list from the given one
(define (minus-all n lon)
  (foldl - n lon))

(minus-all 20 empty)            ;==> 20
(minus-all 20 (list 5 2))       ;==> 13
(minus-all 20 (list 5 4 3 2 1)) ;==> 5
      

Exercise 14:

Why doesn't this function work? Fix the function so that it produces the correct results. Hint: subtraction is not commutative... i.e., it is order dependent.

---

Finally Something Fun...

Ok... now that we're through all that, we'll design some animation functions, and put them all together with the loop functions to get a fun little program.

Here's our world definitions:

(require 2htdp/image)
(require 2htdp/universe)

;; ****************************
;; A World is a  [listof Rect]

;; A Rect is:
;;     (make-rect Posn Posn String)
;; where the first posn is the rect's current position, the second
;;   is its velocity (speed in x and y) and the string is its color
(define-struct rect (pnt vel color))

;; Gravitational Acceleration
(define G-ACCEL 2)

;; Width and Height of each rectangle
(define RW 10)
(define RH 10)

;; Width and Height of the Scene
(define SW 400)
(define SH 400)

      

In other words, our world is a list of Rect (blocks). Each one knows where it is (pnt), its velocity vector (vel) and its color.

Exercise 15:

Design the function gravity ([listof Rect] -> [listof Rect]) that adds (remember Y is upside down on the screen) the G-ACCEL constant to the y component of the velocity of each element of the World. Use map.

Exercise 16:

Design the function move ([listof Rect] -> [listof Rect]) that moves each Rect one step in the direction it is headed. Use map.

Hint: (X_new, Y_new) = (X_old + X_vel, Y_old + Y_vel)

Exercise 17:

Design the function only-on-screen ([listof Rect] -> [listof Rect]) that removes the Rects that are not on the screen from the world. Use filter.

Exercise 18:

Design the function draw ([listof Rect] -> Scene) that draws all the Rects into an empty-scene, size (SW by SH). Use foldl. Hint: Fill in the general contract of foldl with specific "types" (Rect and Scene), then design a local function to match.

Finally: Now, as a final step, use this code to finish off the World simulation. Drag your mouse on the screen to see what happens!!

;; new-rect : Number Number -> Rect
;; Create a new Rect at the given point
(define (new-rect x y)
  (make-rect (make-posn x y)
             (make-posn (- (random 14) 7) (- (random 10)))
             (cond [(= (random 2) 0) "red"]
                   [else "orange"])))

;; tick : World -> World
;; Make updates to the world... gravity, movement, and filter
(define (tick lob)
  (only-on-screen (move (gravity lob))))

;; mouse : World Number Number String -> World
;; On drag, create random Rects
(define (mouse lob x y me)
  (cond [(string=? me "drag") (cons (new-rect x y) lob)]
        [else lob]))

(big-bang empty
          (on-tick tick)
          (on-mouse mouse)
          (on-draw draw))

If you finish early, try having the rectangles bounce when they reach the bottom, or when they collide with each other!

Enjoy!