School of Information Technology and Electrical Engineering
Semester One Examinations, 2023
COMP3400 Functional and Logic Programming
§Very Short Answer
Question 1. [20 marks]
The following ten questions are worth two marks each for a total of 20 marks. Part (a) [2 marks]
A Pythagorean triplet is a triplet of positive integers (a, b, c) such that a2 + b2 = c2. Write a Haskell expression that produces a list of a hundred Pythagorean triplets.
Part (b) [2 marks]
Define a function f so that
> : type f
f :: (a -> a -> a) -> a -> a
up to renaming the type variables. Your implementation does not have to be total.
Part (c) [2 marks]
The zip of two lists xs and ys is given by [(x,y) | x <- xs, y <- ys]. Use an applicative to generate the zip of two lists.
Part (d) [2 marks]
Very briefly explain what the function foo (_ : x: __) = x does.
Part (e) [2 marks]
For what value of xs does fold r f b xs == foldl f b xs
Part (f) [2 marks]
Let reverse :: [Integer] -> [Integer] be a function that reverses a list. Write a useful quick-check for reverse. Just write xs = arbitrary [Integer] to get an arbitrary list of integers.
Part (g) [2 marks]
What is the type of the following function. Be sure to include any necessary class constraints. foo x (y: ys) = if x > y then ys else y:[]
Part (h) [2 marks]
What is the β-normal form of λx.x(λy.y)x?
Part (i) [2 marks]
Using the applicative for Either write a Haskell expression that adds Right 1 and Right 2 to get Right 3.
Part (j) [2 marks]
Define map :: (a -> b) -> [a] -> [b] using the fold r function.
§Short Answer
The following eight questions are worth five marks each for a total of 40 marks.
Question 2. [5 marks]
Give the β normal form for the following λ-calculus expression or show the expression is divergent.
(λx.xx)(λy.y)(λz.z9)(λy.y)
Question 3. [5 marks]
Suppose there is an Integer in the name password which has global scope. Implement the function verify :: IO () that gives a user three tries to guess the password.
Example usage in REPL:
> password = 1234
> verify
Prompt: 2
Prompt: 10
Prompt: 7
Failure .
> verify
Prompt: 1234
Success
Question 4. [5 marks]
Part (a) [3 marks]
Write a function group :: Eq a => [a] -> [[a]] that groups adjacent equivalent items in the following way
> group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1]
[[1,1],[2,2,2],[3],[4,4,4],[1]]
Hint: Recall the functions dropWhile and takeWhile of type (a -> Bool) -> [a] -> [a].
Part (b) [2 marks]
Using afold write a function biggest :: [[a]] -> [a] to find the largest group. If there are ties, the group with least index in the input is returned.
> biggest $ group [1, 1, 2, 2, 2, 3, 4, 4, 4, 1]
[2,2,2]
Question 5. [5 marks]
Consider the higher-order function unfold
unfold p h t x
| p x = []
| otherwise = h x : unfold p h t (t x)
Part (a) [2 marks]
What is the type of unfold?
Part (b) [3 marks]
Define map :: (a -> b) -> [a] -> [b] using unfold.
Question 6. [5 marks]
Write a Haskell function
numSums :: Integer -> [Integer] -> Integer
where numSums target xs is the number of ways the target can be computed by summing members of xs.
Preconditions: The members of xs are distinct and positive non-zero.
> numSums 30 [25, 10, 5]
5
because 25+5, 10+10+10, 10+10+5+5, 10+5+5+5+5, and 5+5+5+5+5+5 are the comprehensive ways you can make thirty from a 25, 10, and 5.
Question 7. [5 marks]
Define the norm of a list xs to be given by
norm xs = (sum $ map (^2) xs) ** 0.5
(the square root of the sum of squares of the list’s elements).
Part (a) [3 marks]
Define a function trNorm :: Float -> [Float] -> Float. that computes the norm of a list tail recursively.
Part (b) [2 marks]
Give an iteration invariant and bound value that proves the correctness of trNorm. Do not prove that your function satisfies this invariant or that your bound value is valid – just state them.
Question 8. [5 marks]
Define a function
mapMaybe :: (a -> b) -> [Maybe a] -> Maybe [b]
which maps a function over a list of Maybe a. If Nothing is in the input list the answer is Nothing:
> mapMaybe (>0) [Just 1, Just 0, Just 2]
Just [True,False,True]
> mapMaybe (>0) [Just 1, Nothing, Just 2]
Nothing
Question 9. [5 marks]
Define a custom data type Walker a and the functions
fromList :: [a] -> Maybe (Walker a); fromList [] = Nothing
stepL :: Walker a -> Walker a
stepR :: Walker a -> Walker a
peek :: Walker a -> a
so that we have the following functionality:
> Just xs = fromList [1,2,3,4]
> peek xs
1
> peek $ stepR xs
2
> peek $ stepL xs
1
> peek $ (stepR . stepR) xs
3
> peek $ (stepL . stepR . stepR) xs
2
> peek $ (stepR . stepR . stepR . stepR) xs
4
§Long Answer
Show your work. Unsupported solutions will receive little or no credit.
Question 10. [10 marks]
Consider the following datatype for representing polynomials with integer degree and coef- ficients from a:
data Polynom a = Mono a Integer
| Add (Polynom a) (Polynom a)
| Mul (Polynom a) (Polynom a) deriving (Show, Eq)
For instance, 2x4 + 3x + 1 is given by Add (Add (Mono 2 4) (Mono 3 1)) (Mono 1 0).
Part (a) [3 marks]
Define a functor for Polynom that maps a function over the coefficients:
> (+1) <$> Add (Add (Mono 2 4) (Mono 3 1)) (Mono 1 0)
Add (Add (Mono 3 4) (Mono 4 1)) (Mono 2 0)
> (/2) <$> Add (Mul (Mono 1 2) (Mono 3 4)) (Mono 5 6)
Add (Mul (Mono 0.5 2) (Mono 1.5 4)) (Mono 2.5 6)
Part (b) [7 marks]
Prove fmap id = id (i.e. the first functor law) for your functor.