DAY: January 13, 2014 | TIME: 8:30–12:30 | PLACE: V-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
findIndex :: Eq a => a -> [a] -> Int
that given an x
and a list xs
, finds out at what position x
occurs in the list. We start counting positions at 0. If there are multiple positions, the function findIndex always returns the first position x
is at.
Examples:
*Main> findIndex 'a' "bepacepa"
3
*Main> findIndex 11 [2,3,5,7,11,13]
4
*Main> findIndex "hej" ["hej","hi","hola","hello","hoi"]
0
The function may assume that x
actually occurs in the list (so, you may do whatever you want if x
does not occur in the list).
2. Implement a function
extension :: String -> String
that given a file name, returns the file extension. The extension consists of the last dot (“.”) occurring in the file name, plus all characters following that dot.
If there is no dot in the filename, you may decide yourself what you do. If there is more than one dot in the filename, the extension starts at the last dot.
Examples:
*Main> extension "tenta.doc"
".doc"
*Main> extension "Sherlock_Holmes.English.srt"
".srt"
*Main> extension "www.chalmers.se"
".se"
Hint:
reverse
and takeWhile
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
size :: Store -> Int
that counts the number of integer elements in the tree.
Examples:
*Main> size Empty
0
*Main> size (Join 7 Empty (Join 3 Empty Empty))
2
4. Anna is writing a QuickCheck property involving the functions length
and ++
. She has written:
prop_length_append :: [Int] -> [Int] -> Bool
prop_length_append xs ys =
length (xs ++ ys) == ...
But then she got stuck.
Can you help Anna by giving a Haskell expression you can write instead of the ...
which makes the property correct? (It should be something different than the left-hand side of course.)
5. Write a program
initFile :: IO ()
that asks the user for a file name and file content, and then creates a file of that name and content.
Example:
*Main> initFile
notes.txt
Haskell is nice!
(The user typed "notes.txt <enter> Haskell is nice! <enter>"
in the terminal.)
After this, the file notes.txt
has been created:
*Main> readFile "notes.txt"
"Haskell is nice!"
Hint:
getLine
and writeFile
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. Arne has a radio-controlled car that accepts four different commands: forward, backward, turn left and turn right. When the car turns left or right, it always turns exactly 90 degrees. In order to improve his driving skills, Arne wants to write a computer simulator for the car’s movement.
He starts by modeling the four commands as a data type:
data Command
= FORW Int
| BACKW Int
| LEFT
| RIGHT
The integer argument to FORW
and BACKW
denotes the distance the car should drive in that direction.
But after this, Arne gets stuck. He needs your help to implement a function
destination :: [Command] -> (Int,Int)
that, given a list of commands computes the position of the car after following these commands. The original position of the car is (x, y) = (0, 0), and it is facing “upwards” in the sense that going forwards will increase its y position.
Example:
*Main> destination [FORW 20, BACKW 10, RIGHT, FORW 100]
(100,10)
*Main> destination [FORW 20, BACKW 5, LEFT, FORW 100]
(-100,15)
Can you help him by implementing the function destination
?
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" ]
]
]
You are interested finding words that are considered important on the Internet. To do this, you need to implement a function
importantHTML :: Doc -> [String]
that returns all emphasized words in an HTML document.
All words inside <EM> ... </EM>
should be considered emphasized, regardless of what other tags appear in the ...
part.
Example:
*Main> importantHTML annasSida
["Haskell","Myst","anna@gmail.com"]
*Main> importantHTML [Tag "EM" [Tag "P" [Text "One for all"]]]
["One","for","all"]
Hint:
words
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
--------------------------------------------------------------------------
-- input/output
putStr :: String -> IO ()
getLine :: IO String
readFile :: FilePath -> IO String
writeFile :: FilePath -> String -> IO ()
--------------------------------------------------------------------------