Exercise 1 Design the function power, which computes the first number to the power of the second number using multiplication (do NOT use expt because it makes the problem trivial).

; power : Nat Nat -> Nat

; Compute n^m using '*'

(define (power n m) ...)

(check-expect (power 2 5) 32)

Exercise 2 Now, design a new function, power-fast which uses a method of repeated squaring to calculate the answer to the same problem. The basic rules of repeated squaring are: 1. x^(2y+1)=(x^(2y))*x 2. x^(2y)=(x^y)*(x^y)

(define res1 (time (power 2 100000)))

(define res2 (time (power-fast 2 100000)))

; digit->string: Nat -> String

; Turn a single digit number into a single char string

(define (digit->string n)

(string (integer->char (+ 48 n))))

(check-expect (digit->string 5) "5")

(check-expect (digit->string 0) "0")

Exercise 3 Design the function num->string that returns the string representation of a natural number. What is the base case for this function? What can we do to get from one digit to the next?

(check-expect (num->string 0) "0")

(check-expect (num->string 5) "5")

(check-expect (num->string 1234) "1234")

(check-expect (num->string 4321) "4321")

Exercise 4 Design the function, rotate-dir, that rotates a given Dir 90 degrees counter-clockwise (rotate to the left). What are the four cases of Dir and what should you return?

Exercise 5 Design the function, rotate-dirs, that rotates all the Dirs in a [List-of Dir] counter-clockwise. What loop function can you use?

Exercise 6 Design the function, move-posn, that returns a Posn that is the result of moving the given x and y in the given Direction, by the given amount.

; move-posn : Number Number Dir Number -> Posn

; Move the x and y in the given direction by the given amount

(define (move-posn x y dir amt) ...)

Exercise 7 Design the function, draw-dirs, that draws lines given a list of directions (in order) starting at the given x and y onto the given image.

; draw-dirs : [List-of Dir] Number Number Image -> Image

; Draw lines following the given directions starting at (x,y) into

;   the given Image (any color you choose).

; Screen Size...

(define W 400)

(define H 400)

; Draw wrapper

(define (draw w)

(local ((define lst (reverse w)))

(draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H))))

; Key Handler

(define (key w ke)

(cond [(key=? ke "up") (cons 'up w)]

[(key=? ke "down") (cons 'down w)]

[(key=? ke "left") (cons 'left w)]

[(key=? ke "right") (cons 'right w)]

[(key=? ke "r") (rotate-dirs w)]

[else w]))

(big-bang '()

(to-draw draw)

(on-key key))

• If iter is 0, then leave the list alone.

• Otherwise, return a new list modified as follows:

  1. Rotate all the Dirs from the old list counter-clockwise.

  2. Reverse the rotated list.

  3. Append the new reversed/rotated list on the end of the old list.

  4. Recurse on the new list, and with one less iter.

Exercise 8 Design a function, jurassic, which implements the algorithm above. You can use local to define each step separately so that it will be clear that your function follows the specification.

; jurassic: [List-of Dir] Number -> [List-of Dir]

; Compute the next iteration of the Jurassic Fractal, given a [List-of Dir]

;   and the number of iterations left.

(define (jurassic lod iter) ...)

(check-expect (jurassic '(down) 0) '(down))

(check-expect (jurassic '(down) 1) '(down right))

(check-expect (jurassic '(down) 2) '(down right up right))

(check-expect (jurassic '(down) 3) '(down right up right up left up right))

; draw : World -> Image

(define (draw w)

(local [(define lst (jurassic '(down) w))]

(draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H))))

; key : World KeyEvent -> World

(define (key w ke)

(cond [(key=? ke "up") (add1 w)]

[(and (key=? ke "down") (> w 1))

(sub1 w)]

[else w]))

; Let's make this fractal!

(big-bang 0

(to-draw draw)

(on-key key))

Exercise 9 Quickly write a "follow the template" recursive function definition of sum.

Exercise 10 Now write a second definition of sum using DrRacket’s foldr loop function(s).

Exercise 11 Transform your recursive definition of sum into an accumulator style function. You will need a local helper with an extra argument to "accumulate" the sum-so-far.

Exercise 12 Quickly write a "follow the template" recursive function definition of product.

Exercise 13 Now write a second definition of product using DrRacket’s foldr loop function(s).

Exercise 14 Transform your recursive definition of product into an accumulator style function. You will need a local helper with an extra argument to "accumulate" the product-so-far.

Exercise 15 Design a function operate-through which takes a [List-of X] and an [X X -> X] function. This function should produce a [List-of X] where the first element is the same as in the original list, the second element is the operation applied to the first element and the second element of the original list, and so on. In other words, if you pass in the list (list x1 x2 x3 x4) and the operation op you should get back the list (list x1 (op x1 x2) (op (op x1 x2) x3) (op (op (op x1 x2) x3) x4)). Here are some tests:

(check-expect (operate-through (list 1 2 3 4) +)

(list 1 3 6 10))

(check-expect (operate-through (list true false true) and)

(list true false false))

(check-expect (operate-through (list "we" "are" "groot") string-append)

(list "we" "weare" "wearegroot"))