Lab 9 Honors: Accumulators and Generative Recursion


Part 1: Accumulators

You've probably read about them (accumulators) in the book right? If not have a quick look through it... not too long, because we have a lot of cool stuff to get through.

Accumulator style functions are those that (you guessed it) accumulate knowledge in recursive calls, rather than making "blind" structurally recursive calls (though accumulator style functions can also be, and usually are, structurally recursive).

Example: Here's an implementation of list length in both regular and accumulator style

      ;; length.reg : [Listof 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 : [Listof 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)
Notice that in order to keep the contracts the same, I used a local recursive function, rather than adding an argument to the main function.

So it begins...

    Consider the function sum that sums all the elements in a [Listof Number].
  1. Quickly write a "follow the template" recursive function definition of sum.
  2. Now write a second definition of sum using DrRacket's foldr or foldl loop function(s).
  3. Transform your recursive definition of sum into an accumulator style function. Hint you need a local helper with an extra argument to "accumulate" the sum-so-far.

    Lets do the same process for the function product that computes the product of all the elements in a [Listof Number].
  1. Quickly write a "follow the template" recursive function definition of product.
  2. Now write a second definition of product using DrRacket's foldr or foldl loop function(s).
  3. Transform your recursive definition of product into an accumulator style function.

  1. Design a function, absolute->relative, that takes a list of Posns and converts it into a relative list of Posns. In a relative list, each Posn is interpreted relative to the one that came before it, and the first Posn is interpreted relative to (0,0). In other words, return a new list of Posns that are adjusted so that they represent the change in position from the previous Posn in the list.

    Hint: what gets accumulated/remembered between recursive calls? How do you calculate the current element from it?

    Here's a few tests...

        ;; No Posns (nothing interesting)
        (check-expect (absolute->relative '()) '())
        ;; One Posn (still nothing interesting...)
        (check-expect (absolute->relative (list (make-posn 4 5)))
                      (list (make-posn 4 5)))
        ;; A bunch of Posns...
        (check-expect (absolute->relative 
                       (list (make-posn 1 6) (make-posn 20 13)
                             (make-posn 5 15) (make-posn 15 5)
                             (make-posn 20 7)))
                      (list (make-posn 1 6) (make-posn 19 7)
                            (make-posn -15 2) (make-posn 10 -10)
                            (make-posn 5 2)))
  2. Design a function, relative->absolute, that converts a relative list of Posns back into a normal list of Posns.

    Note: The two functions you've designed should have no effect when composed:

         (define a-lop (list (make-posn 5 7)
                             (make-posn 14 13)))
         (check-expect (relative->absolute (absolute->relative a-lop)) a-lop)

A bit of fun before we move on...

    Consider the program below... what does it do? (Hint... run it and find out)
         (require 2htdp/image)
         (require 2htdp/universe)
         ;; Width and Height of our Scene
         (define WIDTH 300)
         (define HEIGHT 300)
         ;; Basic empty scene
         (define base-scene (empty-scene WIDTH HEIGHT))
         ;; A World is a [Listof Posn]
         ;; put-dot : Scene Posn -> Scene
         ;; Put a single Dot into the Scene at the given Posn
         (define (put-dot scn p)
           (place-image (circle 3 "solid" "blue")
                        (posn-x p) (posn-y p)
         ;; draw-dots : World -> Scene
         ;; Draw the dots of the World (a list of Posn)
         (define (draw-dots ps)
           (cond [(empty? ps) base-scene]
                 [else (put-dot (draw-dots (rest ps)) (first ps))]))
         ;; mouse-click : World Number Number String -> World
         ;; Add a new Posn to the World if the mouse was clicked
         (define (mouse-event w x y what)
           (cond [(string=? what "button-down")
                  (cons (make-posn x y) w)]
                 [else w]))
         (big-bang '()
                   (to-draw draw-dots)
                   (on-mouse mouse-event))
  1. Transform draw-dots into accumulator style. Call the new function draw-dots-acc. What does your function accumulate? Use it in the big-bang to be sure it works right.
  2. Add a number/label to each dot by designing new functions, put-num-dot and draw-num-dots. Make sure draw-num-dots is in accumulator style, and use it instead of draw-dots-acc in the big-bang. See Image (2) below for an example of what we expect (after a few clicks).

    Hint: you'll need to text and number->string, but you already guessed that...

    If your numbers aren't in order, then fix them so they do not change as dots are added. You may need to modify the accumulator's starting value and its update expression.

  3. Design the function draw-lines, in accumulator style that draws lines between the dots. Hint: you'll also want to pass the previous point's coordinates (in addition to the accumulator) when you make your recursive call, since the image function line creates a line from (0,0) to the given x/y. See Image (3) for an example.
  4. Finally, design the function draw-num-lines that draws both lines and number/labels on the dots. See Image (4) for an example. This function doesn't have to be in accumulator style, but if you're working off your other function it probably will be.

Example Screen Shots:

(1) Original

(2) Just numbers

(3) Just lines

(4) All together

Part 2: Generative Recursion

We warm up with the power function that we've seen in class.
  1. Design the function, power, that computes the first number to the power of the second number, using multiplication (i.e., you cannot use expt).
          ;; power : Number Number -> Number
          ;; Compute n^m using '*'
          (define (power n m) ...)
          (check-expect (power 2 5) 32)
    Hint: This is just Nat recursion.
  2. Now write a new version,, that uses the method of repeated squaring. You've seen this before, but just to remind you, here are the basic rules:
    x2y+1 = x2y · x     and     x2y = xy · xy

If you want proof that the fast one is actually faster, try this code. The time expression form evaluates to the expression given, in addition to printing the amount of time DrRacket took to evaluate it.

     (define res1 (time (power 2 100000)))
     (define res2 (time ( 2 100000)))
If you don't notice a HUGE difference then you might be doing something twice when you don't need to (see local). Or, you might not always be dealing with whole numbers.

Readable numbers... without the help of DrRacket

Here's a bit of code that turns a single digit number into a single character string:
     ;; digit->string: Number -> 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")
  1. Design the function num->string, that returns the string representation of a number.

    Hint: this is kind of like Nat recursion, but rather than subtracting what do we do to get to the next digit? Another hint: the base case is anything less than 10, where you just return the converted digit->string.

    Here are some tests for you:
         (check-expect (num->string 0) "0")
         (check-expect (num->string 5) "5")
         (check-expect (num->string 1234) "1234")
         (check-expect (num->string 4321) "4321")

The Dragon Fractal...

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 start off building a simple line drawing program. Then we'll combine pieces into the fractal's (generative) recursion.

    First, a direction (Dir) is a Symbol, one of: 'left, 'right, 'up, or 'down
  1. Write 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?
         ;; rotate-dir : Dir -> Dir
         ;; Rotate the given direction to the 'left' (counter-clockwise)
         (define (rotate-dir dir) ...)
  2. Write the function, rotate-dirs, that rotates all the Dirs in a [Listof Dir] counter-clockwise. Hint: Which loop function can you use?
         ;; rotate-dirs : [Listof Dir] -> [Listof Dir]
  3. Write the function, move-posn, that returns a Posn that is the result of moving the given x and y in the given Dir-ection, the given amount, amt.
         ;; move-posn : Number Number Dir Number -> Posn
  4. Write the function, draw-dirs, that draws lines given a list of directions (in order) starting at the given x and y into the given scene.

    Hint: Use structural recursion here, and choose some constant amount for move-posn (say 5). You can use line to create the lines. You'll need a bit of an accumulator too.

         ;; draw-dirs : [Listof Dir] Number Number Scene -> Scene
         ;; Draw lines following the given directions starting at (x,y) into
         ;;   the given Scene (any color you choose).

Here's some interactive stuff to test your functions... use the arrow keys to create a path (a [Listof Dir]). You can hit r to rotate all the points to the left.
     ;; 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))


Now... We need to generate the fractal. Here's the pattern; the blue number is the number of iterations run.
The algorithm takes a [Listof Dir] and a Number that is the iterations left to be done. To start the algorithm off we will pass it the list '(down), and the number of iterations we want.

It goes like this:

  1. Write a function, jurassic, which implements the algorithm above. You can use local to define each step separately, then it will be clear that your function follows the specification.
         ;; jurassic: [Listof Dir] Number -> [Listof Dir]
         ;; Compute the next iteration of the Jurassic Fractal, given a [Listof 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))

Now remove (or comment out) the old big-bang code and replace it with this:

     (define (draw w)
       (local ((define lst (jurassic '(down) w)))
         (draw-dirs lst (/ W 2) (/ H 2) (empty-scene W H))))

     (define (key w ke)
       (cond [(key=? ke "up") (add1 w)]
             [(and (key=? ke "down") (> w 1))
              (sub1 w)]
             [else w]))

     (big-bang 0
               (to-draw draw)
               (on-key key))
Hit the up/down arrows to increase and decrease the number of iterations run.

If you're done early...

When drawing the directions (draw-dirs) try accumulating and changing the current color, or modifying the size of the lines to create interesting drawings.

If you're done really early...

Try doing the Koch Snowflake fractal... that one's pretty fun, and a nice challenge.