Question 1
(a) Select ONE answer for each section.
(i) Which of the following is an invalid list in Haskell:
1) [ [] ]
2) [ [],[] ]
3) [[1], [] ]
4) [False , [True]]
ANS : 4)
(3 Marks)
(ii) The function add defined by
add x y = x + y
has type:
1) Int
2) (Int,Int) -> Int
3) (Int -> Int) -> Int
4) Int -> Int -> Int
ANS : 4)
(3 Marks)
(iii) Evaluating [(x,y) | y <- [1..3], x <- [1..2]] gives:
1) [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]
2) [(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)]
3) [(1,1),(2,1),(1,2),(2,2),(1,3),(2,3)]
4) [(1,1),(2,1),(3,1),(1,2),(2,2),(3,2)]
ANS : 3)
(3 Marks)
(iv) Evaluating length (zip [1..5] [6..11]) gives:
1) 11
2) 10
3) 6
4) 5
ANS 4) (3 Marks)
(v) The expression Node (Node Leaf Leaf) Leaf is a value of the type:
1) data Tree = Node | Leaf
2) data Tree = Leaf Tree | Node
3) data Tree = Leaf | Node Tree Tree
4) data Tree = Leaf Tree | Node Tree Tree
ANS : 3) (3 Marks)
b) Define the following library functions using recursion:
product :: [Int] -> Int
length :: [a] -> Int
reverse :: [a] -> [a]
map :: (a -> b) -> [a] -> [b]
ANS :
product [] = 1
product (x:xs) = x * product xs
length [] = 0
length (x:xs) = 1 + length xs
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
map f [] = []
map f (x:xs) = f x : map f xs
(4 x 3 Marks)
(c) With the aid of a simple example, explain how the library function foldr captures a simple pattern of recursion for processing lists. There is no need to give the actual definition for foldr itself.
ANS : An example e.g foldr (+) 0 and show how the : in the list can be changes to + with 0 being the initial value
(7 Marks)
(Total 34 Marks)
Question 2
• Using list comprehensions, define functions
smaller :: Int -> [Int] -> [Int]
larger :: Int -> [Int] -> [Int]
that return the numbers in a list that are strictly smaller and larger than
a given number, e.g. smaller 3 [2,4,1,5] should return [2,1].
Ans :
smaller x xs = [a | a <- xs, a < x]
larger x xs = [a | a <- xs, a > x]
(4 Marks)
• Using smaller and larger, write a recursive function that implements quicksort. The function has the following type
qsort :: [Int] -> [Int]
You may assume that the argument list contains no duplicates.
ANS:
qsort [] = []
qsort (x:xs) = qsort (smaller x xs) ++ [x] ++ qsort (larger x xs)
(6 Marks)
(c ) Consider the following datatype of trees:
data Tree = Leaf Int | Node Tree Tree
• Write down three different values of type Tree with the property that all
the leaves in each example contain the integer zero.
ANS :
Leaf 0
Node (Leaf 0) (Leaf 0)
Node (Leaf 0) (Node (Leaf 0) (Leaf 0))
(3 Marks)
• Define a function
size :: Tree → Int
that calculates the number of leaves that are contained in a given tree.
ANS:
size (Leaf n) = 1
size (Node l r) = size l + size r
(5 Marks)
• Define a function
depth :: Tree → Int
that calculates the depth of a tree, where the depth is given by the number of nodes in the longest path from the root of the tree to a leaf in the tree.
ANS:
depth (Leaf n) = 0
depth (Node l r) = 1 + max (depth l) (depth r)
(6 Marks)
iv) Let us say that a tree is full if every node has the property that the number of leaves in its left and right subtrees are equal. Using size, define a function
full :: Tree → Bool
that decides if a tree is full.
ANS:
full (Leaf n) = True
full (Node l r) = size l == size r
&& full l
&& full r
(6 Marks)
d) Suppose you are given a function
divides :: Int -> Int -> Bool
that decides if one integer is divisible by another, e.g.
divides 15 2 is False and
divides 15 3 is True.
Using a list comprehension, define a function
divisors :: Int -> [Int]
that returns the divisors of a natural number. For example, divisors 15 should give [1,3,5,15].
ANS :
divisors n = [x | x <- [1..n], divides n x]
(4 Marks)
(Total 34 Marks)
Question 3
• Define the notion of a monad in Haskell, and state the three equational
properties that every such monad must satisfy.
ANS:
Definition:
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
Equational properties:
return x >>= f = f x
mx >>= return = mx
(mx >>= f) >>= g = mx >>= (\x -> (f x >>= g))
(9 marks)
• Given the type definition
data Result a = Succeed a | Fail
show how Result can be made into a monadic type.
ANS:
instance Monad Result where
return :: a -> Result a
return x = Succeed x
(>>=) :: Result a -> (a -> Result b) -> Result b Fail >>= _ = Fail
(Succeed x) >>= f = f x
(5 marks)
• Explain how the do notation can be used to abbreviate a common pattern of monadic programming, and describe the behaviour of this notation for the particular case of the Result monad.
ANS:
An expression of the form
do x1 <- m1
x2 <- m2
...
xn <- mn
f x1 x2 ... xn
abbreviates the following pattern:
m1 >>= \x1 ->
m2 >>= \x2 ->
…
mn >>= \xn ->
f x1 x2 … xn
For the case of the Result monad, such an expression only
succeeds if each of the component expressions m1..mn succeeds,
in which case the resulting values x1.. xn are combined into
a single result value by applying the function f.
(8 marks)
• Using the do notation, define a function
sequence :: [Result a] → Result [a]
that transforms a list of results into a single result.
ANS:
sequence [] = return []
sequence (mx:mxs) = do x <- mx
xs <- sequence mxs
return (x:xs)
(6 marks)
• Explain why sequence is not specific to the Result monad, and state the general type that can be specified for this function.
ANS:
The sequence function is not specific to the Result monad because
its definition only makes use of the basic monadic operations return
and >>=, which are defined for any monad. Hence, we have:
sequence :: Monad m => [m a] -> m [a]
(6 marks)
(Total 34 Marks)
Question 4
• Define appropriate versions of the library functions:
repeat :: a -> [a]
repeat x = xs where xs = x:xs
take :: Int -> [a] -> [a]
take 0 _ = []
take _ [] = []
take n (x:xs) = x : take (n – 1) xs
replicate :: Int -> a -> [a]
replicate n = take n . repeat
for the following type of binary trees:
data Tree a = Leaf | Node (Tree a ) a (Tree a)
deriving Show
ANS :
repeatTree :: a -> Tree a
repeatTree x = Node t x t
where t = repeatTree x
takeTree :: Int -> Tree a -> Tree a
takeTree 0 _ = Leaf
takeTree _ Leaf = Leaf
takeTree n (Node l x r) = Node (takeTree (n-1) l) x (takeTree (n-1) r)
replicateTree :: Int -> a -> Tree a
replicateTree n = takeTree n . repeatTree
(3 x 7 Marks)
• What do you understand by the terms (giving examples if it helps):
Lazy Evaluation
Domain Specific Languages
Pure functional languages (Is Haskell such a language? )
(4 x 3 marks)
ANS: Correct descriptions
(Total 34 Marks)
Question 3
(b) Given the following:
[CHAR] The set of all bytes
FileSystem
file: seq CHAR
• Write an operation to delete all occurrences of a CHAR c? in file.
(3 Marks)
• Write an operation to delete the first occurrence of a CHAR c? in file. (You should write a pre-condition to ensure that there is at least one such occurrence.)
(4 Marks)
(ii) Write an operation that deletes a sequence of bytes, tobedeleted?, from a file. The deleted sequence should be output as part of the operation.
(6 Marks)
(iii) As specified, are the above operations non-deterministic? For any operations that are non-deterministic, suggest a change in the spec that will remove the non-determinism. Show how these changes would be written in Z.
• Marks)
(a) Give a Z specification of a stack (using generic type), showing:
• system state; (4 Marks)
• operation pop; (4 Marks)
• operation push; (4 Marks)
• operation isEmpty which returns a message – either empty or non-empty depending on whether or not the stack is empty. (3 Marks)
(Total 34 Marks)
(6 Marks)
(Total 34 Marks)
Question 4
You are given the partial specification of a file system. This system is made up if files which are sequences of BYTE’s. Each file has an access level value and users can only retrieve the file if the user has that level of access assigned to it.
The basic types are:
[ BYTE, The set of all bytes
FILEID, The set of all fileid’s
PERSON The set of all persons
]
The system state is:
FileSystem
users: ℙPERSON
files : ℙFILEID
fileData :FILEID ⇸ iseq PERSON
hasAccess : PERSON ↔ ℕ
fileAccessLevel : FILEID⇸ℕ
file = dom fileData
dom hasAccess ⊆ users
:
:
• users is the set of registered users in the system
• files is the set of FILEID’s of all the files in the system.
• fileData is the association of FILEID to the sequence of BYTE’s contained in the file.
• fileAccessLevel associates a FILEID with the level of access required by a user to retrieve the file contents.
• hasAccess maps a user to their various access levels.
• Describe the invariants in the system. In some cases, the invariant may not be described in the narrative. Also, you should add in invariants that are not written explicitly in the system state but are described in the narrative.
(6 Marks)
• Write the following operations:
• Add a new user to the system
(4 Marks)
• Add a new file to the system
(6 Marks )
• Retrieve a file (in the form of its sequence of bytes) given the user and FILEID. This operation should be robust.
(9 Marks)
• Improvement to the spec:
• Currently, we use a relation to link a user with all his/her access levels. Show how you might improve the model so that your model has a user linked to their highest level of access. Show how you would change the system state and how you would change the appropriate operations.
(9 Marks)
(Total 34 Marks)