EXAM
Introduction to Functional Programming
TDA555/DIT440



DAY: August 19, 2014 TIME: 8:30–12:30 PLACE: M-salar


Responsible:

Aids:

Grade:

Emil Axelsson, D&IT, Tel: 0733-701736

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

    goodPassword :: String -> Bool

    that checks whether a given password is good. In this exercise, we say that a good password is a password that contains at least one digit.

    Examples:

    *Main> goodPassword "apa"
    False
    
    *Main> goodPassword "apa2bepa"
    True

    Hint:


    2. Implement a function

    sumPred :: (Int -> Bool) -> [Int] -> Int

    that given a function p and a list xs computes the sum of the elements in xs for which p returns true.

    Examples:

    *Main> sumPred even [1,2,3,4]
    6
    
    *Main> sumPred (<5) [0..1000]
    10

    3. Consider the following recursive data type, used to store integers in a tree shape.

    data Store
      = Empty
      | Join Int Store Store

    Now, implement a function

    inStore :: Int -> Store -> Bool

    that checks whether the given number can be found in the store.

    Examples:

    *Main> inStore 4 Empty
    False
    
    *Main> inStore 4 (Join 7 Empty (Join 3 Empty Empty))
    False
    
    *Main> inStore 3 (Join 7 Empty (Join 3 Empty Empty))
    True

    4. Write a QuickCheck property that expresses the fact that nub never returns a longer list than its argument.


    5. Write a program

    checkPassword :: IO ()

    which asks the user to type in a password, and then says if that is a good password or not.

    Examples:

    *Main> checkPassword
    Type in a password> apa
    Bad password :(
    
    *Main> checkPassword
    Type in a password> bepa2apa
    Good password :)

    (The user typed "apa <enter>" and "bepa2apa <enter>", respectively, in the terminal.)

    Hints:

    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. Gaby is implementing a chat program in which users are able to broadcast short single-line messages to other users. One part of this program is the line editor, which reads keyboard presses and produces a corresponding text string in a text box.

    Keyboard presses are represented by the following data type:

    data Key = Chr Char | Back | GoLeft | GoRight

    Chr represents a normal visible character; Back represents the backspace key, which deletes the character to the left of the cursor (if possible); GoLeft moves the cursor to the left (if possible), and GoRight moves the cursor to the right (if possible).

    Help Gaby implement a function

    lineEdit :: [Key] -> String

    that, given a list of keys computes the resulting text string.

    Example:

    *Main> lineEdit [Chr 'a', Chr 'b', GoLeft, Back, Chr 'c']
    "cb"

    Hint:


    7. The HyperText Markup Language, better known as HTML, is a language for describing documents. All webpages are written using HTML.

    Documents written in HTML have a structure that is determined by the use of tags. We can enclose a certain part of our document within certain tags, in order to indicate this structure. To enclose a part of a document in tags, we use matching open tags and close tags. For example:

    (In reality, tags contain more information than just the tag name (such as B, EM, P, etc.), but for simplicity we do not deal with that here.)

    Here is an example of HTML code:

    Welcome to my website!<P><B>My hobbies are <EM>Haskell</EM> programming and playing <EM>Myst</EM>.</B></P><P>Thanks for visiting! <EM>anna@gmail.com</EM></P>

    And here is what it would look like in a browser:

    Welcome to my website!

    My hobbies are Haskell programming and playing Myst.

    Thanks for visiting! anna@gmail.com

    We can represent HTML documents in Haskell in the following way. First, we realize that a document consists of a sequence of document parts.

    type Doc = [DocPart]

    There are two kinds of document parts: (1) a piece of text, and (2) a whole document enclosed in a certain kind of tag.

    data DocPart
      = Text String
      | Tag String Doc

    The example piece of HTML above can be represented by the following Haskell expression:

    annasSida :: Doc
    annasSida =
      [ Text "Welcome to my website!"
      , Tag "P" [ Tag "B" [ Text "My hobbies are "
                          , Tag "EM" [ Text "Haskell" ]
                          , Text " programming and playing "
                          , Tag "EM" [ Text "Myst" ]
                          , Text "."
                          ] ]
      , Tag "P" [ Text "Thanks for visiting! "
                , Tag "EM" [ Text "anna@gmail.com" ]
                ]
      ]

    Define a function html2txt that converts an HTML document to a text string and prints it on the terminal. Paragraphs (<P>...</P>) should be surrounded by blank lines; bold text (<B>...</B>) should be displayed using capital letters; emphasized text (<EM>...</EM>) should be surrounded by asterisks (*).

    Example:

    *Main> html2txt annasSida
    Welcome to my website!
    
    MY HOBBIES ARE *HASKELL* PROGRAMMING AND PLAYING *MYST*.
    
    
    Thanks for visiting! *anna@gmail.com*

    Hint:

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