# CS2500 Lab 7: Abstraction and 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 `[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
(cond [(empty? lon) empty]
[else (cons (+ (first lon) 2)

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

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

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.

Make sure you follow the recipe for abstraction.
1. 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.

## 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
;
; 0 predicate: zero?
;
```
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 `Nat`s, 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.

1. Design a function `double` that doubles the given `Nat`. Again, you may only use `add1` and `sub1` (and `double` of course).
1. Design a function `down-from` that takes a `Nat` `n` and returns the list of `Nat`s counting down from `n`. For example, ```(down-from 3) = (list 3 2 1 0)```.
1. 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)
1. Design a function `nat+` that takes two `Nat`s and computes their sum. (Use recursion, not the built-in `+` function.)
1. Design a function `nat*` that takes two `Nat`s and computes their product. (Again use recursion, not the built-in `*` function, though you may use your `nat+` now.)
1. 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 `Ring`s, 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.
1. 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.)
1. 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.)
1. Design a `draw` function that renders a `World` as a `Scene` by drawing all the `Ring`s in their correct locations.
1. Design a `mouse` function that, when the mouse is clicked, adds a 0-size `Ring` to the `World` at the location of the click.
1. Design a `tick` function that grows all the `Ring`s 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))
```
1. 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…