DAY: August 19, 2014  TIME: 8:30–12:30  PLACE: Msalar 
Responsible: Aids: Grade: 
Emil Axelsson, D&IT, Tel: 0733701736 An English (or EnglishSwedish, or EnglishX) dictionary
Completing Part I gives a 3 or a G; 
Part I (5 small assignments)

Part II (2 larger assignments)

Please read the following guidelines carefully: 
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:
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
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:
goodPassword
from assignment 1, even if you haven’t completed it.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 singleline 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:
(!!)
, 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:
<B> ... </B>
indicates that the text should be in boldface. Here, <B>
is the open tag, and </B>
is the corresponding close tag.<EM> ... </EM>
indicates that the text should be emphasized (often using italics).<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:
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

 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 !! (n1)
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 (n1) xs
drop n xs  n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n1) 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 ()
