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 (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.
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.
lon-add2
and lon-add5
using your more general function, and write a few
tests for each to be sure they work as expected.
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
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.
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.
double
that doubles the given Nat
. Again, you may only use add1
and sub1
(and double
of course).
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)
.
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)
nat+
that takes two Nat
s and computes their sum. (Use recursion, not the
built-in +
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.)
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).
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))
grow-ring
function that increases a Ring
's size by 1.
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.)
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.)
draw
function that renders a World
as a Scene
by drawing all the
Ring
s in their correct locations.
mouse
function that, when the mouse is
clicked, adds a 0-size Ring
to the World
at the location of the click.
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))
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
)
=