EXAM
Introduction to Functional Programming
TDA555/DIT440



DAY: October 27, 2015 TIME: 14:00–18:00 PLACE: H-salar


Responsible:

Aids:

Grade:

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.


    1. Implement a function

    splitComma :: String -> (String,String)

    that splits a string at the first comma character. The comma itself should not be part of the result.

    You don’t need to handle the case where the string does not contain a comma.

    Examples:

    *Main> splitComma "abc,123"
    ("abc","123")
    
    *Main> splitComma "Jeffery Wilkie,15"
    ("Jeffery Wilkie","15")

    Hint:


    2. Assume that you have a database of personal information stored as a text file in the following format:

    Ginger Willard,45
    Brandon Durand,23
    Jeffery Wilkie,15
    Adele Winton,68
    Judith Stevens,38

    Each line consists of a name, followed by a comma, followed by that person’s age.

    Implement a function

    parseDB :: String -> [(String,String)]

    that reads a string in the above format and returns a list of pairs, where each pair is the name and age of the person on the corresponding line in the file.

    You can use the function splitComma from assignment 1 (don’t need to redefine it here).

    Examples:

    *Main> parseDB "abc,123"
    [("abc","123")]
    
    *Main> parseDB "Ginger Willard,45\nBrandon Durand,23\nJeffery Wilkie,15\n"
    [("Ginger Willard","45"),("Brandon Durand","23"),("Jeffery Wilkie","15")]

    (Note the newline characters '\n' in the input string.)

    Hint:


    3. Consider the following recursive data type, modeling logical formulas in Haskell:

    data Form
      = And Form Form
      | Or Form Form
      | Not Form
      | Val Bool

    For example, the formula not True || False is represented as Or (Not (Val True)) (Val False).

    Now, implement a function

    eval :: Form -> Bool

    that evaluates a given formula to its value, a Boolean.

    Examples:

    *Main> eval (And (Val True) (Or (Val False) (Val True)))
    True
    
    *Main> eval (Not (And (Val True) (Val False)))
    True

    Hint:


    4. Write a QuickCheck property that expresses the fact that concatenating two lists (i.e. as ++ bs) gives a new list that has the first list (i.e. as) as a prefix.

    Hint:


    5. Recall the database format from assignment 2. Write a function

    lookupDB :: FilePath -> String -> IO String

    that given a database file name and a person name, looks up the age of the person in the database.

    You can use the function parseDB from assignment 2 (don’t need to redefine it here).

    You can assume that the person to lookup exists in the database.

    For example, assume that the file "db.txt" has the following content:

    Ginger Willard,45
    Brandon Durand,23
    Jeffery Wilkie,15
    Adele Winton,68
    Judith Stevens,38

    Then we get the following example runs of the function:

    *Main> lookupDB "db.txt" "Judith Stevens"
    "38"
    
    *Main> lookupDB "db.txt" "Brandon Durand"
    "23"

    Hint:

    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.


    6. Define a function that displays a table in the text terminal:

    showTable :: [[String]] -> IO ()

    The table is represented as a list of columns. We will use following table as an example:

    myTable :: [[String]]
    myTable = [ ["Adam",     "Bertil", "Cesar"]
              , ["Lilla My", "E.T.",   "X"]
              , ["1",        "2",      "3"]
              ]

    The first (i.e. left-most) column in myTable is the list ["Adam", "Bertil", "Cesar"].

    Each column should be printed next to the previous one, from left to right, and each element in a column should be printed below the previous one. Furthermore, the elements in a column should be left-aligned, and there should be at least one space between each adjacent column.

    Printing myTable should give the following result:

    *Main> showTable myTable
    Adam   Lilla My 1
    Bertil E.T.     2
    Cesar  X        3

    You can assume that all columns in the table have the same number of elements.

    Hint:


    7. Your task is to implement a part of a screen saver that shows a ball bouncing around on the screen. The ball can travel in four different directions: north-east, north-west, south-east and south-west, as represented by the following data type:

    data Dir = NE | NW | SE | SW

    Implement the following function, which returns an infinite list of positions for the ball:

    screenSaver :: (Int,Int) -> Dir -> (Int,Int) -> [(Int,Int)]

    A call to this function takes the form screenSaver (w,h) dir (x,y), where (w,h) gives the width and height of the screen, dir gives the initial direction of the ball and (x,y) is the starting position.

    The ball should move one pixel (in both x and y) in each step. Whenever the ball reaches the end of the screen, it should bounce. For example, if the current direction is NE and it reaches the eastern border, it should go on in the direction NW. If the ball reaches a corner, it should bounce backwards (i.e. NE becomes SW).

    You do not need to take the width of the ball into account. The ball reaches a border when its center reaches the border.

    Example:

    *Main> take 20 $ screenSaver (50,50) NW (3,5)
    [(3,5),(2,4),(1,3),(0,2),(1,1),(2,0),(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7),(10,8),(11,9),(12,10),(13,11),(14,12),(15,13),(16,14)]

    Here is a picture that shows how the ball moves in the above example:

    Appendix

    
    {-
    This is a list of selected functions from the standard Haskell modules:
    
      Prelude
      Data.List
      Data.Maybe
      Data.Char
    -}
    
    --------------------------------------------------------------------------
    -- standard type classes
    
    class Show a where
      show :: a -> String
    
    class Eq a where
      (==), (/=) :: a -> a -> Bool
    
    class (Eq a) => Ord a where
      (<), (<=), (>=), (>) :: a -> a -> Bool
      max, min             :: a -> a -> a
    
    class (Eq a, Show a) => Num a where
      (+), (-), (*)    :: a -> a -> a
      negate           :: a -> a
      abs, signum      :: a -> a
      fromInteger      :: Integer -> a
    
    class (Num a, Ord a) => Real a where
      toRational       ::  a -> Rational
    
    class (Real a, Enum a) => Integral a where
      quot, rem        :: a -> a -> a
      div, mod         :: a -> a -> a
      toInteger        :: a -> Integer
    
    class (Num a) => Fractional a where
      (/)              :: a -> a -> a
      fromRational     :: Rational -> a
    
    class (Fractional a) => Floating a where
      exp, log, sqrt      :: a -> a
      sin, cos, tan       :: a -> a
    
    class (Real a, Fractional a) => RealFrac a where
      truncate, round  :: (Integral b) => a -> b
      ceiling, floor   :: (Integral b) => a -> b
    
    --------------------------------------------------------------------------
    -- numerical functions
    
    even, odd        :: (Integral a) => a -> Bool
    even n           = n `rem` 2 == 0
    odd              = not . even
    
    --------------------------------------------------------------------------
    -- monadic functions
    
    sequence     :: Monad m => [m a] -> m [a]
    sequence     = foldr mcons (return [])
                        where mcons p q = do x <- p; xs <- q; return (x:xs)
    
    sequence_    :: Monad m => [m a] -> m ()
    sequence_ xs = do sequence xs; return ()
    
    --------------------------------------------------------------------------
    -- functions on functions
    
    id               :: a -> a
    id x             = x
    
    const            :: a -> b -> a
    const x _        = x
    
    (.)              :: (b -> c) -> (a -> b) -> a -> c
    f . g            = \ x -> f (g x)
    
    flip             :: (a -> b -> c) -> b -> a -> c
    flip f x y       = f y x
    
    ($) :: (a -> b) -> a -> b
    f $  x           = f x
    
    --------------------------------------------------------------------------
    -- functions on Bools
    
    data Bool = False | True
    
    (&&), (||)       :: Bool -> Bool -> Bool
    True  && x       = x
    False && _       = False
    True  || _       = True
    False || x       = x
    
    not              :: Bool -> Bool
    not True         = False
    not False        = True
    
    --------------------------------------------------------------------------
    -- functions on Maybe
    
    data Maybe a = Nothing | Just a
    
    isJust                 :: Maybe a -> Bool
    isJust (Just a)        =  True
    isJust Nothing         =  False
    
    isNothing              :: Maybe a -> Bool
    isNothing              =  not . isJust
    
    fromJust               :: Maybe a -> a
    fromJust (Just a)      =  a
    
    maybeToList            :: Maybe a -> [a]
    maybeToList Nothing    =  []
    maybeToList (Just a)   =  [a]
    
    listToMaybe            :: [a] -> Maybe a
    listToMaybe []         =  Nothing
    listToMaybe (a:_)      =  Just a
    
    --------------------------------------------------------------------------
    -- functions on pairs
    
    fst              :: (a,b) -> a
    fst (x,y)        =  x
    
    snd              :: (a,b) -> b
    snd (x,y)        =  y
    
    curry            :: ((a, b) -> c) -> a -> b -> c
    curry f x y      =  f (x, y)
    
    uncurry          :: (a -> b -> c) -> ((a, b) -> c)
    uncurry f p      =  f (fst p) (snd p)
    
    --------------------------------------------------------------------------
    -- functions on lists
    
    map :: (a -> b) -> [a] -> [b]
    map f xs = [ f x | x <- xs ]
    
    (++) :: [a] -> [a] -> [a]
    xs ++ ys = foldr (:) ys xs
    
    filter :: (a -> Bool) -> [a] -> [a]
    filter p xs = [ x | x <- xs, p x ]
    
    concat :: [[a]] -> [a]
    concat xss = foldr (++) [] xss
    
    concatMap :: (a -> [b]) -> [a] -> [b]
    concatMap f = concat . map f
    
    head, last       :: [a] -> a
    head (x:_)       = x
    
    last [x]         = x
    last (_:xs)      = last xs
    
    tail, init       :: [a] -> [a]
    tail (_:xs)      = xs
    
    init [x]         = []
    init (x:xs)      = x : init xs
    
    null             :: [a] -> Bool
    null []          = True
    null (_:_)       = False
    
    length           :: [a] -> Int
    length []        = 0
    length (_:l)     = 1 + length l
    
    (!!)             :: [a] -> Int -> a
    (x:_)  !! 0      = x
    (_:xs) !! n      = xs !! (n-1)
    
    foldr            :: (a -> b -> b) -> b -> [a] -> b
    foldr f z []     =  z
    foldr f z (x:xs) =  f x (foldr f z xs)
    
    foldl            :: (a -> b -> a) -> a -> [b] -> a
    foldl f z []     =  z
    foldl f z (x:xs) =  foldl f (f z x) xs
    
    iterate          :: (a -> a) -> a -> [a]
    iterate f x      =  x : iterate f (f x)
    
    repeat           :: a -> [a]
    repeat x         =  xs where xs = x:xs
    
    replicate        :: Int -> a -> [a]
    replicate n x    =  take n (repeat x)
    
    cycle            :: [a] -> [a]
    cycle []         =  error "Prelude.cycle: empty list"
    cycle xs         =  xs' where xs' = xs ++ xs'
    
    take, drop             :: Int -> [a] -> [a]
    take n _      | n <= 0 =  []
    take _ []              =  []
    take n (x:xs)          =  x : take (n-1) xs
    
    drop n xs     | n <= 0 =  xs
    drop _ []              =  []
    drop n (_:xs)          =  drop (n-1) xs
    
    splitAt                :: Int -> [a] -> ([a],[a])
    splitAt n xs           =  (take n xs, drop n xs)
    
    takeWhile, dropWhile    :: (a -> Bool) -> [a] -> [a]
    takeWhile p []          =  []
    takeWhile p (x:xs)
                | p x       =  x : takeWhile p xs
                | otherwise =  []
    
    dropWhile p []          =  []
    dropWhile p xs@(x:xs')
                | p x       =  dropWhile p xs'
                | otherwise =  xs
    
    lines, words     :: String -> [String]
    -- lines "apa\nbepa\ncepa\n" == ["apa","bepa","cepa"]
    -- words "apa  bepa\n cepa"  == ["apa","bepa","cepa"]
    
    unlines, unwords :: [String] -> String
    -- unlines ["apa","bepa","cepa"] == "apa\nbepa\ncepa"
    -- unwords ["apa","bepa","cepa"] == "apa bepa cepa"
    
    reverse          :: [a] -> [a]
    reverse          =  foldl (flip (:)) []
    
    and, or          :: [Bool] -> Bool
    and              =  foldr (&&) True
    or               =  foldr (||) False
    
    any, all         :: (a -> Bool) -> [a] -> Bool
    any p            =  or . map p
    all p            =  and . map p
    
    elem, notElem    :: (Eq a) => a -> [a] -> Bool
    elem x           =  any (== x)
    notElem x        =  all (/= x)
    
    lookup           :: (Eq a) => a -> [(a,b)] -> Maybe b
    lookup key []    =  Nothing
    lookup key ((x,y):xys)
        | key == x   =  Just y
        | otherwise  =  lookup key xys
    
    sum, product     :: (Num a) => [a] -> a
    sum              =  foldl (+) 0
    product          =  foldl (*) 1
    
    maximum, minimum :: (Ord a) => [a] -> a
    maximum []       =  error "Prelude.maximum: empty list"
    maximum xs       =  foldl1 max xs
    
    minimum []       =  error "Prelude.minimum: empty list"
    minimum xs       =  foldl1 min xs
    
    zip              :: [a] -> [b] -> [(a,b)]
    zip              =  zipWith (,)
    
    zipWith          :: (a->b->c) -> [a]->[b]->[c]
    zipWith z (a:as) (b:bs)
                     =  z a b : zipWith z as bs
    zipWith _ _ _    =  []
    
    unzip            :: [(a,b)] -> ([a],[b])
    unzip            =  foldr (\(a,b) ~(as,bs) -> (a:as,b:bs)) ([],[])
    
    nub              :: Eq a => [a] -> [a]
    nub []           = []
    nub (x:xs)       = x : nub [ y | y <- xs, x /= y ]
    
    delete           :: Eq a => a -> [a] -> [a]
    delete y []      = []
    delete y (x:xs)  = if x == y then xs else x : delete y xs
    
    (\\)             :: Eq a => [a] -> [a] -> [a]
    (\\)             = foldl (flip delete)
    
    union            :: Eq a => [a] -> [a] -> [a]
    union xs ys      = xs ++ (ys \\ xs)
    
    intersect        :: Eq a => [a] -> [a] -> [a]
    intersect xs ys  = [ x | x <- xs, x `elem` ys ]
    
    intersperse      :: a -> [a] -> [a]
    -- intersperse 0 [1,2,3,4] == [1,0,2,0,3,0,4]
    
    transpose        :: [[a]] -> [[a]]
    -- transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
    
    partition        :: (a -> Bool) -> [a] -> ([a],[a])
    partition p xs   = (filter p xs, filter (not . p) xs)
    
    group            :: Eq a => [a] -> [[a]]
    -- group "aapaabbbeee" == ["aa","p","aa","bbb","eee"]
    
    isPrefixOf, isSuffixOf   :: Eq a => [a] -> [a] -> Bool
    isPrefixOf []     _      =  True
    isPrefixOf _      []     =  False
    isPrefixOf (x:xs) (y:ys) =  x == y && isPrefixOf xs ys
    
    isSuffixOf x y           =  reverse x `isPrefixOf` reverse y
    
    sort              :: (Ord a) => [a] -> [a]
    sort              = foldr insert []
    
    insert            :: (Ord a) => a -> [a] -> [a]
    insert x []       = [x]
    insert x (y:xs)   = if x <= y then x:y:xs else y:insert x xs
    
    --------------------------------------------------------------------------
    -- functions on Char
    
    type String = [Char]
    
    toUpper, toLower :: Char -> Char
    -- toUpper 'a' == 'A'
    -- toLower 'Z' == 'z'
    
    digitToInt :: Char -> Int
    -- digitToInt '8' == 8
    
    intToDigit :: Int -> Char
    -- intToDigit 3 == '3'
    
    ord :: Char -> Int
    chr :: Int  -> Char
    
    isDigit :: Char -> Bool
    
    --------------------------------------------------------------------------
    -- input/output
    
    putStr  :: String -> IO ()
    getLine :: IO String
    
    readFile  :: FilePath -> IO String
    writeFile :: FilePath -> String -> IO ()
    
    --------------------------------------------------------------------------