Functional Programming
lab session 2
Introduction
The second lab session of the course Functional Programming consists of seven exercises. Exercise 7 is worth
20 points, all other exercises are worth 10 points (totalling 80 points). The remaining 20 points are awarded
(by manual inspection by the teaching assistants) for (a Haskellish) style of programming and efficiency.
Hence, if you passed all problems in Themis, your grade is not automatically a 10.
Exercise 1: Fibonacci Based Recurrence
The Fibonacci series is defined by the following recurrence:
F0 = 1
F1 = 1
Fn = Fn−1 + Fn−2
Based on the Fibonacci series a new recurrence is defined:
A0 = 1
An = An−1 + 2 · (Fn − n)
Make a function recfibs :: Int -> Int -> [Integer] such that the call recfibs m n returns the list
[Am,Am+1,…,An−1,An]. Your program should be able to compute recfibs 0 1000 within 1 second.
Exercise 2: relPrimeDiv
Let d(n) be the number of divisors of n, e.g. d(12) = 6 since the divisors of 12 are 1,2,3,4,6,and 12.
Write a Haskell definition of the infinite increasing list relPrimeDiv :: [Integer] of numbers n such
that n and d(n) are relatively prime. Two positive integers are relatively prime if they share no common
divisors except 1.
For example, take 15 relPrimeDiv should return [1,3,4,5,7,11,13,15,16,17,19,21,23,25,27]. The
time to compute take 5000 relPrimeDiv should not exceed 2 seconds.
Exercise 3: Prime Products
Write a Haskell definition of the infinite increasing list primeProducts :: [Integer] of numbers n that are
the product of two primes. For example, take 10 primeProducts should return [4,6,9,10,14,15,21,22,25,26].
The time to compute take 5000 primeProducts should not exceed 1 second.
1
Exercise 4: Counting Palindromes
A positive integer n is called a palindromic number if the reversal of its digits yields n again. So, 121 is a
palindromic number, while 123 is not.
Write a Haskell definition of the infinite increasing list numPals :: [Integer] of the number of nonzero
palindromic numbers less than 10n, where n starts from 1. Clearly, for n = 1 these palindromes are the
non-zero digits (i.e. a total of 9). For n = 2, it are the 1 digits palindromes together with the numbers 11,
22, 33, 44, 55, 66, 77, 88, 99. So, take 2 numPals should return [9,18].
The time to compute take 5000 numPals should not exceed 1 second.
Exercise 5: Composites
In the lecture it was shown that the following code can be used to generate the infinite list of primes:
primes :: [Integer]
primes = sieve [2..]
where
sieve :: [Integer] -> [Integer]
sieve (p:xs) = p : sieve [x | x <- xs, x ‘mod‘ p /= 0]
Write a Haskell function composites :: Int -> [Integer] such that composites n produces the infinite
list of compsites (i.e. non-primes) that are divisible by any of the first n primes.
For example take 10 (composites 1)=[4,6,8,10,12,14,16,18,20,22] which is simply the list of even
integers, excluding 2. A less trivial cases is take 10 (composites 5)=[4,6,8,9,10,12,14,15,16,18].
Exercise 6: RPN to Prefix
In reverse Polish notation (RPN) arithmetic expressions are written using post-fix notation, i.e. the operators
follow their operands; for instance, to add 3 and 4, one would write 3 4 + rather than 3 + 4. Another
example, using multiple operations is 3 4 – 5 +, which in conventional notation is 3 – 4 + 5. A nice
property of RPN is that there is no need for parentheses, e.g. in conventional notation we need parentheses
in (7 – 2)*5, but in RPN this is simply written as 7 2 – 5 *.
Write a Haskell function rpn2prefix :: String -> String that converts a string containing an integer
expression in RPN into an equivalent Haskell expression in prefix notation. You may assume that the input
string consists of non-negative integers, and the operators + (addition), – (subtraction), * (multiplication),
and / (integer division, i.e. div). Moreover, the input may contain (abundant) spaces. Make sure that the
format of the output string matches the following examples.
Example 1:
rpn2prefix “1 2 +”
output:
“((+) 1 2)”
Example 2:
rpn2prefix “12 1 + 3 *”
output:
“((*) ((+) 12 1) 3)”
Example 3:
rpn2prefix “17 2 – 2 * 5 /”
output:
“((div) ((*) ((-) 17 2) 2) 5)”
Exercise 7: An Expression Parser
In the lecture (see the slides) the implementation of a recursive descent parser for a small grammar was
discussed. The problem with the discussed parser is that it aborts on incorrect input (with an error message).
In reality, for example in a compiler, a parser should not abort. Therefore, a better type for the parser would
be:
parser :: String -> (Bool, String, [String])
Page 2
The first element of the returned tuple is True if the parsing succeeded without errors, otherwise it is False.
The second element is the string that was accepted by the parser. In case of a parse error, this string is
the part of the input that was accepted up to the point where the parsing failed. The last element of the
returned tuple is the remaining input, which should be empty upon succesfull parsing.
Write a parser with the above type that accepts the following grammar (which is suitable for recursive
descent parsing):
E -> T E’
E’ -> + T E’
E’ -> – T E’
E’ ->
T -> F T’
T’ -> * F T’
T’ -> / F T’
T’ ->
F -> ( E )
F ->
F ->
The lexer should ignore all spaces and tabs in the input, so the input “a*b+42*2” is the same as “a*b + 42*2”.
Example 1:
input:
parser “5 + 3*(7 + (8 + 9)*3*2)”
output:
(True,”5+3*(7+(8+9)*3*2)”,[])
Example 2:
input:
parser “5+3*(7+(8+9)*3*2) 42″
output:
(False,”5+3*(7+(8+9)*3*2)”,[“42”])
Example 3:
input:
parser “5+3*+42″
output:
(False,”5+3*”,[“+”,”42″])
Example 4:
input:
parser “f(42)”
output:
(False,”f”,[“(“,”42″,”)”])
Page 3