Haskell lambda代写 | Functional Programming Coursework 1

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

Instructions Complete the given assignments in the file Coursework.hs . Make
sure your file 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 file 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 definition 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 first 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 find the following recursive definition 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 infinite
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 infinite list variables, which contains the variables “a” through “z”,
then repeats these suffixed 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 first 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 first 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”