Part I

Correct answers to 5 out of the following 7 assignments gives a pass on the exam.

1

Given the following function

q1 :: Int -> Int -> Int
q1 x 0 = x
q1 x y | even y = q1 (x+y) (y-1)
       | odd  y = q1 x     (y-1)

What is the result of evaluating the following expression:

q1 0 4

You only need to write the answer. An answer with an incorrect type will be considered incorrect!

2

Give a definition of a function that tests if the values in a list are all the same or all different.

allSameOrDifferent :: Eq a => [a] -> Bool

Examples:

allSameOrDifferent []         == True
allSameOrDifferent [1,2,3]    == True
allSameOrDifferent [1,2,2]    == False
allSameOrDifferent [2,2,2]    == True
allSameOrDifferent "function" == False
allSameOrDifferent "Haskell"  == False

3

Snoc lists are like ordinary lists, except that instead of the cons constructor x:xs that adds an element to the front of a list, they have the Snoc constructor that adds a new element to the back of a list. Consider the following data type for snoc lists:

data SnocList a = Nil | Snoc (SnocList a) a

Define a function that converts a snoc list to an ordinary list:

toList :: SnocList a -> [a]

For example, toList (((Nil `Snoc` 1) `Snoc` 2) `Snoc` 3) == [1,2,3].

Hints: if your definition is not recursive then it is wrong. Reminder: backquotes allows you to put a function between its two arguments, i.e. you can write x `f` y instead of f x y. So xs `Snoc` x is the same as Snoc xs x.

4

Consider the function filtermap defined as follows:

filtermap :: (b->Bool) -> (a->b) -> [a] -> [b]
filtermap p f xs = filter p (map f xs)

Give an alternative definition of filtermap that uses a list comprehension instead of the standard library functions filter and map. Your definition should not use recursion or any library functions.

5

The standard libraries contain the operator !! for accessing the value at a given position in a list. For example "clock" !! 2 == 'o'. If we instead want to put a new value at a given position in a list, we have to define a function ourselves. Let’s call it replace. It can be defined e.g. with the help of splitAt, or directly by recursion like this:

replace :: Int -> a -> [a] -> [a]
replace _ _   []       = []
replace 0 new (old:xs) = new:xs
replace i new (old:xs) = old:replace (i-1) new xs

For example, replace 2 'i' "clock" == "click".

Define a similar function that allows us to modify the value at a given position in a list, by applying a function to it:

modify :: Int -> (a->a) -> [a] -> [a]

For example,

modify 6 toUpper "Happy new Year!" == "Happy New Year!"
modify 2 (*100) [5,6,7,8,9] == [5,6,700,8,9]

6

Define a function that acts as a simple adding machine. It allows the user to enter numbers and shows an updated sum after each number is entered.

addingMachine :: Int -> IO ()

The function should repeat the following sequence of actions forever:

1. Show the accumulated sum of the numbers entered so far.
2. Ask the user to enter a new number.
3. Add the new number to the accumulated sum.

The accumulated sum starts at the number given as an argument to the function. Testing addingMachine in GHCi would result in something like this:

*Main> addingMachine 0
Sum so far: 0
Enter the next number:
100
Sum so far: 100
Enter the next number:
7
Sum so far: 107
Enter the next number:
200000
Sum so far: 200107
Enter the next number:

Hints: you will probably need to use the standard functions getLine, putStrLn and read. Double check that whenever you use a function, the types of its arguments are correct; for example a function which has a String as an argument should not be given an IO String or [String].

7

Define a property that can be used to test with quickCheck that no numbers are both even and odd.

Part II

You do not need to work on this part if you only want to get a 3 or a G (although a correct answer to part II can be used instead of a question in part I).

8

Define a function that inserts a new value in a binary search tree:

insert :: Ord a => a -> Tree a -> Tree a

We use the following data type to represent binary search trees.

data Tree a = Empty | Node (Tree a) a (Tree a)
              deriving (Eq,Show)

The datatype invariant for a binary search tree is that whenever we have a Node t1 x t2, the values in t1 are smaller than x and the values in t2 are larger than x. This implies that the same value x can not appear in several places in a tree, so if x already appears in t, insert x t == t.

An example of a tree that satisfies the invariant is shown on the right, and we could represent it as follows (showing only the top 3 nodes):

t :: Tree Int
t = Node (Node … 3 …) 8 (Node Empty 10 …)

The correct place to insert the number 9 in t would be to the left below the node 10, i.e. the result of insert 9 t would be

Node (Node … 3 …) 8 (Node (Node Empty 9 Empty) 10 …)

9

Chess is a game that is played on a board with 8×8 squares, which could be represented in Haskell using a type like

data ChessBoard = Board [[Maybe Piece]]

data Piece = ...  -- the details are irrelevant here

Each square is either empty or occupied by a chess piece, i.e. either Nothing or Just p for some piece p.

The rows and columns (or ranks and files, as they are called) are usually identified by the numbers 1…8 and the letters a…h, but for simplicity, let us just use the numbers 0…7 for both:

-- A position on the chess board, e.g. (0,0) is the top left corner,
-- (7,0) is the top right corner and (7,7) is the bottom right corner.
type Position = (Int,Int)
e2 = (4,6)
e4 = (4,4)

-- Accessing the piece at a given position
pieceAt :: ChessBoard -> Position -> Maybe Piece
pieceAt (Board rows) (x,y) = rows !! y !! x

Define a function move (and suitable helper functions) to move a piece to a new position:

move :: ChessBoard -> Position -> Position -> Maybe ChessBoard

The function does not need to check that the move is allowed according to the rules of chess, it only needs to check that we are not trying to move a piece from an empty square. For example, here is the expected result of move board e2 e4:

• If there is no piece at position e2, the result should be Nothing.
• If there is a piece at position e2 (as in the chess board illustrated above), the result should be Just new_board, where new_board is the new board, where position e2 is empty and position e4 contains the piece previously located at position e2.

Hint: You may use the functions replace and modify from Question 5, even if you didn’t answer that question.