Lab 5h 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

When we solve problems, we sometimes 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? Since these functions are almost identical you are hopefully asking "Why would you do that?!".

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

Exercise 2 Rewrite both lon-add2 and lon-add5 using your more general function. Write a few tests for each to be sure they work as expected.

Exercise 3 Design a function named starts-with-cat that consumes a [List-of String] and constructs a list of those strings that start with "cat". For example,

> (starts-with-cat (list "oboe" "cataract" "ox" "catharsis"))

(list "cataract" "catharsis")

Exercise 4 Design Write a function named starts-with-dog that consumes a [List-of String] and constructs a list of those strings that start with "dog".

Exercise 5 Design 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. Note to avoid "index out of range" errors you might want to ensure the prefix is shorter than the string you are checking against.

Rewrite both starts-with-cat and starts-with-dog using your more general function. 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, or natural number, is one of:

;  - 0

;  - (add1 Nat)

;

; The predicate for 0 is: zero?

;

; The predicate for (add1 n): positive?

; The selector for (add1 n): sub1

Exercise 6 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.

Exercise 7 Design a function nat-even? that returns true if the given Nat is even. Use only sub1, zero?, nat-even? itself, and possibly not. Do not use even?, odd?, modulo, etc.

Exercise 8 Design a function double that doubles the given Nat. Again, you may only use add1 and sub1, and of course double.

Exercise 9 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)

Exercise 11 Design a function nat+ that takes two Nats and computes their sum. Use recursion instead of the built-in + function.

Exercise 12 Design a function nat* that takes two Nats and computes their product. Again, use recursion instead of the built-in * function, though consider making use of nat+.

Exercise 13 Challenge: Design a function nat-square that squares the given Nat, but don’t use nat*! You may use add1, sub1, double, nat+, and of course nat-square.

Concentric rings in the World

Let’s build a world where clicking our mouse results in ever-growing rings to be drawn. Here is some basic setup:

(require 2htdp/image)

(require 2htdp/universe)

(define width 400)

(define height 400)

(define-struct ring (size center))

; A Ring is a (make-ring Nat Posn)

; where size is the ring's radius

;       center is the x,y coordinate of the ring's center

(define ring1 (make-ring 0

(make-posn 50 50)))

(define ring2 (make-ring (add1 0)

(make-posn 150 0)))

(define ring3 (make-ring (add1 (add1 0))

(make-posn 0 75)))

; A World is a [List-of Ring]

Exercise 14 Design a grow-ring function that increases a Ring’s size by one.

Exercise 15 Design a 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.

Exercise 16 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.

Exercise 18 Design a mouse function that, when the mouse is clicked, adds a 0-size Ring to the World at the location of the click.

Exercise 19 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 0.25)

(to-draw draw)

(on-mouse mouse))

Exercise 20 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...