Assignment 1: Numeric Haskell

Due: 5:00pm, Friday, August 31. Value: 30 pts.

Develop and submit Haskell functions to solve the problems below. Feel free to develop additional “helper functions.”

You can test your code lab using the ghci command, which is already installed in the Linux lab; if you want to install it on another computer, you might try installing The Haskell Platform. To use ghci, first enter your function definitions into a text file, which we'll imagine you've named assn1.hs. Then open a Linux terminal and enter the command “ghci”. At the ghci prompt, you can load your text file using a command such as “:load assn1.hs”. From there you can then type an expression using one of your functions to test whether it works as you expect. If you develop the file further without exiting ghci, you can load the revised version by typing “:reload” (after ensuring the file is saved!) so that it begins using the newer version instead.

Problem 1. Mandelbrot set

The Mandelbrot set (pictured right) is a popular fractal that lies within the two-dimensional plane. A point (cr, ci) is in the Mandelbrot set (and colored black in the picture) if the following algorithm never terminates.

zr, zi ← 0, 0
while zr² + zi² < 4:
   zr, zi ← zr² − zi² + cr, 2 zr zi + ci

Write a function mandelIters that takes two parameters naming a point (cr, ci) and returns the number of iterations that the above pseudocode takes — or 10 if it requires more than 10 iterations. For instance, mandelIters 0.6 0.1 should return 4 since in this case the above pseudocode updates (zr, zc) four times: starting from (0, 0), it becomes (0.6, 0.1) after the first iteration, then (0.95, 0.22), then (1.45, 0.52), then (2.45, 1.61), at which point the loop stops.

To help you test, you can see what my JavaScript solution computes by clicking the image at right or entering the coordinates of a point below. A few reasonable points to try: (0.4, 0), (0.1, 0.8), (0.25, 0.5), (−1.3, 0).

Click image or enter point: cr = , ci =

(To provide a negative value as a parameter, you need to enclose it in parentheses so that Haskell knows that you don't mean to do subtraction. Thus, you'd write “mandelIters (-1.3) 0” to perform the final suggested test.)

Problem 2. Bisection method

The bisection method is an algorithm for finding the zero of a function — that is, given a function f we want to find a value for x for which f(x) is 0.

For the bisection method, we're initially given a continuous function f and two ends of an interval a and b for which f(a) < 0 and f(b) > 0. The bisection method repeatedly looks at the midpoint between a and b, evaluates f at that midpoint, and based on this chooses the half-interval that still crosses the x-axis. It stops when the interval is small (say, |a − b| < 10−4).

For example, if our function is f(x) = x² −5, we might begin with the interval (0, 4) since f(0) = −5 < 0 and f(4) = 11 > 0. The midpoint of our interval (0, 4) is 2; because f(2) = −1 < 0, we restrict our interval to (2, 4). The midpoint of this interval (2, 4) is 3; because f(3) = 4 > 0, we restrict our interval to (2, 3). The midpoint of this interval (2, 3) is 2.5; because f(2.5) = 2.25 > 0, we restrict our interval to (2, 2.5). And so we continue, always making our interval narrower until it is very small (gradually narrowing into the zero at √5).

Write a function findZero that applies the bisection method given a function and the two initial endpoints. The function's type is as follows.

findZero :: (Double -> Double) -> Double -> Double -> Double

One test for the function is to enter “findZero (\x -> x * x - 5) 0 3” and seeing whether the solution is close to √5 ≈ 2.236068.

You should submit your solutions in a single text file using the Moodle course page. (Submission via Moodle is new to me, so please be understanding if there are problems with how it is set up.)