EXAM
Introduction to Functional Programming
TDA555/DIT440



DAY: 2017-10-28 TIME: 14:00–18:00 PLACE: SB Multisal


Responsible:

Aids:

Grade:

David Sands 0737207663 [Will visit the exam rooms between 15.00 and 15.30]

An English (or English-Swedish, or English-X) dictionary

Completing Part I gives a 3 or a G;
Part I and Part II are both needed for a 4, 5, or VG


This exam consists of two parts:
Part I   (7 small assignments)

  • Give good enough answers for 5 assignments here and you will get a 3 or a G
  • (Points on Part II can be counted towards Part I if needed, but this is very unlikely to happen in practice.)
Part II   (2 larger assignments)

  • You do not need to solve this part if you are happy with a 3 or a G!
  • Pass Part I and one assignment of your choice here and you will get a 4
  • Pass Part I and both assignments here and you will get a 5 or a VG


Please read the following guidelines carefully:
  • Begin each assignment on a new sheet
  • Write your number on each sheet
  • Write clearly; unreadable = wrong!
  • Comments (if needed) can be given in Swedish or English
  • You can make use of the standard Haskell functions and types given in the attached list (you have to implement other functions yourself if you want to use them)
  • You do not have to import standard modules in your solutions
  • Tangentbordet är knepigt, men oftast har jag alt under ctrl.

  • Good Luck!

    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]                   = x
    q1 (x:_:xs)              = max x (q1 xs)

    what would the following expression give in ghci?

    q1 (map abs [-1,-6,-5,7])

    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 “dry” if the rainfall in that week is less than 5.

    Complete the definition of the following function:

    dryWeeks :: WeekNumber -> Int
    dryWeeks n | n < 1     = 0
    -- (complete this definition)

    such that dryWeeks n (when n > 0) gives the number of dry weeks in the range 1 up to n.

    Your solution must be recursive. Solutions that do not use recursion will be considered incorrect. Solutions which always return the value 0 (whether intended as a joke or otherwise) will also be considered incorrect!

    3

    In this question you should define a data type to represent a bus ticket of a certain kind described below.

    A bus ticket is either a single ticket (a ticket valid for a certain number of minutes) or a period ticket (a ticket that lasts a number of whole days). A single ticket is marked with the date and time when it expires. A period ticket is marked with the date when it expires.

    You should use the types Date and Time given below (although the details of their definitions are not important for this question):

    type Year   = Int
    type Month  = Int
    type Day    = Int
    type Hour   = Int
    type Minute = Int
    
    data Date = Date Year Month Day 
    data Time = Time Hour Minute

    Your task is (only) to complete the following definition:

    data BusTicket = ...

    Note: you do not have to define any functions, or write any deriving ....

    4

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

    data Expr = X | Num Int | BinOp Op Expr Expr
     deriving (Eq,Show)
    
    data Op = Add | Mul | Subtract
      deriving (Eq,Show)

    Although this data type can represent subtraction, it is not really needed since an expression such as, for example, 100 - X can be written as 100 + (-1) * X.

    Define a function

    removeSub :: Expr -> Expr

    which removes all subtraction operators in an expression by replacing them with a combination of addition and multiplication as in the above example.

    For example, 100 - X would be represented by the expression

    ex4 = BinOp Subtract (Num 100) X

    Then removeSub ex4 should give

    BinOp Add (Num 100) (BinOp Mul (Num (-1)) X)

    Your definition should only remove the subtraction operators. It should not attempt to simplify or evaluate the expression in any way.

    Hint: a correct solution must use recursion for every sub-expression in order to remove all subtraction operators.

    5

    The standard function isPrefixOf tests whether a given list is a prefix of another. For example the following expression is true:

    prop_isPrefixOf = "hell" `isPrefixOf` "hello"
                    && []    `isPrefixOf` [1,2,3]
                    && [1,2] `isPrefixOf` [1,2]
                    && not ([2,3] `isPrefixOf` [1,2,3])

    Define a quickCheck property

    prop_take :: Int -> String -> Bool

    which relates the function isPrefixOf with the function take :: Int -> [a] -> [a]. Your definition must use the two arguments as part of the test (so it is not OK to write a definition like prop_isPrefixOf which just gives a fixed number of examples).

    6

    Consider the following code:

    data Suit = Hearts | Clubs | Diamonds | Spades
      deriving (Eq,Show)
    data Rank = Numeric Int | Jack | Queen | King | Ace
      deriving (Eq,Show)
    data Card = Card Rank Suit
      deriving (Eq,Show)
    
    isRed, isDiamond :: Suit -> Bool
    isRed s             = s == Hearts || s == Diamonds
    isDiamond s         = s == Diamonds
    
    isAce, isLow :: Rank -> Bool
    isAce r             = r == Ace
    
    isLow (Numeric n)   = n < 5
    isLow _             = False
    
    lowDiamonds cs = [Card r s | Card r s <- cs,  isLow r && isDiamond s ]
    
    redAces cs     = [Card r s | Card r s <- cs,  isAce r && isRed s ]
    
    lowRedCards cs = [Card r s | Card r s <- cs,  isLow r && isRed s ]

    The last three functions in this code contain a lot of “cut-and-paste” repetition. Define a function

    selectCards :: (Rank -> Bool) -> (Suit -> Bool) -> [Card] -> [Card]

    which generalises these three functions, so that the following property holds:

    prop_selectCards cs = lowDiamonds cs == selectCards isLow isDiamond cs
                       && redAces     cs == selectCards isAce isRed cs
                       && lowRedCards cs == selectCards isLow isRed cs

    Note: to check such a property with quickCheck we would need to define generators for cards. You do not need to worry about that.

    7

    Give the definition of a QuickCheck generator

    quadlist :: Gen [Integer]

    for lists of Integers, where for every list generated, the length of the list is a multiple of 4. I.e., the generated lists contain 0 numbers, or 4 numbers, or 8 numbers, or 12 numbers, and so on. Hint: QuickCheck function vectorOf :: Int -> Gen a -> Gen [a] which generates a list of a specific length, as well as the generator arbitrary may be useful, but replicate or sized should probably not be used.

    Hints: (i) don’t make the common mistake of trying to apply a function of type Integer -> a to something of type Gen Integer, and (ii) don’t forget that you can work with things of type Gen Integer using do-notation.

    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 arranged in a grid. This can be modelled as a list-of-lists, one for each row:

    data Shape = S [Row] 
    type Row = [Square]
    
    type Square = Maybe Colour
    data Colour = Black | Red | Green   deriving Eq

    For example, a black L-shape might be represented by the following:

    lshape = [[x,o]
             ,[x,o]
             ,[x,x]] where x = Just Black
                           o = Nothing

    An alternative way to represent a shape is to use a coordinate system. Each coloured part of the shape is represented by a coordinate of a position in the grid, and the colour at that coordinate:

    type AltShape = [Point]
    data Point = P Colour (Int,Int)  deriving Eq

    In this representation, the L-shape above could be written:

    altLshape = map (P Black) [(0,0),(0,1),(0,2),(1,2)]

    Note that the alternative definition is not exactly equivalent, as does not give us a way to represent the blank squares; for example, all completely blank shapes, whether large or small, will be represented by the empty list. We will not worry about this minor difference in this question.

    Define a function

    fromShape :: Shape -> AltShape

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

    fromShape lshape == altLshape

    If your solution produces the correct points but listed in a different order that is also acceptable. You may assume, if necessary, that every row in the original shape has the same number of elements.

    9

    Consider the following definition of a binary tree

    data Tree a = Branch (Tree a) a (Tree a)
                | Leaf
                deriving Eq

    When using a tree to represent data it is often good if the tree is balanced, which means that there are roughly the same number of things in the left sub tree as there are in the right sub tree, for every branch in the tree.

    We define the skew of a tree to be a measure of how unbalanced it is. Let us first define the skew of a branch in a tree: the skew of a branch (a non-negative number) is the difference between the number of things in the left sub-tree compared to the right sub-tree. Now we define the skew of a tree to be zero if the tree is a leaf, and the largest skew of all the branches in the tree otherwise.

    For example, consider tree1 :: Tree String

    tree1 = Branch (Branch Leaf "left" Leaf) "top" Leaf

    The skew of the top branch is 1 and the skew of the left branch is 0, so the skew of tree1 is 1. Consider tree2:

    tree2 = Branch (Branch Leaf "left" (Branch Leaf "lr" Leaf)) "top" Leaf

    there are three different branches, with skews 2, 1 and 0, respectively. So the skew of the whole tree is the maximum of these, namely 2.

    Define a function

    skew :: Tree a -> Int

    which computes the skew of a tree. You may compute the skew in any way you like (i.e. it should be equivalent to the definition given above but it does not have to be defined in the same way).