# Functional Programming and Intelligent Algorithms

## Tutorial 1.2: Recursion and Problem Solving

(Sist oppdatert: 1 January 2015)

### Overview

• Reading: Simon Thompson, Chapter 4 and 10.2
Comments on the relationship between binary operators (e.g. +) and functions in two arguments.

### Problem 1: Bisection Method

In this tutorial we shall implement the Bisection Algorithm which is a simple numerical approach to equation solving. Consider the following equation as an example

$0={x}^{5}+{x}^{4}·2+{x}^{2}·4+x-\mathrm{10}$

Let's not discuss whether a solution can be found analytically. We want to find some solution numerically. To facilitate discussion, we define a symbol $\mathrm{f\left(x\right)}$ for the right hand side, i.e.

$\mathrm{f\left(x\right)}={x}^{5}+{x}^{4}·2+{x}^{2}·4+x-\mathrm{10}$

A couple of observations are easy to make.

1. $\mathrm{f\left(-10\right)}<0$
2. $\mathrm{f\left(10\right)}>0$
3. $\mathrm{f\left(x\right)}$ is continuous

It follows from these three observations that $\mathrm{f\left(x\right)}$ has at least one root in the interval $\mathrm{-10}. Without considering the possibility of multiple roots, we want to find one such root.

You can look up the Bisection Method in most undergraduate introductions to calculus. Let $\mathrm{f\left(x\right)}$ be a continuous function and $\mathrm{\left(l,u\right)}$ an interval so that $\mathrm{f\left(l\right)}$ and $\mathrm{f\left(u\right)}$ have different sign; then $\mathrm{f\left(x\right)}$ has a zero in the interval $\mathrm{f\left(x\right)}$. The Bisection Method finds the midpoint $m$ in the interval $\mathrm{\left(l,u\right)}$. If $\mathrm{f\left(l\right)}$ and $\mathrm{f\left(m\right)}$ have different sign, then there must be a zero in the interval $\mathrm{\left(l,m\right)}$, and we use bisection recursively on this interval. Otherwise, we call it recursively on the interval $\mathrm{\left(m,u\right)}$.

1. Open your editor and create a new Haskell module for this problem. Choose an appropriate name for the module.
2. Implement the function $\mathrm{f\left(x\right)}$ described above in Haskell. The type description should be `f :: Double -> Double`
3. We are going to implement a `bisect` function, which can be used to find a zero of `f` with a call like this: `bisect (-10) 10` The arguments are resp. the lower and upper bound of the search interval and have type Double.
• Write the type signature of `bisect` into your module file.
4. The `bisect`function has to be a recursive function, so we need two cases. Use `l` and `u` to denote the bound of the search interval `(l,u)`.
Base case
If the difference `l-u` is very small, we can just take the average of `l` and `u` as the approximate solution. Write a guarded expression for the base case, e.g. `bisect u l | u-l < eps = ...` choose an appropriate value for `eps` and add a defintion after the equal sign.
Recursive case
If the search interval is larger, we split it in two, and find which half must contain a root. Then we recursively continue the search in the relevant half. The recursive call, with two different cases using guards, can look something like this. ``` bisect u l | fl*fm < 0 = bisect f l m | otherwise = bisect f m u where ... ``` You need to complete the `where` clause to define the midpoint `m` and the function values `fm` ($\mathrm{f\left(m\right)}$) and `fl` ($\mathrm{f\left(l\right)}$).
5. Start ghci and load the module that you have written.
6. Test your bisection function by finding the root of $\mathrm{f\left(x\right)}$ in the interval $\mathrm{\left(-10,10\right)}$. I.e. evaluate the following `bisect (-10) 10`
7. It will be useful to check that the result is reasonable. You probably have some software (spreadsheet, MatLab, python, gnuplot) where you can plot $\mathrm{f\left(x\right)}$ on the interval $\mathrm{\left(-10,10\right)}$ and check that the zero you find is (approximately) correct. Or you could evaluate the function on the x-point returned by `bisect` and check if you get approximately zero.

#### Refinement with higher-order functions

We are going to implement a `bisect` function, so that it can be used to find zeros of arbitrary continuous functions.

1. We want to change the `bisect` function so that it can be used like this `bisect f (-10) 10` The first argument is the function for which we want to find a zero, with type `Double -> Double`, making `bisect` a higher-order function. The other two arguments are as before.

1. What is a higher-order function?
2. Change the type signature of `bisect` into your module file.
2. Update the implementation of `bisect` to become a higher-order function.

1. Add the function argument `f` as the first argument on the right hand side of the definition?

When the symbol `f` is used as an argument, `f` on the right hand side will refer to the argument and not to the global definition. Thus no changes are required on the right hand side.

3. Test the revised bisection function by finding the root of $\mathrm{f\left(x\right)}$ in the interval $\mathrm{\left(-10,10\right)}$. I.e. evaluate the following `bisect f (-10) 10`

### Problem 2: More Pictures

Do Exercises 4.25-4.30 in Simon Thompson's book.

Hans Georg Schaathun / hasc@hials.no