Haskell Assignment Sheet 1
An introduction to Haskell and the typed lambda calculus
Submission Instructions
Your full submission should be a single Haskell file with the following template:
You can download the template using the # button next to the file name. You can also copy any code snippet by hovering over it and clicking the ! button which appears on the top right.
Do you already have Haskell set up on your system? If so, you can skip to the questions. Otherwise, read on.
Setting Up Haskell
Nowadays, installing Haskell is painless.
1. Navigate to haskell.org/get-started. Follow the instructions there and install GHCup.
2. You will be prompted to make some decisions in the GHCup install script. Just make sure both stack and cabal are installed. I would highly recommend letting GHCup add PATH variables, installing the Haskell Language Server (HLS), and enabling better stack integration with GHCup. The remaining defaults are probably fine.
3. I recommend using VS Code as an editor, but you’re welcome to use whatever you prefer. It’s a great general purpose text editor and has good integration with the Haskell Language Server. If you are using VS Code, install the official Haskell extension.
I will assume that you are using VS Code with the Haskell extension and HLS on either Linux or Mac. If you are using something else, you should be able to adapt the following instructions to your situation.
To test if your install is working: Create a new directory and open it in VS Code. Create a file called Main.hs and copy the following into it.
You can execute this in a few different ways. The simplest is to use Haskell’s interpreter.
If you want to compile Main.hs into an executable, do this:
This will create an executable Main, but also a Main.o and Main.hi file, both of which you can ignore. +
A final note: If you follow these instructions correctly, you will have the GHC2021 language variant enabled. If, somehow, you managed to install an old variant—such as Haskell2010 or Haskell98—you should be fine, but you might need to explicitly enable some language extensions. The list of extensions enabled by default in GHC2021 is available here.
What if I can’t get Haskell working?
I can’t help you to get Haskell installed, but it might be worth trying repl.it. It’s a browser-based IDE that supports Haskell, so as long as you have a browser, you can write, compile, and run Haskell code from there. Its features are more than sufficient for this course. (It’s free, but unfortunately requires sign-up to use.)
Where are the Haskell docs?
You can visit Stackage. The search bar uses Hoogle under the hood, which you might prefer to use directly.
One useful feature is that you can search by type signature. This can help when you need a function with a particular type but are not sure what it’s called.
You should get used to consulting the documentation every so often. I can’t explicitly cover all built-in functions and features, even if they would be useful for solving problems. You will have to discover some features of Haskell on your own.
Assignment01.hs #
module Assignment01 where
———————————————————–
— QUESTION 1
———————————————————–
— QUESTION 2
———————————————————–
— QUESTION 3
———————————————————–
— QUESTION 4
Your file name and module name must match the template—any other file or module name will be rejected.
You may not use any imports to solve this lab. If your file contains an import statement, you will get zero marks.
module Main where
main :: IO ()
main = putStrLn “Hello, world!”
❯ runhaskell Main.hs Hello, world!
❯ ghc Main.hs
[1 of 1] Compiling Main ( Main.hs, Main.o ) Linking Main …
❯ ./Main Hello, world!
Here is a recursive function in Haskell which computes the exponent bn,
for b, n ∈ Z.
Rewrite this algorithm in iterative style, mirroring the examples in the first lecture. Your function need not work for n < 0.
Question 2
Consider the following program.
For which values of n, if any, does the expression facT foo n reduce to a value? Justify your answer.
Question 3
Write a function which interleaves two lists. For example, interleave [1,2,3] [4,5,6,7,8] should return [1,4,2,5,3,6,7,8].
Question 4 (Hard)
Inhabit the following term.
In other words, provide a self-contained definition for term which type- checks and does not include undefined or any other value that reduces to ⊥. Importantly, you do not need any information other than the type signature to complete this question.
Question 1
recExp :: Integer -> Integer -> Integer
recExp b n =
if n == 0 then 1
else b * recExp b (n – 1)
data T a = T (T a)
facT :: T a -> Int -> Int
facT _ 0 = 1
facT (T t) n = n * facT t (n – 1)
foo :: T a
foo = T (T (T (T (error “⊥”))))
interleave :: [a] -> [a] -> [a]
interleave = undefined
term :: ((((a -> b) -> a) -> a) -> b) -> b
term = undefined
© Conor Reynolds 2022–2023 ! ” # $ ✉
Computer Science Tutoring