In your Haskell file this week, we recommend hiding some functions from the predefined Prelude module. This module include many standard functions and is imported by default in all Haskell files. As we will be implementing our own version of some of these functions, hiding the existing function will avoid ambiguity. You can do this by adding an explicit import line at the start of your file using the following syntax:

import Prelude hiding (length, sum, product, zip, take, repeat, cycle, (++))

1 Pattern Matching on Lists

Using pattern matching, define the following functions:

1.1. A function headOrZero :: [Int] → Int, which returns the first element of a list or 0 if it is empty.

1.2. A function length :: [Int] → Int, which returns the number of elements in a given list.

1.3. A function sum :: [Int] → Int, which returns the summation of all the elements in the list and 0 if the list is

empty.

1.4. A function product :: [ Int ] → Int, which multiplies all the elements in the list together. Make sure to pick an appropriate base case for the empty list!

1.5. Define a function snoc :: Int → [Int] → [Int] which adds an element to the end of a list. (We call it snoc because it’s the opposite of (:) a.k.a. “cons”, which adds an element to the front of a list.)

For example, snoc 2 [1, 3] = [1, 3, 2].

1.6. Implement the function take :: Int → [Int] → [Int] such that take n xs only returns the first n elements of

the input list. For example: take 3 [1, 2, 3, 4, 5] = [1, 2, 3].

1.7. Define a function insert :: Int → [Int] → [Int] that, given an element x and a sorted input list xs in as- cending order, produces another sorted list with x inserted into the correct position in xs. If the element is already present in the list, it should appear an additional time. For example, insert 2 [1,3] = [1,2,3] and insert 3 [1,3] = [1,3,3].

† 1.8.

1.9. Define a function merge :: [Int] → [Int] → [Int] that takes two lists xs and ys that are sorted in ascending

Use the insert defined in the previous question to implement the function isort :: [Int] → [Int] which sorts an arbitrary input list in ascending order. For example, isort [ 2, 3, 1, 2 ] = [ 1, 2, 2, 3 ].

order, and produces another list containing all their elements in ascending order.

1.10. Define a function zip :: [ Int ] → [ Int ] → [ (Int, Int) ] that takes two input lists and returns a list which pairs up the corresponding element of the lists. For example, zip [2, 3, 1] [1, 4, 4] = [(2, 1), (3, 4), (1, 4)]. What does your function do when the lists differ in length?

2 List Comprehension

Many problems concerning lists can be expressed using list comprehension. Remember you should be reading Learn You A Haskell alongside this course. If you haven’t already done so, work through the sections on ranges and list comprehensions now.

2.1. Using a list comprehension and a range, define a function squaresUpto :: Int → [Int] which, given an n, returns the list of all the square numbers up to and including the nth square number. For example, squaresUpto 3 = [0, 1, 4, 9]

2.2. Define a function odds :: Int → [Int], which lists the positive odd numbers less than or equal to the input number.

2.3. Implement the function orderedPairs :: [ Int ] → [ (Int, Int) ] which returns all pairs of elements (x, y) taken from its input list such that x < y. For example, orderedPairs [ 3, 4, 1 ] = [ (1, 3), (3, 4), (1, 4) ]. It doesn’t matter in which order the pairs appear.

† 2.4.

A bit string is a string made up of either '0' or '1'. Write a function that will output all possible bit strings of length n. For example, bitString 2 = [ "00", "01", "10", "11" ]

3 Laziness

Haskell is a lazy language. This means nothing is executed unless it is strictly necessary. For example, to evaluate True || p we don’t need to know the value of p as the result is going to be True regardless. Therefore, evaluating p is only going to waste time! Although many languages implement similar ideas, sometime referred to as “short circuiting”, Haskell takes it to a whole new level with some interest consequences.

In this section, you will explore laziness and its applications. Some of these questions may seem tricky but try experimenting with your code as this is the best way to learn, and don’t be affraid to ask a TA for help if you’re stuck.

3.1. In Haskell, the expression ⊥ (written “undefined”) causes the program to crash and can behave as a value of any type, e.g. ⊥ :: Int, ⊥ :: Bool, ⊥ :: [Int] etc.. Try to predict which of the following expressions will crash and evaluate them in GHCi to verify your answers.