Lab 11 Dragon Fractal
Purpose: To practice the use of accumulators and generative recursion.
Harder Better Faster Stronger
Exercise 1 Design the function power, which takes in two natural numbers and computes the first number to the power of the second number using multiplication (follow the recursive template for a natural number).
Exercise 2 Design the 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:
X2Y = (XY)*(XY)
X2Y+1 = X*(X2Y)
Remember Who You Are
Exercise 3 Design the function my-foldl which works exactly like foldl. You may not use foldl to implement it.
Etch-a-Sketch
In this section of the lab we will create a simple line-drawing program. The program starts with a blank canvas and the user can draw lines of a fixed size by pressing the arrow keys.
Step 1: What stays the same?
For your convenience we have provided some constants to use below. You can modify them or add to them if you find that you need to keep track of something else.
(require 2htdp/image) (define WIDTH 600) (define HEIGHT 600) (define BACKGROUND (empty-scene WIDTH HEIGHT)) (define LINE-LENGTH 10) (define LINE-COLOR "black") (define START-POSITION (make-posn 200 200))
Step 2: What changes?
To keep track of what changes we will keep a list of all the directional keys the user has pressed. Here is a data definition for a direction:
; A Dir is one of: ; - "left" ; - "right" ; - "up" ; - "down" ; and represents one of the 4 possible directions
Exercise 4 Define the template for functions that take in a Dir.
Step 3: Which handlers do we need?
Exercise 5 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create. Keep in mind that we will need to use a list of Dirs as our world state.
Step 4: Design your handlers
We will start by designing the function that draws the lines in the given directions. However, let’s break this down into some simpler functions first:
Exercise 6 Design the function move-posn that takes a Posn, a Dir, and a Number and produces that position shifted by the given amount in the given direction. For example, (move-posn (make-posn 1 2) "left" 3) would produce (make-posn -2 2).
Exercise 7 Design the function draw-from-start, which takes a [List-of Dir], a Posn, and an Image. It then adds lines starting at the given position and going in each direction. Each line should start where the last one ended. You can use the pre-defined function add-line to add lines to an image. Note: You should not use a list abstraction for this problem.
Exercise 8 Use draw-from-start to design the function for your to-draw clause.
Now we need to design the on-key handler. When a user presses an arrow key it should add a direction to the end of the list of directions.
Exercise 9 Design the function for your on-key clause. When an arrow key is pressed, add the appropriate direction to the end of the list so far. When another key is pressed, nothing should happen.
Step 5: Put it all together!
Exercise 10 Design the function etch-a-sketch which runs your line-drawing program.
Stretch Goals: Generating Fractals
For the next part of the lab you will design functions to draw (and iterate) something called the dragon curve which is a fractal. Put simply, a fractal is just an image that is the same at various levels of detail. We will make use of the functions we wrote for our line-drawing program in order to develop this program.
Step 1: What stays the same?
We should be able to use the same constants as we had in our line-drawing program so there is nothing further we need to do for this step.
Step 2: What changes?
We will use a natural number to keep track of the number of iterations of the fractal to show. When someone presses the up arrow we will increase the number, and when someone presses the down arrow we will decrease the number (unless it is already zero). Since a NaturalNumber is atomic data there is no need for us to design any new data.
Step 3: Which handlers do we need?
Like our line-drawing program we will need a drawing function and a function that can handle keyboard inputs so that you can increase or decrease the number of iterations by pressing the arrow keys.
Step 4: Design your handlers
We will start by designing the function that draws the fractal. Remember that all we are given is the number of iterations. Therefore the first thing we need to do is find out what lines to draw.
Exercise 11 Design the function rotate-dir which takes a Dir and rotates it 90 degrees counter-clockwise.
Exercise 12 Design the function rotate-all-dirs which takes a [List-of Dir] and rotates every Dir in the given list 90 degrees counter-clockwise.
Exercise 13 Design the function generate-fractal-dirs which takes a natural number (representing the number of iterations left to draw) and a list of Dirs and performs the following algorithm:
If the number is zero, return the list unchanged.
Rotate every Dir in the input list
Reverse the list of rotated directions
Append this rotated/reversed list to the end of the input list
Recursively call the function with one less iteration
Exercise 14 Design the function for the to-draw clause which takes a natural number and draws that many iterations of the dragon fractal using the generate-fractal-dirs function and the drawing function from our line-drawing program. To start, you should give generate-fractal-dirs the initial list (list "down").
Exercise 15 Design the function for the on-key clause. Remember that your world state is a natural number. This number should increase by one if the up arrow key is pressed and decrease by one if the down arrow key is pressed. Otherwise nothing will happen.
Step 5: Put it all together!
Exercise 16 Design the function dragon-fractal which takes an initial number of iterations and runs the dragon fractal program. Play around with it but don’t be surprised if the program breaks after about 10 iterations (the image becomes too large so you may get something unexpected).