# Haskell辅导 | COMP2209 Assignment Haskell Programming Challenges

这个作业是了解Haskell函数式编程的概念，并能够以这种风格编写程序，

COMP2209 Assignment Instructions

Learning Outcomes (LOs)

• Understand the concept of functional programming and be able to write programs in this style,

• Reason about evaluation mechanisms.

Introduction

This assignment asks you to tackle some functional programming challenges associated with

interpreting, translating, analysing and parsing variations of the lambda calculus, a language which is

known to be Turing complete1

. It is hoped these challenges will give you additional insights into the

mechanisms used to implement functional languages, as well as practising some advanced functional

programming techniques such as pattern matching over recursive data types, complex recursion, and

the use of monads in parsing. Your solutions need not be much longer than a page or two, but more

thought is required than with previous programming tasks you have worked on. Each challenge is

independent so that if you find one of them difficult you can move on to the next one.

For ease of comprehension, the examples in these instructions are given in a human readable format.

To assist with your implementation a file called Challenges2019tests.hs is provided with the sample

test cases but in machine readable format so that you do not need to re-type them. This test file

imports the Challenges.hs code you are asked to develop and submit. A dummy version of

Challenges.hs is also provided which you should edit to incorporate the code you have developed.

You may and indeed should define auxiliary or helper functions to ensure your code is easy to read

and understand. You must not, however, change the signatures of the functions which are exported

from Challenges.hs for testing, nor their defined types. Likewise you may not add any third party

Import statements, so that you may only Import modules from the standard Haskell distribution. If

you make such changes, your code may fail to compile on the server used for automatic marking, and

you will lose a significant number of marks.

As well as the published test cases an additional test suite will be applied to your code during marking.

To prevent anyone from gaining advantage from special case code, this second test suite will only be

published after marking has been completed.

It is your responsibility to adhere to the instructions specifying the behaviour of each function, and

your work will not receive full marks if you fail to do so. Your code will be tested only on values

satisfying the assumptions stated in the description of each challenge, so you can implement any error

handling you wish, including none at all. Where the specification allows more than one possible result,

any such result will be accepted. When applying the tests it is possible your code will run out of space

or time. A solution which fails to complete a test suite for one exercise within 30 seconds on the test

server will be deemed to have failed that exercise, and will only be eligible for partial credit. Any

1 Church showed how to encode integer arithmetic and Booleans as pure lambda expressions; combinators

which enable recursive definitions to be encoded were invented by Turing and Curry, among others.

reasonably efficient solution should take significantly less time than this to terminate on the actual

test data that will be supplied.

Depending on your proficiency with functional programming, the time required for you to implement

and test your code is expected to be 5 to 10 hours per challenge. If you are spending much longer

than this, you are advised to consult the teaching team for advice on coding practices.

Note that this assignment involves slightly more challenging programming compared to the previous

functional programming exercises. You may benefit, therefore, from the following advice on

debugging and testing Haskell code:

https://wiki.haskell.org/Debugging

https://www.quora.com/How-do-Haskell-programmers-debug

http://book.realworldhaskell.org/read/testing-and-quality-assurance.html

It is possible you will find samples of code on the web providing similar behaviour to these

challenges. Within reason, you may incorporate, adapt and extend such code in your own

implementation. Warning: where you make use of code from elsewhere, you must acknowledge and

cite the source(s) both in your code and in the bibliography of your report. Note also that you cannot

expect to gain full credit for code you did not write yourself, and that it remains your responsibility to

ensure the correctness of your solution with respect to these instructions.

Lambda Calculus and Let Expressions

You should start by reviewing the material on the lambda calculus given in lectures 12, 13 and 14. You

may also review the wikipedia article, https://en.wikipedia.org/wiki/Lambda_calculus, or Selinger’s

notes http://www.mscs.dal.ca/~selinger/papers/papers/lambdanotes.pdf, or both.

The simplest lambda notation uses a syntax such as λx -> e where x is a variable and e another lambda

expression. In this notation, the lambda expression has only one formal argument or

parameter. Application of a lambda function is written here the same way as in Haskell, with the

function followed by its actual argument, which is also known as juxtaposition. Lambda expressions

may be nested, for example: λx -> λy -> e.

You will be using the following data type for the abstract syntax of this notation:

data LamExpr =

LamApp LamExpr LamExpr | LamAbs Int LamExpr | LamVar Int deriving (Show, Eq)

It is assumed here that each variable is represented as an integer using some numbering scheme. For

example, it could be required that each variable is written using the letter x immediately followed by

a natural number, such as for example x0, x1, and x456. These are then represented in the abstract

syntax as Var 0, Var 1, and Var 456 respectively. Likewise, for example, the lambda expression λx1 ->

x2 x1 is represented as LamAbs 1 (LamApp (Var 2) (Var 1)). Representing variables using integers

rather than strings makes it is easier to generate a fresh variable that has not been already used

elsewhere.

The let notation can also be used to define a function but without the need for any Greek letter or

arrow. For example let f x = e, and let f x y = e are both let expressions that define a function f. A let

expression can also be applied, for example let f x = e in f y. Multiple let expressions can also be

defined simultaneously by separating them with a semi-colon, for example let f x = e; y = d in f y. To

make this notation seem more concrete, numeric literals are allowed in these expressions, albeit these

will also interpreted as just another shorthand for a lambda expression.

The let expressions used in this assignment have the following concrete syntax (expressed in BNF):

Expr ::= Num | Var | Fun | Expr Expr | “let” EqnList “in” Expr | “(“ Expr “)”

EqnList ::= Eqn | EqnList “;” Eqn

Eqn ::= Fun VarList “=” Expr

Fun ::= “f” Digits

VarList ::= Var | Var VarList

Var ::= “x” Digits

Num ::= Digits

Digits ::= Digit | Digits Digit

Digit ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”

As with the lambda expressions above, variable and function names in these let expressions are

represented numerically (x0, x1, x2, … and f0, f1, f2, … respectively) to simplify processing.

You will be using the following data type for the abstract syntax of this notation:

data LetExpr =

LetApp LetExpr LetExpr | LetDef [([Int], LetExpr)] LetExpr | LetFun Int | LetVar Int |

LetNum Int deriving (Show, Eq)

It is assumed in these challenges that application associates to the left and binds tighter than any other

operator in both of the notations used here.

Functional Programming Challenges

Challenge 1: Converting a Lambda Calculus Expression to Alpha Normal Form

The first challenge requires you to write a function to convert a lambda expression to an alpha

equivalent one and return this value. In general, there would be many possible answers. For example,

λx0 -> λx1 -> x0 is alpha equivalent to λx1 -> λx -> y. Your function however must construct an answer

in which each bound variable uses the first available identifier. Note that variable numbering starts

at 0. The first lambda expression above is therefore in alpha normal form, according to the definition

given here, whereas the second is not. Care is required to avoid hiding a variable unintentionally. For

example, in the expression λx0 -> λx1 -> λx2 -> x0, you cannot rename x1 to x0 as this would bind the

later occurrence of x0 to the wrong lambda abstraction. On the other hand, you can safely rename x2

to x1 as x1. Your implementation should have the property that two alpha equivalent expressions have

the same alpha normal form. Here are some examples of this alpha normal form:

Lambda term Alpha Normal Form

x1 x0 x1 x0

λx3 -> x2 λx0 -> x2

λx0 -> λx1 -> x0 λx0 -> λx1 -> x0

λx1 -> λx0 -> x1 λx0 -> λx1 -> x0

λx1 -> λx0 -> x0 λx0 -> λx0 -> x0

λx0 -> λx1 -> λx2 -> x0 λx0 -> λx1 -> λx1 -> x0

Challenge 2: Counting Lambda Calculus Reductions

For this challenge you will program beta reduction of a lambda expression using all possible strategies.

In general a lambda expression may contain more than reducible (sub-)expression (redex). There are

therefore many different possible reduction sequences. We are interested here only in reduction

sequences that lead to an expression without any redexes, that is to say in beta normal form. The

famous Church-Rosser theorem states that any two such end results will be the same, or at least alpha

equivalent, lambda expressions. Note however that lambda reduction may not terminate, and

moreover that some reduction sequences will be longer than others.

For example, the lambda expression whose concrete syntax is shown below has two reducible

expressions, which are indicated by the underlined text: (λx -> λy -> x) z ((λt -> t) u). One reduction

sequence is therefore:

(λx -> λy -> x) z ((λt -> t) u)

(λy -> z) ((λt -> t) u)

z

and another one is:

(λx -> λy -> x) z ((λt -> t) u))

(λx -> λy -> x) z u

(λy -> z) u

z

You are asked to program a function which counts the number of different reduction sequences up to

a given maximum length, starting with the given lambda expression and ending with a beta normal

form that cannot be reduced further, and returns this count. Examples of this function are:

Lambda expression Maximum Count of All Different Reduction Sequences

λx -> (λy -> y) 0 0 – as no reduction sequence is this short

λx -> (λy -> y) 1 1 – one singleton sequence containing this

expression

λx -> (λy -> y) 2 1 – no other reduction sequences exist

(λx -> x)(λy -> y) 0 0

(λx -> x)(λy -> y) 1 0 – this expression is not in beta normal form yet

(λx -> x)(λy -> y) 2 1 – one reduction step gives a sequence of length 2

(λx -> λy -> x) z ((λt -> t) u) 2 0

(λx -> λy -> x) z ((λt -> t) u) 3 1

(λx -> λy -> x) z ((λt -> t) u) 4 3 – three reduction sequences of length up to 4 exist

Challenge 3: Pretty Printing a Lambda Expression

You are asked to write a “pretty printer” to display a simple lambda expression. Your output should

produce a syntactically correct expression. In addition, your solution should omit brackets where

these are not required. That is to say, omit brackets when the resulting string represents the same

abstract expression as the original one. Finally, your function should recognise a lambda expression

or sub-expression alpha equivalent to the Scott encoding of a natural number, and print the

corresponding numeral rather than the lambda expression. Use the encoding in which2

0 is represented by λx -> λy -> x

1 is represented by λx -> λy -> y (λx -> λy -> x)

2 is represented by λx -> λy -> y (λx -> λy -> y (λx -> λy -> x)), and so on.

2 You may find slight variations elsewhere in the literature, since Scott did not formally publish his encoding. See

the article Programming in the λ-calculus: from Church to Scott and back (Jansen 2013, The Beauty of Functional

Code, Springer) for further explanations and discussion of this encoding and others.

In your output, use the backslash character to stand for the λ symbol. Beyond that you are free to

format and lay out the expression as you choose in order to make it shorter or easier to read or both.

Some examples of pretty printing are:

LamApp (LamVar 2) (LamVar 1) “x2 x1”

LamApp (LamAbs 1 (LamVar 1)) (LamAbs 1 (LamVar 1)) “(λx1 -> x1) λx1 -> x1”

LamAbs 1 (LamApp (LamVar 1) (LamAbs 1 (LamVar 1))) “λx1 -> x1 λx1 -> x1”

LamAbs 1 (LamAbs 2 (LamVar 1)) “0”

LamAbs 1 (LamAbs 1 (LamApp (LamVar 1) (LamAbs 1

(LamAbs 2 (LamVar 1)))))

“1”

Challenge 4: Parsing Let Expressions

You are asked to write a parser for the let expressions defined by the BNF grammar above. You are

recommended to adapt the monadic parser examples published by Hutton and Meijer. You should

start by reading the monadic parser tutorial by Hutton in Chapter 13 of his Haskell textbook, or the

on-line tutorial below:

http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf on-line tutorial

Your parser will have the type signature String -> Maybe LetExpr and will return Nothing if the given

string does not parse correctly according to the rules of the grammar. The grammar and LetExpr data

type are defined on page 3 of these instructions. Note that you will need to transform the grammar

into an equivalent form without left recursion, as this grammar construct results in a non-terminating

parser. Some examples of the parsing function are:

“let x1 = x2” Nothing — syntactically invalid wrt the given grammar

“x1 (x2 x3)” Just (LetApp (LetVar 1) (LetApp (LetVar 2) (LetVar 3)))

“x1 x2 x3” Just (LetApp (LetApp (LetVar 1) (LetVar 2)) (LetVar 3))

“let f1 x1 = x2 in f1 x1” Just (LetDef [([1,1], LetVar 2)] (LetApp (LetFun 1) (LetVar 1)))

“let f1 x2 = x2; f2 x1 = x1 in f1 x1” Just (LetDef [([1,2],LetVar 2),([2,1],LetVar 1)] (LetApp (LetFun 1)

(LetVar 1)))

Challenge 5: Converting a Let Expression to Lambda Calculus

The challenge requires you to convert a let expression into a lambda calculus expression. The lambda

expression will be represented using the following data type defined on page 2 of these instructions.

This challenge concerns parallel and recursive let definitions, so conversion can be quite complex. The

description below builds up step by step to the full algorithm.

First consider a simple let expression without any use of recursion or parameters

let f = e in d

Here any occurrence of f in d is to be replaced by e, which can be represented using the notation

d [ f := e ]

This substitution can also be expressed directly in the lambda calculus as

(λf -> d) e

The next step, involves a let expression including a parameter or parameters, for example

let f x y = e in d

This can be expressed as a simple let by defining f as an abbreviation for a lambda expression

let f = (λx -> λy -> e) in d

Hence by the simple let conversion rule above, the equivalent lambda expression is

(λf -> d) (λx -> λy -> e)

Note that this is equivalent, using the substitution notation above, to

d [ f := λx -> λy -> e ]

Now consider a recursive definition. Here it is recommended to use the trick described by Jansen

(2013, op. cit.) to replace the recursion with self-application3

let f x = e in d

Assume that f occurs free in d and e. This can nonetheless be reduced to a lambda expression via

let f’ = λf -> λx -> e[ f := f f] in

d [ f := f’ f’]

Using the approach described previously and eliminating the resulting substitutions will result in a

lambda calculus expression.

Finally, consider mutually recursive definitions of f and g.

let f x = e; g y = h; in d

These can be converted to

let f’ = λf -> λg -> λx -> e [ f := f f g || g := g f g ]

g’ = λf -> λg -> λy -> h [ f := f f g || g := g f g ]

in

d [ f := f’ f’ g’ || g := g’ f’ g’]

where || is a parallel substitution4

. Note that with care parallel substitution can be implemented by

a sequence of simple substitutions, resulting once more in a lambda calculus expression, or you may

choose to implement it directly. Note also that three or more mutually recursive functions can be

converted in a similar way.

Here are some examples of the letToLambda conversion function:

let f0 = f0 in f0 (λx0 -> x0 x0) λx0 -> x0 x0

let f1 x2 = x2 in f1 (λx0 λx0 -> x0) λx0 λx0 -> x0

let f1 x2 x3 = x3 x2 in f1 λx0 -> λx1 -> x1 x0

let f0 x0 = f1; f1 x1 = x1 in f0 λx0 -> λx1 -> x1

let f0 x0 x1 = x0; f1 x1 = f0 x1 f1 in f1 λx0 -> x0

Note that there are multiple possible answers, and that this table gives only one possibility in each

case. Your solution may produce different results and they will be marked correct so long as they are

beta equivalent to the lambda expressions above. (Some of the results above have been beta reduced

for brevity.)

Challenge 6: Converting Lambda Calculus to Let Expressions

This final challenge asks you to perform the reverse conversion by writing a function which takes a

lambda expression and returns an equivalent let expression. This quite easy to do if each lambda

abstraction can be converted locally. An additional constraint, however, is that the returned let

expression can have only one let definition block, which must occur at the topmost level. Hence all

functions defined in this block are global. There are various techniques you might use, such as the

ones found in the lambda calculus section of the Wikipedia article covering lambda lifting in different

3 An alternative is to use the Y fixed point combinator, which is also shown in Jansen’s paper. You may use this

solution if you prefer; it is more widely known and written about.

4 Parallel substitutions occur simultaneously. For example (a b)[a := b || b := a] simplifies to (b a). This

simplification can occur through a sequence of standard substitutions: (a b)[a := c][b := a][c := b].

notations: https://en.wikipedia.org/wiki/Lambda_lifting. Take care with your choice of individual

transformation steps to ensure that the overall conversion process works correctly.

Some examples of the lambdaToLet conversion function are:

λx0 -> x0 let f0 x0 = x0 in f0

x1 λx0 -> x0 let f0 x0 = x0 in x1 f0

(λx0 -> x0) x1 let f0 x0 = x0 in f0 x1

(λx0 -> x0) (λx0 -> x0) let f0 x0 = x0; f1 x0 = x0 in f0 f1

λx0 -> x0 λx1 -> x0 x1 let f0 x0 x1 = x0 x1; f1 x0 = x0 (f0 x0) in f1

As with the previous challenge, there are multiple correct answers. Your solution will be accepted as

passing the test provided its results are equivalent to those given above.

Implementation, Test File and Report

In addition to your solutions to these programming challenges, you are asked to submit an additional

Tests.hs file with your own tests, and a report.

You are expected to test your code carefully before submitting it. Your Tests.hs file may incorporate

and enhance the published Challenges2019tests.hs test cases and main function.

Your report should include an explanation of how you implemented and tested your solutions, which

should be up to 1 page (400 words). Note that this report is not expected to explain how your code

works, as this should be evident from your code itself together with any comments you have included

where necessary and appropriate. Instead you should cover the development and testing tools and

techniques you used, and comment on their effectiveness.

Your report should include a second page with a bibliography listing the source(s) for any fragments

of code written by other people that you have adapted or included directly in your submission.

Submission and Marking

Your Haskell solutions should be submitted as a single plain text file Challenges.hs. Your tests should

also be submitted as a plain text file Tests.hs. Finally, your report should be submitted as a PDF file,

Report.pdf.

The marking scheme is given in the appendix below. There are up to 5 marks for your solution to each

of the programming challenges, up to 5 for your explanation of how you implemented and tested

these, and up to 5 for your coding style. This gives a maximum of 40 marks for this assignment, which

is worth 40% of the module.

Your solutions to these challenges will be subjected to automated testing, so it is important you

adhere to the type definitions and type signatures given in the supplied dummy code file, and that

you do not change the list of functions and types exported by this file. Your code will be run using a

command line such as ghci –e “main” Challenges2019tests.hs, and you should check before you

submit that your solution compiles and runs as expected. The supplied Parsing.hs file will be present

so it is safe to Import this, and any library included in the standard Haskell distribution, but not third

party ones. Note that the comp2209 virtual machine is running the Glorious Glasgow Haskell

Compilation System version 7.6.3. Your own test cases will also be run using a similar command line,

so make sure these define a suitable main function which runs your tests and reports the results.

Appendix: Marking Scheme

Grade Functional Correctness Readability and Coding Style Development & Testing

Excellent

5 / 5

Your code passes the supplied

test cases and all the additional

tests we ran; anomalous inputs

are detected and handled

appropriately

You have clearly mastered this

programming language, libraries and

paradigm; your code is very easy to

read and understand; excellent

coding style

Proficient use of a range of

development & testing tools and

techniques correctly and

effectively to design, build and

test your software

Very Good

4 / 5

Your code passes the supplied

test cases and almost all the

additional tests we ran

Very good use of the language and

libraries; code is easy to understand

with very good programming style,

with only minor flaws

Very good use of a number of

development & testing tools and

techniques to design, build and

test your software

Good

3 / 5

Your code passes the supplied

test cases and some of the

additional tests we ran

Good use of the language and

libraries; code is mostly easy to

understand with good programming

style, some improvements possible

Good use of development &

testing tools and techniques to

design, build and test your

software

Acceptable

2 / 5

Your code passes some of the

supplied test cases; an

acceptable / borderline attempt

Acceptable use of the language and

libraries; programming style and

readability are borderline

Adequate use of development &

testing tools and techniques but

not showing full professional

competence

Poor

1 / 5

Your code compiles but does not

run; you have attempted to code

the required functionality

Poor use of the language and

libraries; coding style and readability

need significant improvement

Some use of development &

testing tools and techniques but

lacking professional competence

Inadequate

0 / 5

You have not submitted code

which compiles and runs; not a

serious attempt

Language and libraries have not

been used properly; expected

coding style is not used; code is

difficult to read

Inadequate use of development

tools and techniques; far from

professional competence

Guidance on Coding Style and Readability

Authorship You should include a comment in a standard format at the start of your code identifying you as the

author, and stating that this is copyright of the University of Southampton. Where you include any

fragments from another source, for example an on-line tutorial, you should identify where each of

these starts and ends using a similar style of comment.

Comments If any of your code is not self-documenting you should include an appropriate comment. Comments

should be clear, concise and easy to understand and follow a common commenting convention. They

should add to rather than repeat what is already clear from reading your code.

Variable and Function

Names

Names in your code should be carefully chosen to be clear and concise. Consider adopting the naming

conventions given in professional programming guidelines and adhering to these.

Ease of

Understanding and

Readability

It should be easy to read your program from top to bottom. This should be organised so that there is

a logical sequence of functions. Declarations should be placed where it is clear where and why they

are needed. Local definitions using let and where improve comprehensibility.

Logical clarity Functions should be coherent and clear. If it is possible to improve the re-usability of your code by

breaking a long block of code into smaller pieces, you should do so. On the other hand, if your code

consists of blocks which are too small, you may be able to improve its clarity by combining some of

these.

Maintainability Ensure that your code can easily be maintained. Adopt a standard convention for the layout and

format of your code so that it is clear where each statement and block begins and ends, and likewise

each comment. Where the programming language provides a standard way to implement some

feature, adopt this rather than a non-standard technique which is likely to be misunderstood and more

difficult to maintain. Avoid “magic numbers” by using named constants for these instead.

Andy Gravell, December 2019