Functional Programming and Intelligent Algorithms

Tutorial 4: Higher-Order Functions

Week 1: Getting started with Haskell

5 Tutorial 4: Higher-Order Functions

5.1 Worked example: The optimisation problem

In Tutorial 3, we implemented minimisation of a single pre-defined function f(x). It would be obviously, be better if we could use fmin on any function h(x). Then the function h needs to be an argument to the function.

First, let’s update the type decalaration, by adding a function parameter. The first argument must have the same type as f, i.e. Double -> Double. I.e. change the type declaration to fmin :: (Double > Double) > Double > Double
Secondly, we need to add the parameter in the definition, and every reference to f must be replaced by a reference to the parameter name h, as follows: fmin h x0 | x0  delta < low      = low 
          | x0 + delta > high     = high 
          | h (x0  delta) < h x0 = fmin h (x0  delta) 
          | h (x0 + delta) < h x0 = fmin h (x0 + delta) 
          | otherwise             = x0
Save the module and reload the module it in GHCi.
Test the function fmin f 0 Do you get the same answer as the first time?

5.2 Practice problem: The bisection algorithm

Now you have seen how to make fmin a higher-order function. Now you do the same to the bisect function, so that it can find zeros of arbitrary continuous functions.

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.

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

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.

Test the revised bisection function by finding the root of g(x) in the interval (10,10). I.e. evaluate the following bisect f (10) 10 Is the answer the same as before?

7th April 2017
Hans Georg Schaathun /