RE-EXAM
Introduction to Functional Programming
TDA555/DIT440



DAY: 2016-12-20 TIME: 14:00–18:00 PLACE: M-salar


Responsible:

Aids:

Grade:

David Sands; Questions:Alexander Sjösten 0317726167

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   (5 small assignments)

  • Give good enough answers for 4 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!
  • Do Part I and one assignment of your choice here and you will get a 4
  • Do Part I and both assignments here and you will get a 5 or a VG


Please read the following guidelines carefully:
  • Answers can be given in Swedish or English
  • Begin each assignment on a new sheet
  • Write your number on each sheet
  • Write clearly; unreadable = wrong!
  • 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
  • Never eat anything bigger than your own head

  • Good Luck!

    Part I

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


    1.

    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

    Complete the definition of the following function:

    mostRain :: WeekNumber -> Double
    mostRain n | n < 1     = 0
               | otherwise =                       -- (complete this case)

    such that mostRain n (when n > 0) gives the amount of rain in the rainiest week from week 1 up to and including week n.

    For example, suppose that the rainfall in week 3 is 20.5 (rainfall 3 == 20.5). Now if week number 3 is the rainiest of the first 50 weeks, then mostRain 50 == 20.5.

    Your solution must be recursive. Solutions that do not use recursion will be considered incorrect.

    Hint: The function max may be useful. Note that you do not have to provide a definition for the function rainfall.


    2. Define a function

    countLength :: Int -> String -> Int

    such that countLength n s returns the number of words in string s which have length n. The following property gives some examples:

    prop_countLength1 = countLength 4 "live long and prosper" == 2
                     && countLength 3 "eat and eat and eat"   == 5 
                     && countLength 2 "eat and eat and eat"   == 0

    You should make use of the standard function words.


    3. The following datatypes are used to represent a hand of cards:

    data Suit = Hearts | Clubs | Diamonds | Spades
      deriving Eq
    data Rank = Numeric Int | Jack | Queen | King | Ace
      deriving Eq
    data Card = Card Rank Suit
    deriving Eq
    
    
    data Hand = Empty | Add Card Hand

    Define a function

    moreAcesThan :: Hand -> Hand -> Bool

    where hand1 `moreAcesThan` hand2 gives True if the number of aces in the hand1 is more than the number of aces in hand2, and False otherwise (i.e. if the number of aces in both hands are the same, or if hand2 has more aces than the hand1).

    Hint: define a helper function which counts the number of aces in a given hand. The following simple definition might also be useful:

    rank (Card r _) = r

    4.

    Write a QuickCheck property prop_countLength that relates countLength n s (from question 2) to the values of length (words s) and length s as follows: if there are m words of length n in s then s must have at least n*m characters, and there must be at least m words in s.

    For example, countLength 10 "absolutely fabulously" == 2, and in this example there are at least 2 * 10 characters in that string (there are in fact 21), and there are at least 2 words (there are in fact exactly two).


    5. Consider the following function:

    rep :: Int -> String -> IO()
    rep n s
       | n <= 0    = return () 
       | otherwise = do putStrLn s
                        rep (n - 1) s

    This definition is not written in a good Haskell style since it uses more computation in IO than is really needed.

    In this question you are to rewrite this function starting with the following incomplete definition:

    rep :: Int -> String -> IO()
    rep n s = putStr w
      where w :: String
            w =                                      -- complete this definition

    The new version should behave the same as the old version when it is run. The definition of the missing local variable w must not use recursion. If your definition uses recursion it will be considered incorrect.

    Hint: Use the standard functions replicate and unlines.

    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).

    If you want to get a 4, you have to do Part I, plus one of the following assignments.

    If you want to get a 5 or a VG, you have to do Part I, plus both of the following assignments.


    6.

    Tic-tac-toe, also called wick wack woe (in some Asian countries) and noughts and crosses (in the British Commonwealth countries) and X’s and O’s in the Republic of Ireland, is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a k by k grid (where k is usually 3). The X player goes first. The player who succeeds in placing k marks in a horizontal, vertical, or diagonal row wins the game. [description adapted from Wikipedia]

    In this question we will consider the following representation of a tic-tac-toe grid:

    data Play = O | X  -- The letter O not the number 0 (zero)
        deriving Eq
    
    data TicTac = TicTac Int  [[Maybe Play]]
    
    exampleTT = TicTac 3 [ [Just O,  Just X,  Nothing],
                           [Just X,  Just O,  Nothing],
                           [Just X,  Nothing, Just O ] ]

    Note that the Int parameter describes the intended size of the grid.

    Define a function

    winner :: TicTac -> Bool

    which gives True if there is a winning line somewhere in the grid. For example, winner exampleTT == True because there are three Os in a line on one of the two diagonals.

    You may assume that every TicTac grid of the form TicTac n rs that rs has n rows, and each row has exactly n elements. A winning line (vertical, horizontal, or diagonal), must have n identical plays

    Note: Your solution must work for grids of any size. If it only works for grids of size 3 then your answer will be considered incorrect.

    Hint:


    7.

    A kind of family tree can be represented by the following Haskell datatype:

    type Name  = String
    type Born    = Int
    data Family = Fam Name Born [Family]

    Here is an example Family:

    duck :: Family
    duck = Fam "Uncle Scrooge" 1898
                        [ Fam "Donald" 1932 [] ,
                          Fam "Ronald" 1933
                                  [ Fam "Huey" 1968 [] ,
                                    Fam "Duey" 1968 [] ,
                                    Fam "Louie" 1968 [] ]
                        ]

    This value represents the male line of the duck family where Uncle Scrooge, born in 1898, had two sons, Donald and Ronald. Ronald has three children. Donald has no children, and Ronald has no grandchildren.

    In a family tree, it would be impossible for some child to be born before their parent. Define a function

    isValidTree :: Family -> Bool

    which given a family tree, checks that every parent is born before they have children.

    *Main> isValidTree duck
    True
    
    *Main> isValidTree $ Fam "Walt Disney" 1901 [duck]
    False

    Note: Some ducks reach sexual maturity after just 20 weeks, so it is possible that a child is born in the same year as their parent.