Functional Programming SS16
Solution – Exam 17.08.2016
aaProf. Dr. J. Giesl D. Korzeniewski
Exercise 1 (Programming in Haskell): (6 + 6 + 7 + 16 = 35 points)
We de�ne a polymorphic data structure Warehouse to represent a warehouse that can contain goods.
data Warehouse a
= Corridor (Warehouse a) (Warehouse a)
| Shelf [a] deriving Show
The data structure Goods is used to represent di�erent types of goods.
data Goods
= NoGoods | Box | Barrel deriving (Show, Eq)
For example, aWarehouse is a valid expression of type Warehouse Goods.
aWarehouse = Corridor (Shelf [Box, Box]) (Corridor (Shelf [Barrel, NoGoods]) (Shelf [Box]))
The following function can be used to fold a Warehouse:
fold :: (a -> a -> a) -> a -> Warehouse a -> a
fold f res (Shelf xs) = foldr f res xs
fold f res (Corridor left right) = f (fold f res left) (fold f res right)
In the following exercises, you are allowed to use the functions given above, functions implemented in preceding
parts of the exercise, and prede�ned functions from the Haskell-Prelude. Moreover, you are always allowed to
implement additional auxiliary functions.
a) Implement a function buildWarehouse :: [a] -> Int -> Warehouse a that gets a list and a number
indicating how many items may be stored in one shelf. The function should return a warehouse containing
all items in the input list, distributed on the minimal number of shelves possible while respecting the
limit given by the second input.
If the input list is the empty list, Shelf [] should be returned. If the integer argument is less than 1
the function may behave arbitrarily.
For example buildWarehouse [Box, Box, Barrel, NoGoods, Box] 2 should result in a warehouse
with 3 shelves which together contain all elements from the list. A possible result would be aWarehouse,
as de�ned above.
b) Implement a function mapWarehouse together with its type declaration (mapWarehouse :: …). The
function mapWarehouse gets a unary function and a Warehouse, and applies the function to every element
stored in the lists of the Shelf objects of the Warehouse. For example, the expression
mapWarehouse (\x -> if x == Box then NoGoods else x) returns a function that replaces all Boxes
in a Warehouse by NoGoods.
c) Implement a function inventory :: Warehouse Goods -> (Int, Int) that returns a tuple containing
the number of Boxes and Barrels in the input Warehouse. For example inventory aWarehouse should
yield (3, 1).
Hints:
You may use fold given above and mapWarehouse from the previous task (even if you have not solved
the previous task).
d) In this part of the exercise, you should implement a program that controls a forklift. The goal of the
forklift is to store Goods in a Warehouse. Goods can only be placed in free spaces indicated by NoGoods
or stacked on top of a shelf.
Implement a function storeGoods :: Warehouse Goods -> Goods -> IO (). Its input is a Warehouse
that contains Goods. It processes the Warehouse as follows:
1
Functional Programming SS16
Solution – Exam 17.08.2016
For a Corridor, it prints “Do you want to turn left or right? (l|r)”. If the user answers “l”,
it proceeds with the �rst argument of the Corridor, if the answer is “r” it continues with the second
argument of Corridor, otherwise an error message “Incorrect input” is printed and the question is
repeated.
Once a Shelf is encountered the user is asked “How high do you want to raise the fork?” and an
integer k is read. The program then distinguishes the following cases:
• The number k is less than 0: An error message “Your forklift fell over” is printed.
• The number k is a position of the list in the Shelf: (Here an object Shelf [x_0, …, x_n] has
positions 0, . . . , n and the object at position i is x_i.) If the list contains NoGoods at position
k, the message “Inserted the
depending on the input, otherwise the message “No room in the shelf” is printed.
• The number k is at least the length of the list: The message “Stacked on top of the shelf” is
printed.
Afterwards the program terminates.
A successful run might look as follows:
*Main> storeGoods (Corridor (Shelf [Barrel, NoGoods, Box]) (Shelf [Box])) Barrel
Do you want to turn left or right? (l|r) l
How high do you want to raise the fork? 1
Inserted the Barrel
In the following run, the goods are stacked on top of a shelf:
*Main> storeGoods (Corridor (Shelf [Barrel, NoGoods, Box]) (Shelf [Box])) Barrel
Do you want to turn left or right? (l|r) y
Incorrect input
Do you want to turn left or right? (l|r) r
How high do you want to raise the fork? 42
Stacked on top of the shelf
Hints:
You should use the function getChar :: IO Char to read a character input from the user. Moreover,
you may assume there is a function getInt :: IO Int that reads an integer from the command line.
To print a String, you should use the function putStr :: String -> IO () or the function putStrLn
:: String -> IO (), if the output should end with a line break. You should use the function
show :: Goods -> String to convert a Goods object to a String. To save space, you may also assume
that the following additional declarations exist in your program:
leftRight, incorrect, howHigh, fellOver, noRoom, stacked :: String
leftRight = “Do you want to turn left or right? (l|r) ”
incorrect = “Incorrect input”
howHigh = “How high do you want to raise the fork? ”
fellOver = “Your forklift fell over”
noRoom = “No room in the shelf”
stacked = “Stacked on top of the shelf”
Solution:
a) buildWarehouse :: [a] -> Int -> Warehouse a
buildWarehouse [] _ = Shelf []
buildWarehouse xs max | length xs <= max = Shelf xs
| otherwise = Corridor
(Shelf (take max xs))
(buildWarehouse (drop max xs) max)
2
Functional Programming SS16
Solution - Exam 17.08.2016
b) mapWarehouse :: (a -> b) -> Warehouse a -> Warehouse b
mapWarehouse f (Shelf xs) = Shelf (map f xs)
mapWarehouse f (Corridor left right) =
Corridor (mapWarehouse f left) (mapWarehouse f right)
c) inventory :: Warehouse Goods -> (Int, Int)
inventory w =
fold (\(x, y) (x’, y’) -> (x+x’, y+y’)) (0, 0) (mapWarehouse invHelper w)
where invHelper Box = (1, 0)
invHelper Barrel = (0, 1)
invHelper _ = (0, 0)
d) storeGoods :: Warehouse Goods -> Goods -> IO ()
storeGoods (Corridor left right) g = do
putStr leftRight
input <- getChar putStrLn "" case input of 'l' -> storeGoods left g
‘r’ -> storeGoods right g
_ -> do
putStrLn incorrect
storeGoods (Corridor left right) g
storeGoods (Shelf xs) g = do
putStr howHigh
input <- getInt case () of _ | input < 0 -> putStrLn fellOver
| input < (length xs) -> if (xs !! input) == NoGoods
then putStrLn (“Inserted the “++(show g))
else putStrLn noRoom
| otherwise -> putStrLn stacked
Exercise 2 (Semantics): (17 + 16 + 9 = 42 points)
a) i) Let D1, D2, and D3 be domains with complete orders v1, v2, and v3, respectively. Let g : D1 → D2
and f : D2 → D3 be strict and monotonic functions. Here, we say that g is strict on a (possibly
non-�at) domain D1 if and only if g(⊥D1) = ⊥D2 . As usual, f ◦ g is the composition of f and g
(i.e., (f ◦ g)(x) = f(g(x))). Prove or disprove whether f ◦ g is:
1) strict
2) monotonic
ii) Let Σ = {a, . . . , z}, let Σ∗ be the set of all �nite words over the alphabet Σ, and let ≤lex denote
the usual lexicographic order on Σ∗ (which corresponds to the order of words in a lexicon). So, for
example abc ≤lex abcd and xyz ≤lex xzz.
Prove or disprove each of the following statements:
1) There is an in�nite chain in (Σ∗,≤lex).
2) The order ≤lex is complete on Σ∗.
3) The order ≤lex is con�uent.
b) i) Consider the following Haskell function f:
f :: (Int, Int) -> Int
f (x, 0) = 0
f (x, y) = (x * y) + f (x, y – 1)
3
Functional Programming SS16
Solution – Exam 17.08.2016
Please give the Haskell declaration for the higher-order function ff corresponding to f, i.e., the
higher-order function ff such that the least �xpoint of ff is f. In addition to the function declaration,
please also give the type declaration for ff. You may use full Haskell for ff.
ii) Let φff be the semantics of the function ff. Give the de�nition of φ
n
ff(⊥) in closed form for any
n ∈ N, i.e., give a non-recursive de�nition of the function that results from applying φff n-times to
⊥. Here, you should assume that Int can represent all integers, so no over�ow can occur.
iii) Give the de�nition of the least �xpoint of φff in closed form.
c) Consider the data type declarations on the left and, as an example, the graphical representation of the
�rst three levels of the domain for Nats on the right:
data Nats = Z | S Nats
————————————-
data Warehouse a
= Corridor
(Warehouse a)
(Warehouse a)
| Shelf [a]
data Goods
= NoGoods | Box | Barrel ⊥
Z 2nd level
3rd level
1st level
S Z S (S ⊥)
S ⊥
Give a graphical representation of the �rst three levels of the domain for the type Warehouse Goods.
You may abbreviate the constructors to the �rst two letters (i.e., you may write Co instead of Corridor).
Solution:
a) i) 1)
(f ◦ g)(⊥D1) = f(g(⊥D1)) Def. of ◦
= f(⊥D2) g is strict
= ⊥D3 f is strict
Thus f ◦ g is strict.
2) Let d1, d
′
1 ∈ D1 such that d1 vD1 d′1. Because g is monotonic, we have that g(d1) vD2 g(d′1).
Because f is monotonic, we also have f(g(d1)) vD3 f(g(d′1)). Therefore, (f ◦ g)(d1) vD3 (f ◦
g)(d′1). So, f ◦ g is monotonic.
ii) 1) C = {z, zz, zzz, . . . } is an in�nite chain.
2) The relation ≤lex is not a cpo. A relation ≤lex is a cpo i� Σ∗ has a least element w.r.t. ≤lex and
every ≤lex-chain has a least upper bound in Σ∗. Obviously, the least element is the empty word
�. Consider C = {z, zz, zzz, . . . }. For every word w ∈ Σ∗ of length n ∈ N we have w ≤lex zn+1,
w 6= zn+1 and zn+1 ∈ Σ∗. Because Σ∗ contains only �nite words, this implies that the chain C
has no least upper bound in Σ∗.
3) The relation ≤lex is con�uent. If u ≤lex v, u ≤lex w and n is the maximum of the lengths of
v and w, then we have v ≤lex zn and w ≤lex zn. This su�ces since ≤lex is transitive and thus
≤∗lex=≤lex.
4
Functional Programming SS16
Solution – Exam 17.08.2016
b) i) ff :: ((Int, Int) -> Int) -> ((Int, Int) -> Int)
ff f (x, 0) = 0
ff f (x, y) = (x * y) + f (x, y – 1)
ii)
(φnff(⊥))(x, y) =
0 if y = 0 ∧ 0 < n x·y·(y+1) 2 if 0 < y < n ∧ x 6= ⊥ ⊥ otherwise iii) (lfp φff)(x, y) = 0 if y = 0 x·y·(y+1) 2 if 0 < y ∧ x 6= ⊥ ⊥ otherwise c) Co ⊥ (Co ⊥ ⊥) Co (Sh ⊥) ⊥ Sh ⊥ Sh (⊥ : ⊥) ⊥ Co ⊥ ⊥ Sh [ ]Co (Co ⊥ ⊥) ⊥ Co ⊥ (Sh ⊥) Exercise 3 (Lambda Calculus): (5 + 14 + 6 = 25 points) a) Consider the following variant of the function from Exercise 2b: f' :: Int -> Int -> Int
f’ x 0 = 0
f’ x y = (x * y) + f’ x (y – 1)
Please implement this function in the lambda calculus, i.e., give a lambda term q such that, for all
x, y, z ∈ Z, f’ x y == z if and only if q x y can be reduced to z via WHNO-reduction with the →βδ-
relation and the set of rules δ as introduced in the lecture to implement Haskell. You can use in�x
notation for prede�ned functions like (==), (∗), (+), or (−).
b) Let
t = λ g x y. if (x == 1) Nil (Cons y (g (x− 1) (y ∗ x)))
and
δ = { if True→ λx y. x,
if False→ λx y. y,
fix→ λ f. f(fix f)}
∪ { x− y → z | x, y, z ∈ Z ∧ z = x− y}
∪ { x+ y → z | x, y, z ∈ Z ∧ z = x+ y}
∪ { x ∗ y → z | x, y, z ∈ Z ∧ z = x · y}
∪ { x == x→ True | x ∈ Z}
∪ { x == y → False | x, y ∈ Z, x 6= y}
5
Functional Programming SS16
Solution – Exam 17.08.2016
Please reduce fix t 3 1 by WHNO-reduction with the →βδ-relation. List all intermediate steps until
reaching weak head normal form, but please write �t� instead of
λ g x y. if (x == 1) Nil (Cons y (g (x− 1) (y ∗ x)))
whenever possible.
c) Consider the representation of natural numbers in the pure lambda calculus presented in the lecture, i.e.,
n ∈ N is represented by the term λ f x. fn x. Give a pure lambda term for multiplication, i.e., a term
mult such that mult(λ f x. fn x)(λ f x. fm x) can be reduced to λ f x. fn·m x.
Explain your solution shortly. You may give a reduction sequence as explanation.
Solution:
a) fix (λ f x y. if (y == 0) 0 ((x ∗ y) + (f x (y − 1))))
b)
fix t 3 1
→δ (λ f. (f (fix f))) t 3 1
→β t (fix t) 3 1
→β (λx y. if (x == 1) Nil (Cons y ((fix t) (x− 1) (y ∗ x)))) 3 1
→β (λ y. if (3 == 1) Nil (Cons y ((fix t) (3− 1) (y ∗ 3)))) 1
→β if (3 == 1) Nil (Cons 1 ((fix t) (3− 1) (1 ∗ 3)))
→δ if False Nil (Cons 1 ((fix t) (3− 1) (1 ∗ 3)))
→δ (λx y. y) Nil (Cons 1 ((fix t) (3− 1) (1 ∗ 3)))
→β (λ y. y) (Cons 1 ((fix t) (3− 1) (1 ∗ 3)))
→β Cons 1 ((fix t) (3− 1) (1 ∗ 3))
c)
mult = λn m f. n (m f) or
mult = λn m f.m (n f)
The representation of m applies the function f m times to some x: (m f). This is applied n times to
some x by supplying it as the function to the representation of n. This results in n ·m applications of f
to some x, which represents n ·m.
6
Functional Programming SS16
Solution – Exam 17.08.2016
mult(λ f x. fn x)(λ f x. fm x)
→β(λm f. (λ f x. fn x) (m f))(λ f x. fm x)
→βλ f. (λ f x. fn x) ((λ f x. fm x) f)
→βλ f. (λ f x. fn x) (λx. fm x)
→βλ f. (λx. (λx. fm x)n x)
=λ f.
(
λx.
(
(λx. fm x)
(
. . . ((λx. fm x) x)
)))
→∗βλ f. (λx. f
m·n x)
=λ f x. fm·n x
Exercise 4 (Type Inference): (18 points)
Using the initial type assumption A0 := {h :: ∀a.a}, infer the type of the expression λx.h (xh) using the
algorithm W.
Solution:
W(A0, λx.h (xh))
W(A0 + {x :: b1}, h (xh))
W(A0 + {x :: b1}, h) = (id, b2)
W(A0 + {x :: b1}, x h)
W(A0 + {x :: b1}, x) = (id, b1)
W(A0 + {x :: b1}, h) = (id, b3)
mgu(b1, b3 → b4) = [b1/(b3 → b4)]
= ([b1/(b3 → b4)], b4)
mgu(b2, b4 → b5) = [b2/(b4 → b5)]
= ([b1/(b3 → b4), b2/(b4 → b5)], b5)
= ([b1/(b3 → b4), b2/(b4 → b5)], (b3 → b4)→ b5)
7