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 (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 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:
(!!)
, 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 !! (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 ()
--------------------------------------------------------------------------