Declarative Programming I
Functional Programming in Haskell
Unassessed Exercises
Tony Field (Room 376)
Answer as many as you can at your own speed.
These exercises do NOT need to be submitted for marking.
Model answers to each set will be handed out in due course.
Functional Programming in Haskell
Unassessed Exercise Sheet 1: Expressions, Built-in Types and Prelude Introduction
All the problems on this sheet can be solved by typing expressions at the Hugs prompt:
Prelude> type your expression here and press RETURN
First read the laboratory notes provided, which introduces you to the Department’s computers and tells you how to start the Haskell (Hugs) system. As you do each question, read any accompanying notes carefully. Also, most importantly, make up your own problems and try them out too.
Note that an important objective of this first batch of problems is to introduce you to some of Haskell's built-in types and functions (Haskell's so-called prelude). Within Hugs, you can find out more about any known identifier, including types, functions, classes etc., by typing :info identifier (or use :i for short), e.g. :info +, :i Int etc. To get a list of all function names that are in scope at any time type :names (or :n).
You will probably not be able to complete these exercises in the two lab sessions allocated before Thursday's lectures, but don't panic! There are more questions here than you need, so skip over some of them once you've got the hang of it.
1.Type in and evaluate the following Haskell expressions:
(a)2 - 3 - 4
(b)2 - ( 3 - 4 )
Q: What does this tell you about the associativity of the Haskell ‘-’ operator?
Remark: a left-associative operator op implies that successive applications are bracketed from the left, so that a op b op c is evaluated as ( ( a op b ) op c ). For a right-associative operator, it would be evaluated as ( a op ( b op c ) ).
(c)100 `div` 4 `div` 5
(d)100 `div` ( 4 `div` 5 )
(e)2 ^ 3 ^ 2
Remark: div is the prefix integer division function (quotient function), as in div 12 5 which gives the answer 2. The back quotes in `div` turns the prefix function into an infix operator, as in 12 `div` 5 (try this out). Do not confuse back quotes with the forward quotes that are used to delimit characters. Note also that an infix operator can be turned into a prefix function by enclosing it in brackets. For example, the expression (+) 8 5 means the same as 8 + 5.
Q: What can you say about the associativity of the `div` and ^ operators?
(f)3 - 5 * 4
(g)2 ^ 2 * 3
(h)2 * 2 ^ 3
Q: What can you say about the relative precedence of the -, * and ^ operators?
Remark: An operator’s precedence is an integer in the range 0-9 which is used to determine the order in which multiple operator applications are evaluated. If op1 has a higher precedence (a higher number) than op2 then a op1 b op2 c evaluates to ( ( a op1 b ) op2 c ) and a op2 b op1 c evaluates to ( a op2 ( b op1 c ) ). We say that op1binds more tightly than op2, as with * and + respectively, for example. Experiment with the other Haskell operators.
(i)( 3 + 4 - 5 ) == ( 3 - 5 + 4 )
(j)ord 'a'
(k)chr ( ord 'b' - 1 )
(l)chr ( ord 'X' + ( ord 'a' - ord 'A' ) )
(m)'p' /= 'p'
(n)'h' <= 'u'
Remark: The alphabetic characters ‘a’, ‘A’, ‘b’, ‘B’ etc. are encoded by computers as numbers. The most commonly used numbering scheme is called the ASCII encoding. The ASCII code for a character c can be obtained by the Haskell function ord (for ordinal value). The inverse of ord is called chr. See the attached ASCII table and check it out by applying the ord function to various characters. The operators ==, /=, <, >, <=, >= also work on characters using the ASCII numeric representation in the obvious way, e.g. 'a' < 'b' gives True because
ord 'a' < ord 'b'.
(o)sqrt 2 ^ 2
(p)sqrt 2 ^ 2 – 2 (try also sqrt 2 ^ 2 == 2 )
(sqrt is a function that calculates the square root of a given number).
Q: What does this tell you about the relative precedence of prefix function application and infix function application?
Remark: (o) gives a rather unintuitive answer. The reason is that floating-point arithmetic (arithmetic with Floats and Doubles) is only an approximation to arithmetic with real numbers. Computers use a finite representation for what is, mathematically, an infinite and continuous object (the infinite real line). The associated arithmetic is therefore subject to artefacts such as rounding error (we don’t get exactly the right answer) and overflow (the answer is too big or too small for the computer to represent). To understand this fully you will have to wait until the lectures on computer arithmetic which will follow shortly in another course.
Finally, for practice, work out how Haskell brackets the following expressions and test your answers by typing in equivalent expressions with the brackets explicitly inserted. Note: the function truncate is a prefix function which rounds a floating point number (Float) down to the nearest Int, e.g. truncate 19.567 = 19; max and min respectively return the larger and smaller of two given numbers (works with Int, Integer, Float and Double types).
(q)not True || 5 < 6 `mod` truncate 2.8 ^ 2
(r)1 + sin 0.7 ^ 2 - sqrt 5 * 4
(s)cos 2 * pi ^ 2 >= 4 || sin pi < max 0.5 0.9
(t)2 ^ truncate pi ^ 2 < 0.8 & pi > sin 0.8
2.Using the Haskell operators div, mod and ord, where necessary, write expressions to find the values of the following:
(a)The last digit of the number 123
(b)The penultimate digit of the number 456
(c)The eighth lower-case letter of the alphabet (i.e. starting from ‘a’)
(d)The “middle” upper-case letter of the alphabet
(e)The minimum number of 13 gallon barrels needed to hold the entire contents of an 823 gallon vat
3.Using the minimum number of brackets as possible, write down expressions which evaluate to True iff:
(a)100 is exactly divisible by 10
(b)22 is even (do not use the built-in even function in Haskell!)
(c)The penultimate digit of 139 is different from the last digit of 55
(d)The letter ‘z’ is the 26th lower-case letter of the alphabet
(e)The letter ‘c’ is either the 1st or the 3rd lower-case letter of the alphabet
(f)The letter ‘b’ is neither the 1st nor the 3rd lower-case letter of the alphabet
(g)As for (e) but this time do not use the not operation
(h)100 lies between 50 and 200
(i)10 does not lie between 50 and 200
(j)As for (h) but do not use the not operation
4.All of the following expressions are syntactically correct, but some of them have some form of type error. For each, work out whether the expression is correctly typed or not. Where the type is incorrect work out how Haskell has implicitly bracketed the expressions.
(a)2 * 3 == 6
(b)6 == 2 * 3
(c)2 + 3 == 5
(d)not 2 * 3 == 10
(e)3 == 4 == True
(f)if True then False else True == True
(g)if 3 == 4 then ord 'a' else ord 'b'
(h)ord if 3 == 4 then 'a' else 'b' + 1
(i)8 > 2 ^ if 3 == 4 then 2 else 3 == False
Assuming that the expressions with incorrect types were a result of the programmer accidentally omitting parentheses, suggest where they might be added to make the types of the expressions correct. What types do these expressions now have?
5.Write a qualified expression using a let which finds the two roots of the equation
ax2 + bx + c = 0
using the formula
b (b2 4ac)
______
2a
in the case where a=1, b=4 and c=1.5. Write your expression in such a way that the term inside the square-root is computed only once and return the two roots in the form of a tuple.
6.Using `div` and `mod` write an expression which converts time (an integer called s, say), representing the number of seconds since midnight, into a triple of integers representing the number of (whole) hours, minutes and seconds since midnight. Use a let to perform the calculation for the specific case where s=8473.
7.A polar coordinate (r,) can be converted into cartesian coordinates using the fact that the x-axis displacement is r cos , and the y-axis displacement is r sin Write a let expression which converts the polar coordinate (1,/4) into cartesian coordinates represented by a pair of Floats.
Remark: Haskell allows you to match tuples in qualified expressions. As an example, in the same way that we can write let x = 5 in blah, which gives x the value 5 in expression blah we can also write let (x,y) = (5,6) in blah which simultaneously gives x the value 5 and y the value6. Alternatively, there are built-in functions called fst and snd which will respectively deliver the first and second elements of a given pair. Solve this problem using both approaches, i.e. using tuple matching and by explicit use of the so-called projectorsfst and snd.
8.The operators ==, /=, <, >, <=, >= also work on tuples. To see how, try the following:
(a)( 1, 2 ) < ( 1, 4 )
(b)( ( 4, 9 ), ( 3, 1 ) ) > ( ( 1, 10 ), ( 9, 4 ) )
(c)( 'a', 5, ( 3, 'b' ) ) < ( 'a', 5, ( 3, 'c' ) )
Remark: The ordering used by Haskell's comparison operators is lexicographical - it works from left to right just like the ordering used in a dictionary.
Functional Programming in Haskell
Unassessed Exercise Sheet 2: Functions
For each function you define enter its type as well. As an additional exercise, when you are happy that your function is correct, delete the type definition using the editor and then return to the Hugs system. The Hugs system will automatically work out (infer) the type of your function and you can check this by typing :type <fun> where <fun> is the name of your function. In some cases you may be surprised to see that the inferred type is different to the type you originally wrote down. You may be able to work out what its doing in these cases; if not the later lectures will help to explain.
1.Write a function adddigit of two arguments which will add a single-digit integer onto the right-hand end of an arbitrary-size integer. For example, adddigit123 4 should evaluate to 1234. Ignore the possibility of integer overflow.
2.Write a function convert which converts a temperature given in oC to the equivalent temperature in oF. (To convert from oF to oC the rule is to subtract 32 from the temperature in oF and then multiply the result by 5/9.)
3. Given the type synonym type Vertex = ( Float, Float ) write a function distance :: Vertex -> Vertex -> Float that will calculate the distance between two points, each represented as a Vertex. Using the distance function write a function
triArea :: Vertex -> Vertex -> Vertex -> Float that will calculate the area of the triangle formed by the three given vertices. Note that a triangle whose sides are of length a, b and c has an area given by where .
4.The factorial of a non-negative integer n is denoted as n! and defined as:
n (n-1) (n-2) (n-3) … 2 1
0! is defined to be 1. Write a function fact which defines the factorial of a non- negative integer. Ignore the possibility of integer overflow.
5.Write a function remainder which defines the remainder after integer division. Implement the division by repeated subtraction (i.e. do not use the predefined functions div and mod). Ignore the possibility of division by zero.
6.Write a function quotient which defines integer division using repeated subtraction. Ignore division by zero.
7.The Fibonacci numbers are defined by the recurrence
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2, n>1
Write a Haskell function fib that, given an integer n=0, 1, 2, ... returns the nth Fibonacci number by encoding the above recurrence directly. If you think about the way a call to this function will be evaluated you will notice that there is an enormous degree of redundancy. For a given n, he function call Fn-2 is made twice, the call Fn-3 three times, Fn-4 five times etc. (Notice any pattern?!) A much more efficient way to compute the nth Fibonacci number is to use an auxiliary function that includes as arguments the kth and the (k+1)th Fibonacci numbers for some number k. The idea is that the recursive call is made with the (k+1)th and the (k+2)th Fibonacci numbers - can you see how to generate them from the kth and the (k+1)th? You will also need to carry a third argument which keeps count of how many (more) numbers in the sequence to calculate before arriving at the required (nth) one. Define an auxiliary function fib' which works in this way and redefine the original fib function to call fib' appropriately.
8. The Golden Ratio, G, is a beautiful number discovered by the ancient Greeks and used to proportion the Parthenon and other ancient buildings. The golden ratio has this property: take a rectangle whose sides (long:short) are in the golden ratio. Cut out the largest square you can and the sides of the rectangle that remains are also in the golden ratio. From this you should be able to work out that (do it!). Curiously, it can also be shown that the ratio of consecutive Fibonacci numbers converges on the golden ratio, i.e. . Inspired by your earlier fib' function build a function gRatio which takes a threshold value e of type Float and which returns the value of where n is the smallest integer satisfying . Hint: notice that you now need three consecutive Fibonacci numbers instead of just two. The absolute value of a number (ignoring its sign, that is) can be obtained using Haskell's abs function. Also, to perform the division above, you must first cast the integers representing the various Fibonacci numbers into floating-point numbers using the built-in function fromInt. For now you can think of this function as having type fromInt :: Int -> Float. The true picture will emerge later in the course.
9.A decimal number d may be converted to binary representation by the following algorithm:
i.If d is less than 2, its binary representation is just d.
ii.Otherwise, divide by 2. The remainder gives the last (rightmost) digit of the binary representation, which is either 0 or 1.
iii.The preceding digits of the binary representation are given by the binary representation of the quotient from step (b).
Write a function binary which takes an integer and converts it to its binary representation. This will be a decimal number consisting only of the digits 0 and 1. As an example, binary19 should produce the answer 10011.
10.Write a function newbase of two arguments which converts a number to its representation in some specified base 10. The value produced will be a decimal number containing only the digits which are valid in the new base. This is a generalisation of the binary function above.
11.The number of arrangements (permutations) of r objects selected from a larger set of n objects is denoted as nPr and defined as:
n!
n (n-1) (n-2) … (n-r+1) or______
(n-r)!
Define a recursive function perm such that perm n r evaluates nPr (do not use fact)
12.Given an integer argument the built-in function succ returns the next largest integer. For example, succ 4 returns 5. The function pred does the opposite. Write a function add2 which will add two non-negative numbers using succ and pred only. Use multiple recursion equations with pattern matching rather than conditionals. Remember that there are two parameters, each of which can be either zero or non-zero, so a strict definition will require four equations. Can the number of equations be reduced?
13.Write a recursive function larger to determine the larger of two positive integers. Use multiple recursion equations and do not use conditional expressions. Hint: write down the left-hand sides of the four recursion equations first.
14.Write a recursive function chop which takes an n-digit number and which uses repeated subtraction to define a pair of numbers which are the first n-1 digits and the last digit respectively. Do not use div or mod.
15.Write a function concatenate which concatenates the digits of two non-zero integers. concatenate123 456 evaluates to 123456 but concatenate123 0 evaluates to 123. Use the earlier function chop. Estimate the cost of your concatenate function in terms of the number of multiplications and subtractions it performs.
Functional Programming in Haskell
Unassessed Exercise Sheet 3: Lists and Higher-order Functions
Many of these questions concern some of Haskell's (first-order) built-in list processing functions. By the end of the course you should be familiar with all of them and be able to use them to best advantage.
length :: [ a ] -> Int
The number of items in a list
(!!) :: [ a ] -> Int -> a
xs !! n returns the nth element of xs starting at index 0
null :: [ a ] -> Bool
True if the list is empty; False otherwise
(++) :: [ a ] -> [ a ] -> [ a ]
Joins (appends) two lists
head :: [ a ] -> a
Returns the first item in the list (equivalent to index 0)
tail :: [ a ] -> [ a ]
Returns the list with the first item removed
take :: Int -> [ a ] -> [ a ]
take n xs returns the first n items in xs
drop :: Int -> [ a ] -> [ a ]
drop n xs returns the rest of xs after the first n items have been removed
zip :: [ a ] -> [ b ] -> [ ( a, b ) ]
Zips the elements of the two lists pairwise
unzip :: [ ( a, b ) ] -> ( [ a ], [ b ] )
Opposite of zip
The following are list generalisations of the functions +, *, &, ||, ++, max and min respectively:
sum :: [ Int ] -> Int
Returns the sum of the elements of the list (also works with Integer, Float and Double types)
product :: [ Int ] -> Int
As above, but returns the product
and :: [ Bool ] -> Bool
True iff every element of the list is True
or :: [ Bool ] -> Bool
False iff every element of the list is False
concat :: [ [ a ] ] -> [ a ]
Joins the elements of a list of lists
maximum :: [ Int ] -> Int
Delivers the largest element in the given list (also works with Integer, Float and Double types)
minimum :: [ Int ] -> Int
As above but delivers the smallest element
Now the higher-order functions:
map :: ( a -> b ) -> [ a ] -> [ b ]
Applies the given function to each element of the given list
filter :: ( a -> Bool ) -> [ a ] -> [ a ]
Returns a list of those elements in the given list which satisfy the given predicate
zipWith :: ( a -> b -> c ) - [ a ] -> [ b ] -> [ c ]
Applies the given binary function pairwise to the elements of the two lists
foldr1 :: [ a -> a -> a ) -> [ a ] -> a
Returns the result of inserting the binary operator, in right-associative fashion, in between each element of the given list. foldl1 does the same but associates to the left.