Fundamentals of Computer Science I

Lab 6 - Abstraction and natural number recursion

Purpose In this lab we will practice recognizing similarities in function definitions and in data definitions and how to avoid them. This lab also has some fun with natural number recursion.

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

---

Abstraction

Sometimes when we solve problems, we find that the solution to one problem looks a lot like the solution to another one. Check out the following functions and data definition. From now on we will leave out the definition for lists, and use the [List-of X] notation.

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

  ;; lon-add2 : [List-of Number] -> [List-of 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 : [List-of Number] -> [List-of 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.

• 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.
• Rewrite 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.

Try another:

  ;; A [List-of String] is one of
  ;;  -- empty
  ;;  -- (cons String [List-of String])

• Write a function named starts-with-cat that consumes a [List-of String] and constructs a list of those strings that start with "cat".
• Write a function named starts-with-dog that consumes a [List-of String] and constructs a list of those strings that start with "dog".
• Write a function named starts-with that abstracts both of the functions above, taking an extra argument, which is the substring to be found in each element.
• Rewrite both starts-with-cat and starts-with-dog using your more general function, and write a few tests for each to be sure they work as expected.

---

Recursion over natural numbers

A recursive data structure we use very often in programming is the collection of natural numbers:

  ;; A Nat (natural number) is one of:
  ;;  - 0
  ;;  - (add1 Nat)
  ;;
  ;; 0 predicate: zero?
  ;;
  ;; (add1 n) predicate: positive?
  ;; (add1 n) accessor:  sub1

1. What is the template for Nat?

In the following exercises we will redefine some built-in arithmetic functions to get practice writing recursive functions over Nats, so don't simply reuse the built-in functions.

1. Design a function nat-even? that returns true if the given Nat is even.

   You may only use sub1 (and possibly not). E.g., do not use even?, odd?, modulo, etc.

2. Design a function double that doubles the given Nat. Again, you may only use add1 and sub1 (and double of course).
3. Design a function down-from that takes a Nat n and returns the list of Nats counting down from n. For example, (down-from 3) = (list 3 2 1 0).
4. Design a function repeat that takes a Nat n and a String s and returns a list that repeats s n times. For example, (repeat "buffalo" 8) = (list "buffalo" "buffalo" "buffalo" "buffalo" "buffalo" "buffalo" "buffalo" "buffalo"). Do not use make-list! (though it's good to know about)
5. Design a function nat+ that takes two Nats and computes their sum. (Use recursion, not the built-in + function.)
6. Design a function nat* that takes two Nats and computes their product. (Again use recursion, not the built-in * function, though you may use your nat+ now.)
7. Challenge: Design a function sqware that squares the given Nat (Note the intended name misspelling!), WITHOUT using nat*! You may use add1, sub1, double, and nat+ (and sqware of course).

---

Concentric rings in the World

Some basic setup:

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

  (define width 400)
  (define height 400)

In this animation, a World is a collection of Rings, each of which has a size and a location.

  ; A World is a [listof Ring]

  ; A Ring is a (make-ring Nat Posn)
  (define-struct ring (size center))

1. Design a grow-ring function that increases a Ring's size by 1.
2. Design a little draw-ring function that takes a Nat r as input and simply returns an image of a circle with radius r. (We'll make this more interesting later.)
3. Design a place-ring function that draws a Ring into the given Scene at the Ring's location. (Use draw-ring here so that we can modify it later to change the animation.)
4. Design a draw function that renders a World as a Scene by drawing all the Rings in their correct locations.
5. Design a mouse function that, when the mouse is clicked, adds a 0-size Ring to the World at the location of the click.
6. Design a tick function that grows all the Rings in the World using grow-ring.

Put it all together and see what you get:

  (big-bang empty
            (on-tick tick .25)
            (to-draw draw)
            (on-mouse mouse))

7. Now let's redesign the draw-ring : Nat -> Image function. Instead of making an image of a solid circle, let's make concentric rings of many circles. We can achieve this by overlaying many circles of increasing sizes:
   (overlay ) =
   Natural number recursion should serve you well here…