Introduction to Functional Programming

The aim of this exercise is to help you get started using the functional language Haskell, using the interactive implementation called Hugs. The best way to learn how to use Haskell is by doing it, so it is very important that you work through the exercise.

 

Getting Started

 

Start Hugs by clicking its icon, which you will find in the Start menu. You should see a window with some menus along the top, some buttons along the left edge, and an interactive session in the main body.After some preliminary information, it should say

 

Type :? for help

Prelude>

 

Hugs is just like a calculator; it simply evaluates any expression that is entered.For example, type 2*3 after the > prompt, and press Return.Hugs will respond with the result:

 

Prelude> 2*3

6 :: Int

(11 reductions, 9 cells)

Prelude>

 

This means that the value of the expression is 6 and the type of the expression is Int.Hugs also gives you a rough idea of the computation time required (number of reductions) and the amount of memory used (number of cells).

 

Hugs also has some commands, which always begin with a : (colon) character. Type in :?which is the command to display the list of commands and you will see a list of all the commands that Hugs provides. Whenever you forget a Hugs command you can use :? to get the full list.

 

Basic Expressions and Types

 

Types are extremely important in functional programming. You should always think about both the value and the type of every expression. The basic types include Int, Integer, Float, Double, Char and Bool. You are given below a number of examples of simple expressions. For each one, try to predict the value of the expression, and then try it out using Hugs. Can you guess what the difference is between the types Int and Integer?

 

Integers

 

2*3

4+5*6+7

5 `div` 2

5 `mod` 2

2^3

2^40

2^40 :: Integer

2^5000 :: Integer

 

Floating Point

 

2.5+ 3.1

10 * sqrt 9

 

Booleans

 

2<3

2+2 == 4

2 <= 3 && 3 <= 10

5<6 || 8>2

False && True

not (3==4)

 

Characters

 

`a` < `b`

isUpper `b`

isLower `b`

 

Lists

 

[1,2,3] ++ [4,5,6]

3 : [5,9,2]

2 : [1,8]

7 : []

length [`a`, `b`, `c`]

[3..8]

[1..20]

[1,3..20]

sum [1,3,10]

sum [1..5]

[x+x|x<-[1..10]]

 

Program Files

 

We can save some Haskell definitions in a file, and load it into Hugs; this is easier than typing it in every time you want to use it. The following three lines define a simple function named sqr, which takes an Int number and returns its square. The first line is a comment because it begins with --. The second line declares the type; it says that sqr takes an Int argument and returns an Int result. The third line says that when sqr is applied to a value x, it returns x*x.

 

-- sqr x -- returns the square of x

sqr :: Int -> Int

sqr x = x*x

 

Enter these three lines into a file.Save the file in a suitable place (for example, in your working FP directory), and give it the name square.hs .You can click Text Editor (on the Edit menu), and itís also possible to start any editor you like separately.

 

You should then use the Module Manager (on the File menu) to tell Hugs which file(s) are in your program.(If you want to control which directories Hugs will look in for your files, you can set this using the Options menu.)Now you can load the files by using Reload (File menu). Notice that there are also icons for the most common commands, include reloading.

 

Now that you have loaded the file square.hs you can test it by evaluating the following expressions:

 

sqr 2

2 + sqr 5

 

Now go back into the text editor and add a new definition for the cube function (this should be very similar to the sqr function!).Save the file, reload and test your cube function.

 

Errors

 

Next let`s see what happens when there is an error in your program. First add the following definition to your file:

 

mistake1 :: Int -> Int

mistake1 x = 2 +* x

 

This is a syntax error, because +* isnít a valid operator.Hugs will give you a syntax error message. Next, remove the definition of mistake1 and put in the following:

 

mistake2 :: Int -> String

mistake2 x = x+1

 

This time there is a type error, because the first line says that the function receives an Int and returns a String, but actually it returns an Int.The Hugs interpreter checks for syntax errors and type errors before it attempts to execute your program.

 

Sometimes you will encounter runtime errors.Try evaluating the following two expressions:

 

1/0

[1..]

 

The first should give a runtime error message because of the division by 0. The second is a very short program that counts up from one.This is an infinite loop, and you can interrupt it by clicking the Stop icon.

 

More Small Programs

 

The following problems are all small, and can be solved with just a few lines of Haskell.In every case give the type of the function.

 

1.      Define a function max4 that takes four (Int) numbers and returns the maximum.

 

2.      Define a function leap which returns True if its argument is a leap year.

 

3.      Write a function factorial that takes an Int argument and returns its factorial.For example, factorial 5 is 1*2*3*4*5, and factorial 0 is 1.

 

4.      Write a function oddsum that takes an Int argument and returns the sum of the odd numbers from 1 up to that number. For example, oddsum 10 should return 1+3+5+7+9 = 25.

 

5.      Write a function occurs which returns the number of occurrences of the character `e` in a given string.Then generalize the function to return the number of occurrences of a given character in a given string.

 

6.      Write a function to sort a list of Int (ascending order). What algorithm are you using?

 

7.      Write a function to merge two sorted lists (ascending order) of Int, to produce a sorted list.

 

8.      Write a function to insert an Int into an ordered list (ascending), with no duplicates.

 

9.      Write a function to compare pairs of Int in lexicographic ordering. E.g. (1,2) is less than (3,5); (3,4) is less than (3,5), (5,2) is not less than (4,5). Since compare is the name of a function already in the standard prelude, you must use a different name for your function.

 

10.  Write a function which takes a list of firstnames, a list of surnames, and produces a single string of (compound) names with a space between each first and surname, a comma between each (compound) name, and the list terminates with a full stop. E.g. if the input is: [``Freddy``,``Tony``] and [``Mercury``, ``Blair``], then the output is ``Freddy Mercury, Tony Blair.`` Be careful with how you place commas! Also, any unmatched first names or surnames are excluded.

 

 

NOTE: You are required to complete this assignment and you should demonstrate your programs to your tutor during the lab.