Instructions Complete the given assignments in the ﬁle Coursework.hs . Make
sure your ﬁle does not have syntax errors or type errors; where necessary, comment out
partial solutions (and explain what you intended). Use the provided function names. You
may use auxiliary functions, and you are encouraged to add your own examples and tests.
Assessment and feedback Your work will be judged primarily on the correctness of your
solutions. Secondarily, incorrect or partial solutions (also when commented out) may be
given partial marks if they are well presented. Marking is part-automated, part-manual.
You will receive individual marks, and we will publish an overall feedback document.
In this coursework we will implement the lambda-calculus in Haskell. You are started off with
the following, in the ﬁle Coursework.hs.
Var: a type for variables, as a synonym of String.
Term: a data type for lambda-terms. It has three constructors, Variable, Lambda,
and Apply, which match the three cases of the deﬁnition of lambda-terms:
M ::= x j x:M j M M
example: an example lambda-term, a:x: (y: a) x b .
pretty: a function that renders a Term as a lambda-term (but with \ for ). Try it:
Lambda “a” (Lambda “x” (Apply (Apply (Lambda “y”
(Variable “a”)) (Variable “x”)) (Variable “b”)))
*Main> putStrLn (pretty example)
\a. \x. (\y. a) x b
We will ﬁrst replace the standard show function for Terms with pretty. Comment out the
line deriving Show and un-comment the two lines instance Show Term. . . .
\a. \x. (\y. a) x b
Assignment 1 (10%): Complete the function numeral which given a number i , returns
the corresponding Church numeral Ni as a Term. Recall that the Church numerals are:
N0 = f:x: x N1 = f:x: f x N2 = f:x: f (f x) : : :
You may ﬁnd the following recursive deﬁnition of the numeral Ni helpful.
Ni = f:x:N0
0 = x
= f (N0
i 1) (if i = 0)
*Main> numeral 2
\f. \x. f (f x)
Next, we will build a function that generates a fresh variable. First, we create an inﬁnite
supply of variables; then we remove those already in use. We will store used variables as
an alphabetically sorted list, with each variable mentioned at most once: we only care if
variables occur, and not how often. To help with this you are given the merge function from
the merge sort algorithm in the tutorials.
Assignment 2 (20%):
a) Complete the inﬁnite list variables, which contains the variables “a” through “z”,
then repeats these sufﬁxed with 1, “a1″,…,”z1”, then 2, “a2″,…,”z2”, etc.
*Main> [variables !! i | i <- [0,1,25,26,27,100,3039]]
b) Complete the function filterVariables which takes two lists of variables and re-
turns the ﬁrst with all variables from the second list removed from it.
*Main> filterVariables [“y”,”z”,”a1″,”a2″] [“y”,”a1″,”a3″]
c) Complete the function fresh which given a list of variables, generates a fresh variable
not occurring in the list. Use filterVariables to remove the given variables from
variables, then take the ﬁrst variable in the remaining list.
*Main> fresh [“a”,”b”,”x”]
d) Complete the function used that collects all the variable names used in a Term, both
as a Variable and in a Lambda abstraction. Return them in an ordered list (use
merge to combine two ordered lists into one).
*Main> used example
*Main> fresh it
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: firstname.lastname@example.org 微信号:vipnxx