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

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.