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

True``````

Hint:

• Use the standard function `isDigit`

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

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

Hints:

• You may use the function `goodPassword` from assignment 1, even if you haven’t completed it.
• Use `getLine`.

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:

• To avoid using the indexing operator `(!!)`, it is a good idea to represent the current line as two separate lists: the part to the left and the part to the right of the cursor. (But using indexing is also fine.)

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:

• Text enclosed in boldface tags `<B> ... </B>` indicates that the text should be in boldface. Here, `<B>` is the open tag, and `</B>` is the corresponding close tag.
• Text enclosed in emphasize tags `<EM> ... </EM>` indicates that the text should be emphasized (often using italics).
• Text enclosed in paragraph tags `<P> ... </P>` indicates that the text forms a paragraph (often by having an empty line before and after).

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

• Use the standard function `toUpper`.

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

--------------------------------------------------------------------------

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

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

--------------------------------------------------------------------------``````