Purpose This lab is an introduction to generative recursion and accumulator style functions.
You may have read about generative recursion in the book, but if not, go take a look. Generative recursion is a type of programming which rearranges a problem into a series of smaller subproblems, which are then combined to find a solution. These sub-problems are often (but not always) the same kind of problem as the original, which means you can use recursion!
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)
; 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")
For the next part of the lab you will design functions to draw (and iterate) an interesting fractal design called the Dragon. This was used on the headings of chapters in the book Jurassic Park (if anyone is old enough to remember that...). We’ll start off by building a simple line drawing program. Then we’ll combine pieces into the fractal’s (generative) recursion.
; A Direction (Dir) is a Symbol and is one of: ; - 'left ; - 'right ; - 'up ; - 'down
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.
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:
Rotate all the Dirs from the old list counter-clockwise.
Reverse the rotated list.
Append the new reversed/rotated list on the end of the old list.
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))
Now you can hit the up or down arrows to increase or decrease the number of iterations run.
You’ve seen one use of accumulators in class, namely use of the list of "visited" nodes when implementing path?. An accumulator is an argument that summarizes the collected knowledge seen so far in a recursive function. For example, the implementation of list length in both regular and accumulator style is shown below.
; length.reg : [List-of X] -> Number (define (length.reg lst) (if (empty? lst) 0 (add1 (length.reg (rest lst))))) (check-expect (length.reg (list 1 2 3 4 5)) 5) ; length.acc : [List-of X] -> Number (define (length.acc lst) (local [(define (loop lst acc) (if (empty? lst) acc (loop (rest lst) (add1 acc))))] (loop lst 0))) (check-expect (length.acc (list 1 2 3 4 5)) 5)
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"))
Exercise 16 When drawing the directions in your draw-dirs function, try accumulating and changing the current color or modifying the size of the lines to create interesting drawings.
Exercise 17 Try making the Koch Snowflake fractal. This one’s a bit more of a challenge!