Functions

Some Simple Programs

In the following, we shall explore some simple programs to get used to Haskell as well as the environment in which we are working:

MyAdd

One of the most useful mathematical operations is undoubtedly the addition and here is a little program that defines "myadd" - my own definition of addition which of course does not differ from what we know as addition: It uses the same program structure as the program Pythagoras and also the Hello World. Note that we have defined a function called myadd inside the module Main and then a variable z to hold the result which we print out.

module Main where

myadd a b = a + b

main :: IO ()
main = do let z = myadd 5 3
          putStrLn $ "The result is: " ++ show z


Exercises:

1. Try this program in your Haskell IDE and then edit it so that instead of addition, it does subtraction ,multiplication and division.
2. Save each as a separate program in your folder. For each add it a comment as the first line just stating the file name and what the program does.
3. make a copy of each of the programs and for each arrange that instead of the parameters of the function being supplied at compile time that they are supplied at run time. Yoou may need to make reference to the program "2 plus 2" for this.

Have fun!


Factorial n


From our high school mathematics, we may be familiar with the factorial of a number n say (written n!). We know that

n! = n . (n-1).(n-2) ...3.2.1

So for instance 3! = 3.2.1 and 30! = 30.29.28....3.2.1

We can always visualise an abstraction better if we use concrete examples and also simple examples too. Now to be able to code this we see that

n! = n.(n-1)!

This gives us an idea! The problem is: is this idea supported in the programming language? In Haskell it is.  The idea of using a function in its own definition is called recursion and Haskell can handle this so let's see how we may be able to do it:

module Main
    where

fac 0 = 1
fac n = n * fac (n-1)

main = print (fac  3)


Exercises

1. Try this. What result did Haskell provide? Does this match your expectations?
2. Again, arrange for the parameter to be entered at run time from the keyboard.
3. Create a table of "test" values (about five) and run your program for each of these values while hand computing the answers. Compare. What does this tell you about your code?

Note: An important facet in programming is testing your code. While you make every effort to program correctly, your program must be tested before being put into production. As a rule, you should select your test data so that it provides some indication of the operation of your program both under normal input as well as input which would test its limiting conditions.


Multiplication (Recursive addition)


It does not have to be a complicated problem for us to apply recursion. Consider the following multiplication done by using a recursive addition:

module Main where

mult a 1 = a
mult a b = a + mult a b-1

main :: IO ()
main = do let z = mult 5 3
          putStrLn $ "The result is: " ++ show z

Exercise

1. Run this program.
2. Test it out with several parameters of your choice.

Fibonacci Sequence

You may have heard of the Fibonacci Sequence. This is a sequence of numbers as follows:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The first and second numbers are both equal to 1 The next number is found by adding up the two numbers before it.

• The 2 is found by adding the two numbers before it (1+1)
• Similarly, the 3 is found by adding the two numbers before it (1+2),
• And the 5 is (2+3),
• and so on!

So what is the 10th number in the sequence?

We can set Haskell to the task as follows:

module Main
    where

fib 1 = 1
fib 2 = 1
fib n = fib (n - 1) + fib (n-2)

main :: IO ()
main = print (fib 10)


Exercise

1. Run this program. What is the result?
2. Try hand computing the fib (10) and see how your result matches with the computer generated result.
3. Now we feel confident we can predict the 20th number. What is it?
4. Try fib(30), fib (40) and fib (50)

Have fun!

The output of the previous programs would probably look like:

To make adjustments to the code which is already loaded you can use the built-in text editor:

You may realise that the output of the previous program is deficient in some respect. What is it? You may also have realised that it took some time to compute fib (40). Were you able to do fib(50)?

What if you were doing some research into Fibonacci Numbers for a mathematical project and you had to compute fib(1000)? This computational complexity is hat you would eventually have to be able to reduce by using smart algorithms. We cannot afford to tie up the CPU for such a long time and especially if you are in a commercial environment where you are paying for CPU time. Fortunately Haskell is a lazy language (it only computes what it really has to) so we can use this to our advantage.


Exercise

1. Arrange for a user prompt to enter the required parameter.
2. Create a table showing the parameters and the time taken for the computation
3. draw a rough sketch showing the increase in time for parameters of 5, 10, 15, 20, 25, 30,..50

Have fun!


Multiple of 3 and 5


Consider the following problem which was one of the problems posed in Project Euler:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

As simple solution from elementary set theory would be to get the sum of all multiples of 3 and the sum of all multiples of 5 and then subtract those that are multiples of both 3 and 5 as we would have counted this set in twice.  Try this for the same problem up to say a limit of 20:

multiples of 3 = {3, 6, 9, 12, 15, 18}
multiples of 5 ={5, 10, 15}
multiples of 3 and 5 = {15}

sum of multiples of 3 = 63
sum of multiples of 5 = 30
sum of multiples of 3 and 5 = 15

Hence sum of multiples of 3 and 5 less than 20 = 63 + 30 - 15 = 78

We can make Haskell work this out for us as in the following:

Prelude> sum [n | n <- [1..20-1], n `mod` 5 == 0 || n `mod` 3 == 0]
78
Prelude> 

and using this we can solve the problem in the Project Euler easily with

Prelude> sum [n | n <- [1..1000-1], n `mod` 5 == 0 || n `mod` 3 == 0]

The Project Euler (https://projecteuler.net/about) is a great source of problems to sharpen your problem solving skills. Not all the problems will be quite as easy as the one shown but you will get hooked on problem solving and the problems are challenging! Try it!


Even Fibonacci Numbers


Try sussing out a plan by hand for the solution of the second problem in Project Euler.

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.



Euclid's GCD Algorithm


Another problem usually tacked early in a course in programming is Euclid's GCD algorithm. The problem context can be gleaned from the Cut-the-Knot website: http://www.cut-the-knot.org/blue/Euclid.shtml. The idea is that the GCD of two numbers, represented by

gcd (25, 15) = 5  so 5 is the highest number that divides into both 15 and 25.

The algorithm computes the Greatest Common Divisor (GCD) of two integers.

We have seen that the algorithm works basically as:

gcd (x, y) = gcd (y, remainder of x/y) y > 0

gcd (x, y) = x, y = 0

Where both x and y are non-negative integers.

Testing:

gcd (x, y)	gcd (y, x%y)	y >0	Output
gcd (15, 10)	gcd (10, 5)	true
gcd(10, 5)	gcd (5, 0)	true
gcd(5,0)		false	5

The Haskell program to produce the solution is:


module Main where

mygcd a 0 = a
mygcd a b = mygcd b (a `mod` b)

main :: IO ()
main = do let z = mygcd 15 25
          putStrLn $ "The gcd of 15 and 25 is: " ++ show z


This is a fairly complicated set of code and so what we should do as part of the testing process is do a dry run of the code. In the dry run, we will select a  set of test data and follow the values assigned to the various variable locations.


Dry Run

let n = 34

let m = 20

32 = 1.20 + 12

20 = 1.12 + 8

12 = 1.8 + 4

8 = 2.4 + 0

Thus, gcd (34, 20) = 2

• Can you describe this algorithm in some way that would make it clearer?

Observe that while the remainder is non-zero, move the m number to where the n number is and look for divisors of the remainder. The scenario is somewhat clearer when we lay it out as follows:

temp	n	m	n % m
	34	20	14
34	20	14	6
20	14	6	2
14	6	2	0

Exercise

1. Run this program using several sets of test data.
2. How do the results of the run compare with your own computations?

Have fun!