# Lab 9 Honors: Accumulators and Generative Recursion

Remember
• Work in Pairs
• Change roles often
• Follow the design recipe and/or the abstraction recipe

## 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
(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 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 `Posn`s and converts it into a relative list of `Posn`s. 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 `Posn`s 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 `Posn`s back into a normal list of `Posn`s.

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)
scn))

;; 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, `power.fast`, 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 (power.fast 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 `Dir`s 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))
```

### Onward...

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:

• If `iter` is 0, then leave the list alone
• Otherwise, return a new list modified as follows:
1. Rotate all the `Dir`s from the old list counter-clockwise
2. Reverse the rotated list (remember `(reverse ...)`?)
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`

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.