Introduction to Functional Programming

DAY: 2016-10-29 TIME: 14:00–18:00 PLACE: M-salar




David Sands, D&IT, Tel: 0737 20 76 63

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

  • Good Luck!

    Part I

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


    Given the following definition:

    af :: Num a => [a] -> [a]
    af []       = []
    af [x]      = [x + 1]
    af (x:y:xs) = (x + 1) : y : af xs

    what answer do we get when we give the following expression to ghci:

    af [10,20,30]

    2. Implement a function

    urls :: String -> [String]

    that given a text (as a string), returns a list with all web addresses (URLs) in that text. We say that web addresses are words that start either with the string “http://” or with “https://”.
    Your solution must take care of both of these cases.


    *Main> urls "First try http://www.chalmers.se then try https://www.google.com"
    *Main> urls "It's fun to stay at the Y.M.C.A."


    3. Give a definition of a Haskell data type that can be used to represent arithmetic expressions such as the following four examples:

    3 * (2 + x) * y
    x + 2 * y
    2 * 3

    Your data type should be suitable to represent arithmetic expressions of any size built using multiplcation, addition, integers, and variables x and y only. You should not be able to represent variables other than x and y in your data type, or any invalid expressions.

    4. Function lookup is one of the standard functions. Write a QuickCheck property prop_LookJust that expresses that if lookup x table gives a result Just y, then the pair (x,y) should actually be in the table.


    5. Implement a Haskell function:

    wordCount :: FilePath -> IO (Int,Int)

    that given a file name, counts the number of words and lines in that file, and returns them as a pair (in that order).


    *Main> wordCount "ExamAnswers.hs"     -- (a file with 331 words and 96 lines)
    *Main> wordCount "emptyfile.txt"           -- (a file that contains nothing)


    Part II

    You do not need to work on this part if you only want to get a 3 or a G!

    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.


    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

    showTicTac :: TicTac -> String

    so that for example

    *Main> putStr (showTicTac exampleTT)
    X| |O

    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. You should print the grid exactly as above.

    Hint: the functions intersperse and unlines could be useful here.


    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.

    Define a function

    parent :: Name -> Family -> [Name]

    which given a name of a person and a family tree, finds all the possible parents of the person in the tree. So, for example,

    *Main> parent "Duey" duck
    *Main> parent "Uncle Scrooge" duck
    *Main> parent "Bob" duck

    If the child’s name appears several times in the family tree then there could be more than one possible parent.