Functional Programming SS16
Solution – Exam 19.09.2016
aaProf. Dr. J. Giesl D. Korzeniewski
Exercise 1 (Programming in Haskell): (7 + 7 + 5 + 18 = 37 points)
We de�ne a polymorphic data structure Maze to represent a maze (i.e., a labyrinth) that can contain treasures
and traps. The data structure Discovery is used to represent traps and treasures.
data Maze a data Discovery
= Intersection (Maze a) (Maze a) = Trap String
| Corridor a (Maze a) | Treasure
| DeadEnd a
| Exit
For example, aMaze is a valid expression of type Maze Discovery.
aMaze = Intersection (Corridor (Trap “a trap door”) (DeadEnd Treasure))
(Intersection (DeadEnd Treasure) Exit)
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 buildMaze :: Int -> Maze Int that gets a random seed as input.
The call (buildMaze seed) for an integer seed should create a maze according to the following rules:
• with probability 1
5
the function returns Exit
• with probability 1
5
the function returns a DeadEnd with a random number as argument
• with probability 1
5
the function returns a Corridor with a random number and a random submaze
• with probability 2
5
the function returns an Intersection with two random submazes, which di�er
with high probability (i.e., they are constructed from di�erent seeds)
Hints:
• You are given a function rand :: Int -> Int which creates a new uniformly distributed (pseudo)
random number from an input number, the seed. Already a small di�erence in the seed creates very
di�erent results (i.e., the sequence produced by consecutive calls (rand seed) and (rand (seed+1))
is reasonably random). Also using a previous random number as new seed produces reasonably ran-
dom sequences.
For each decision during the generation, for each number inserted into the maze, and for each
submaze a new random number should be used. So for any integer seed never use (rand seed)
twice in a computation.
• To get a result with a certain probability, you should generate a (pseudo) random number and
perform an appropriate case analysis depending on the value of this random number.
b) Implement a function mapMaze which gets a function and a maze as input. It should return a maze,
where the function is applied to each element stored in the maze. For example, if it gets a function
even :: Int -> Bool and a maze of type Maze Int, it should return a maze where we have True at
each position where there was an even number in the input maze.
Also give a reasonable type declaration for the function!
c) Implement a function populateMaze :: Maze Int -> Maze Discovery which takes a maze as returned
by buildMaze from part a) and returns a maze �lled with di�erent Discoveries which depend on the
numbers that were in the maze before. The function should replace even numbers with
(Trap “a trap door”) and odd numbers by a Treasure.
Hints:
You may use mapMaze from the previous task (even if you have not solved the previous task).
d) In this part of the exercise, you should implement a small game where you control an adventurer who
explores a Maze Discovery.
1
Functional Programming SS16
Solution – Exam 19.09.2016
1) Implement a function react :: Discovery -> Int -> IO Int that handles the reaction to a
Discovery. It gets a Discovery and the number of already collected treasures as input. For traps
it should output a message indicating that a trap was reached including the String of the trap and
that all treasures were lost. So the result in this case is 0, wrapped in the IO monad. For treasures,
it should print that a treasure was found and the new number of treasures collected. The result in
this case is the input number incremented by one, wrapped in the IO monad.
Hints:
• 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.
2) Implement a function exploreMaze :: Maze Discovery -> [Maze Discovery] -> Int -> IO ().
This function is the main loop of the game. The �rst input parameter is the maze in front of the
adventurer, the second parameter is the current path of Intersections back to the starting point,
and the third parameter is the number of already collected treasures.
At an Intersection the user gets asked for input, the possibilities are l for left, r for right, or b for
back. Depending on the input, the exploration should continue at the �rst (left) or second (right)
argument of the Intersection, or for input b at the �rst Intersection in the list of exploreMaze’s
second input parameter.
At a Corridor or DeadEnd, �rst react should be called and after that, the exploration continues either
at the following maze or, in case of a DeadEnd, at the �rst Intersection in the list of exploreMaze’s
second input parameter.
At an Exit, the user gets a message which indicates that the adventurer escaped the maze and prints
the number of treasures collected.
During the main loop you should always update the current path back to the starting point if you
move out of an Intersection and the function react from 1) can help you to update the current
number of treasures.
We assume that one can also escape the maze via the entrance. So, whenever the adventurer should
go back, either because of a DeadEnd or the user input b, but the list in the second input parameter
is empty, the function should behave as if an Exit was encountered.
A run might look as follows:
*Main> exploreMaze aMaze [] 0
Go left, right, or back? (l|r|b) l
You reached a trap door and lost your treasures!
You found another treasure! You now have 1 treasures.
Go left, right, or back? (l|r|b) l
You reached a trap door and lost your treasures!
You found another treasure! You now have 1 treasures.
Go left, right, or back? (l|r|b) r
Go left, right, or back? (l|r|b) l
You found another treasure! You now have 2 treasures.
Go left, right, or back? (l|r|b) b
Go left, right, or back? (l|r|b) r
Go left, right, or back? (l|r|b) r
You escaped the maze with 2 treasures.
Hints:
• You should use the function getChar :: IO Char to read a character input from the user.
• You do not have to handle wrong user input correctly, i.e., you may assume that the user will only
supply valid input.
• You do not have to pay attention to output formating (spaces, line breaks).
• You do not have do modify the maze, e.g, if treasures are found they are not removed but may be
collected multiple times.
2
Functional Programming SS16
Solution – Exam 19.09.2016
Solution:
a) buildMaze :: Int -> Maze Int
buildMaze seed | m5 == 0 = Exit
| m5 == 1 = DeadEnd (rand (seed+1))
| m5 == 2 = Corridor (rand (seed+1)) (buildMaze (seed+2))
| otherwise = Intersection (buildMaze (seed+1)) (buildMaze (seed+2))
where m5 = (rand seed) `mod` 5
b) mapMaze :: (a -> b) -> Maze a -> Maze b
mapMaze f (Intersection left right) = Intersection (mapMaze f left) (mapMaze f right)
mapMaze f (Corridor a maze) = Corridor (f a) (mapMaze f maze)
mapMaze f (DeadEnd a) = DeadEnd (f a)
mapMaze _ _ = Exit
c) populateMaze :: Maze Int -> Maze Discovery
populateMaze maze = mapMaze populate maze
where populate x | even x = Trap “a trap door”
| otherwise = Treasure
d) 1) react :: Discovery -> Int -> IO Int
react (Trap s) t = do
putStrLn (“You reached “++s++” and lost your treasures!”)
return 0
react Treasure t = do
putStrLn (“You found another treasure! You now have “++(show t)++” treasures.”)
return (t+1)
2) exploreMaze :: Maze Discovery -> [Maze Discovery] -> Int -> IO ()
exploreMaze (Intersection left right) ms t = do
putStr “Go left, right, or back? (l|r|b) ”
input <- getChar putStrLn "" case input of 'l' -> exploreMaze left ((Intersection left right):ms) t
‘r’ -> exploreMaze right ((Intersection left right):ms) t
‘b’ -> exploreMaze (head’ ms) (tail ms) t
where head’ [] = Exit
head’ (x:xs) = x
exploreMaze (Corridor a m) ms t = do
new_t <- react a t exploreMaze m ms new_t exploreMaze (DeadEnd a) ms t = do new_t <- react a t exploreMaze (head' ms) (tail ms) new_t where head' [] = Exit head' (x:xs) = x exploreMaze Exit _ t = do putStrLn ("You escaped the maze with "++(show t)++" treasures.") 3 Functional Programming SS16 Solution - Exam 19.09.2016 Exercise 2 (Semantics): (17 + 12 + 9 = 38 points) a) i) Prove or disprove continuity for each of the functions f, g : (Z⊥ → Z⊥)→ Z⊥ f(h) = { 0 if h(0) = 0 ⊥ otherwise g(h) = { 0 if h(x) = 0 holds for all x ∈ Z⊥ ⊥ otherwise If you want to make use of the fact that computable functions are continuous, give an implementation of the function and an argument for the correctness of the implementation. ii) Let L denote the set of all Haskell lists of type [Int]. For example [1, 3, 5, 5, 2], [1, 2, 3, 2, 1], and the in�nite list [3, 6, 9, 12, . . . ] are contained in L. Let ` ∈ L. We de�ne s : L→ N∪{∞} where s(`) is the length of the longest pre�x of ` that is sorted in ascending order. For example s([1, 3, 5, 5, 2]) = 3, s([4, 3, 1]) = 1, and s([3, 6, 9, 12, . . . ]) =∞ Let ≤sort ⊂ L×L be the partial order de�ned as `1 ≤sort `2 if and only if s(`1) < s(`2) or `1 = `2. Here, we have n <∞ for every n ∈ N, but ∞ ≮∞. Prove or disprove each of the following statements: 1) There is an in�nite chain in (L,≤sort). 2) The order ≤sort is complete on L. 3) The order ≤sort is con�uent. b) i) Consider the following Haskell function f: f :: (Int, Int) -> Int
f (x, 0) = x
f (x, y) = y * f (x, y – 1)
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 Maze a
= C a (Maze a)
| D a
| E
data Discovery
= Tp String | Ts
⊥
Z 2nd level
3rd level
1st level
S Z S (S ⊥)
S ⊥
4
Functional Programming SS16
Solution – Exam 19.09.2016
Give a graphical representation of the �rst three levels of the domain for the type Maze Discovery.
Solution:
a) i) The function f is continuous. Let C = {hi | i ∈ N} ⊂ Z⊥ → Z⊥ be a chain. Either there is an i
such that hi(0) = 0, then also for all j > i, hj(0) = 0 and thus (tC)(0) = 0. Hence, f(tC) = 0
and tf(C) = t{⊥, 0} = 0. Otherwise for all i we have hi(0) 6= 0 and thus (tC)(0) 6= 0. Hence,
f(tC) = ⊥ and tf(C) = t{⊥} = ⊥.
The function g is not continuous. Let C ′ = {h′i | i ∈ N} where h
′
i(x) = 0 i� x < i or x = ⊥, else
h′i(x) = ⊥. For all hi ∈ C
′, g(hi) = ⊥ but tC ′ is the constant function 0, so g(tC ′) = 0 6= tg(C ′) =
t{⊥} = ⊥.
ii) 1) C = {[1, 2, 1, 1, . . . ], [1, 2, 3, 1, 1, . . . ], [1, 2, 3, 4, 1, 1, . . . ], . . . } is an in�nite chain.
2) The relation ≤sort is not a cpo. A relation ≤sort is a cpo i� L has a least element w.r.t. ≤sort
and every ≤sort-chain has a least upper bound in L. Obviously, the least element is the empty
list [ ]. Consider C, de�ned as above. Obviously every sorted, in�nite list is an upper bound.
But as sorted, in�nite lists are incomparable w.r.t. ≤sort, there is no least upper bound.
3) The relation ≤sort is not con�uent. We have [ ] ≤sort [1, 2, 3, . . . ] and [ ] ≤sort [2, 4, 6, . . . ], but
all in�nite, sorted lists are incomparable. Thus, there is no q such that [1, 2, 3, . . . ] ≤sort q and
[2, 4, 6, . . . ] ≤sort q.
b) i) ff :: ((Int, Int) -> Int) -> ((Int, Int) -> Int)
ff f (x, 0) = x
ff f (x, y) = y * f (x, y – 1)
ii)
(φnff(⊥))(x, y) =
{
y! · x if 0 ≤ y < n ∧ x 6= ⊥
⊥ otherwise
iii)
(lfp φff)(x, y) =
{
y! · x if 0 < y ∧ x 6= ⊥
⊥ otherwise
c)
C Ts ⊥ D (Tp ⊥)
C ⊥ ⊥
C (Tp ⊥) ⊥
⊥
E
D TsC ⊥ EC ⊥ (D ⊥)C ⊥ (C ⊥ ⊥)
D ⊥
Exercise 3 (Lambda Calculus): (9 + 10 + 6 = 25 points)
a) Consider the following Haskell function:
5
Functional Programming SS16
Solution - Exam 19.09.2016
len :: List a -> Int
len Nil = 0
len (Cons x xs) = 1 + len xs
Here Cons and Nil are the list constructors as de�ned in the lecture.
Please give an equivalent function in simple Haskell. Here, you can of course use prede�ned functions
like isa_Nil, argof_Cons, and sel_n_k. Additionally, implement the function in the lambda calculus,
i.e., give a lambda term q such that, for all lists list and y ∈ Z, y is the length of list if and only
if len list can be reduced to y 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 (+).
You do not have to use the transformation algorithms presented in the lecture. It is su�cient to just
give an equivalent simple program and an equivalent lambda term.
b) Let
t = λ g x y. if (x ∗ y == 0) y (g x (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}
Please reduce fix t 3 0 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 ∗ y == 0) y (g x (y + x))
whenever possible.
c) Consider λx.x a b as a representation of pairs of values (a, b) in pure lambda calculus.
Give a de�nition for a pure lambda term apply which applies a given term f to both elements of a
pair, i.e., apply f (λx.x a b) →∗β λx.x (f a), (f b)) should hold. You may use the shorthand notations
True = λx y.x and False = λx y.y in your solution.
Explain your solution shortly!
Solution:
a) len = \xs -> if (isa_Nil xs) then 0 else
(if (isa_Cons xs) then (1 + sel_2_2 (argof_Cons xs) else bot)
fix (λ f xs. if (isaNil xs) 0 (if (isaCons xs) (1 + f (sel2,2 (argofCons xs))) (bot))
Alternatively:
len = \xs -> if (isa_Nil xs) then 0 else
(1 + sel_2_2 (argof_Cons xs))
6
Functional Programming SS16
Solution – Exam 19.09.2016
fix (λ f xs. if (isaNil xs) 0 (1 + f (sel2,2 (argofCons xs))))
b)
fix t 3 0
→δ (λ f. (f (fix f))) t 3 0
→β t (fix t) 3 0
→β (λx y. if (x ∗ y == 0) y ((fix t) x (y + x))) 3 0
→β (λ y. if (3 ∗ y == 0) y ((fix t) 3 (y + 3))) 0
→β if (3 ∗ 0 == 0) 0 ((fix t) 3 (0 + 3))
→δ if (0 == 0) 0 ((fix t) 3 (0 + 3))
→δ if True 0 ((fix t) 3 (0 + 3))
→δ (λx y. x) 0 ((fix t) 3 (0 + 3))
→β (λ y. 0) ((fix t) 3 (0 + 3))
→β 0
c)
apply = λ f p. λ x. x (f (p True)) (f (p False))
Using True and False we can select the �rst and second element of the pair respectively. Inside the
template for a new pair the function f is applied to each element of the pair individually.
Exercise 4 (Type Inference): (20 points)
Using the initial type assumption A0 := {f :: ∀a.(a→ List a)}, infer the type of the expression f (λx.f x)
using the algorithm W.
Indicate the computed most general type or explain the problem the algorithm encounters if the expression is
not well typed.
Solution:
W(A0, f (λx.f x))
W(A0, f) = (id, b1 → List b1)
W(A0, λx.f x)
W(A0 + {x :: b2}, f x)
W(A0 + {x :: b2}, f) = (id, b3 → List b3)
W(A0 + {x :: b2}, x) = (id, b2)
mgu(b3 → List b3, b2 → b4) = [b2/b3, b4/List b3]
= ([b2/b3, b4/List b3], List b3)
= ([b2/b3, b4/List b3], b3 → List b3)
7
Functional Programming SS16
Solution – Exam 19.09.2016
mgu(b1 → List b1, (b3 → List b3)→ b5) = [b1/(b3 → List b3), b5/List (b3 → List b3)]
([b2/b3, b4/List b3, b1/(b3 → List b3), b5/List (b3 → List b3)], List(b3 → List b3))
8