# Haskell lambda代写 | Functional Programming Coursework 1

本次澳洲代写主要为haskell lambda计算相关的assignment

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.

**Lambda-calculus**

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:

*Main> example

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. . . .

*Main> example

\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

i

N0

0 = x

N0

i

= f (N0

i 1) (if i = 0)

*Main> numeral 2

\f. \x. f (f x)

Variables

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]]

[“a”,”b”,”z”,”a1″,”b1″,”w3″,”x116″]

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″]

[“z”,”a2″]

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”]

“c”

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

[“a”,”b”,”x”,”y”]

*Main> fresh it

“c”