Part I

You have to complete 5 out of the following 7 assignments to get a pass on the exam.

1

Given the following function

q1 :: [Int]  -> Int
q1 []                    = 0
q1 [x]                   = 0
q1 (x:y:xs)              = max (q1 xs) y

Write out the computation steps for computing the value of

q1 [1,3,4,2]

Note: this requires approximately 5 steps, so you should write five expressions, each one equivalent to

q1 [1,3,4,2]

and the last one should be a number (the final value of that expression).

2

In this question you should assume that you have a function rainfall which computes the rainfall in Gothenburg for a given week (where weeks are numbered from 1 and upwards)

type WeekNumber = Int
rainfall :: WeekNumber -> Double    -- assume this function exists

A week is considered to be “wet” if the rainfall in that week more than 10.

Give a definition of a function

countWetWeeks :: WeekNumber -> Int

such that countWetWeeks n (when n > 0) give the total count of the number of wet weeks in the week range 1 up to n.

Your solution must use a list comprehension, but may also use other predefined functions. Solutions which use recursion instead of a list comprehension will be considered incorrect. Solutions which return a list instead of a number will be considered incorrect.

3

In this question you should define a data type to represent a picture made of simple geometric shapes. More precisely, a picture is a list of zero or more simple shapes. A simple shape is either a circle or a rectangle, and has a colour (either black, red, green, or blue), and a position on the coordinate plane. If it is a circle it has a specified diameter (an integer of unspecified units). If it is a rectangle it has a height and a width (also integers).

Your task is (only) to complete the following Haskell definition of a data type Picture to represent this:

data Picture = ...

together with any other types that you need for this purpose. You may make use the following definitions:

data Colour    = Black | Red | Green | Blue
type Position  = (Int,Int)

Note: You are only representing a picture - you do not have to think about how a picture might be actually drawn on the screen. You do not have to define any functions, or write any deriving ....

Your answer should precisely represent the possible shapes specified, and nothing more.

4

The following data type represents arithmetic expressions with multiplication, addition, and subtraction:

data Expr = Num Int | BinOp Op Expr Expr
 deriving (Eq,Show)

data Op = Add | Mul | Sub
  deriving (Eq,Show)

Define a function

largestNum :: Expr -> Int

which given an expression, returns the largest number that appears in the expression.

For example, if some Haskell expression e :: Expr represents the arithmetic expression 1 + 2 * 3, then largestNum e would give 3.

5

Consider the following badly written Haskell definition:

check :: Int -> Bool
check n
  | (n >= 10) == True && (n <= 40)  == True = True
  | (n >= 50) == True && (n <= 104) == True = True
  | otherwise                               = False

Rewrite this definition so that it does not use the equality operator (==) and also does not use definition by cases (|), and does not use if-then -else. Your solution should not be unnecessarily complicated.

6

Give a recursive definition of the following standard function:

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [ x | x <- xs, p x ]

7

Give the definition of a QuickCheck generator

lenlist :: Gen [Int]

for lists of numbers, where for every list generated, the values of the elements in the list are not negative, but never larger than the length of the list. So for example, if it generates a list of ten elements, then every number in the list is no bigger that ten and no smaller than zero.

Your solution should make use quickCheck functions

vectorOf :: Int -> Gen a -> Gen [a]
choose   :: (Int,Int) -> Gen Int
arbitrary :: Gen Int

but you should not use arbitrary to generate a list.

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

The following definitions represent a shape composed of coloured squares at specific coordinates on a grid:

type AltShape = [Point]
data Point = P Colour (Int,Int)  deriving Eq
data Colour = Black | Red | Green | Blue  deriving Eq

We will assume that coordinates are always positive, and the coordinate (0,0) refers to the top left square of the picture, and the y-coordinates grow downwards (this is common in computer science but not in mathematics). A Red L-shape could be represented by

lShape = [P Red (0,0), P Red (0,1), P Red (0,2), P Red (1,2)]

Note that although every square in this shape is red, we can also have shapes where the colours are mixed. Note also that the order of the elements in the list is unimportant, assuming that there are no repeated coordinates (and you may assume this).

A different way to represent such shapes is as a list-of-lists, one list for each row:

type Shape = [Row] 
type Row   = [Square]

type Square = Maybe Colour

For example, the red L-shape above would be represented by the following value of type Shape:

lShape2 = [[x,o]
          ,[x,o]
          ,[x,x]] where x = Just Red
                        o = Nothing

Define a function

toShape :: AltShape -> Shape

that converts from a AltShape to an Shape, so that for example

toShape lShape == lShape2

Every row in your shape should have the same number of elements, but not have more elements than are needed.

Tip: don’t make the mistake of writing a function of type Shape -> AltShape as that would not be considered correct!

9

The last digit of a Swedish personal number (in 10 digit form) is a “checksum” digit and is included to make it possible to check whether there might be errors in the other numbers. The algorithm for checking is standard (the Luhn algorithm), and is used for many different kinds of identification numbers of different sizes. The algorithm is described as follows (using the example of the personal number 6504089019)

• From the rightmost digit and moving left, double the value of every second digit (i.e. double the second from last (1), fourth from last (9), etc). In the example, this gives the numbers 6+6, 5, 0+0, 4, 0+0, 8, 9+9, 0, 1+1, 9 = 12,5,0,4,0,8,18,2,9
  
• Take the sum of all the digits in the result (1+2+5+0+4+0+8+1+8+2+9 = 40). Note that we add together the digits, which is not the same as just adding the numbers!
• If the total is divisible by 10 (as it is in this example), the card number is valid, otherwise it is invalid.

Define a function valid :: Integer -> Bool and suitable helper functions to check if a number is valid according to the above algorithm. You may assume that the number is positive, but the function should work for any number of digits.

Hint: digitToInt :: Char -> Int may be useful.