DAY: October 27, 2015 | TIME: 14:00–18:00 | PLACE: H-salar |
Responsible: Aids: Grade: |
David Sands, D&IT, Tel: 0737 20 76 63 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
splitComma :: String -> (String,String)
that splits a string at the first comma character. The comma itself should not be part of the result.
You don’t need to handle the case where the string does not contain a comma.
Examples:
*Main> splitComma "abc,123"
("abc","123")
*Main> splitComma "Jeffery Wilkie,15"
("Jeffery Wilkie","15")
Hint:
takeWhile
and dropWhile
.2. Assume that you have a database of personal information stored as a text file in the following format:
Ginger Willard,45
Brandon Durand,23
Jeffery Wilkie,15
Adele Winton,68
Judith Stevens,38
Each line consists of a name, followed by a comma, followed by that person’s age.
Implement a function
parseDB :: String -> [(String,String)]
that reads a string in the above format and returns a list of pairs, where each pair is the name and age of the person on the corresponding line in the file.
You can use the function splitComma
from assignment 1 (don’t need to redefine it here).
Examples:
*Main> parseDB "abc,123"
[("abc","123")]
*Main> parseDB "Ginger Willard,45\nBrandon Durand,23\nJeffery Wilkie,15\n"
[("Ginger Willard","45"),("Brandon Durand","23"),("Jeffery Wilkie","15")]
(Note the newline characters '\n'
in the input string.)
Hint:
lines
.3. Consider the following recursive data type, modeling logical formulas in Haskell:
data Form
= And Form Form
| Or Form Form
| Not Form
| Val Bool
For example, the formula not True || False
is represented as Or (Not (Val True)) (Val False)
.
Now, implement a function
eval :: Form -> Bool
that evaluates a given formula to its value, a Boolean.
Examples:
*Main> eval (And (Val True) (Or (Val False) (Val True)))
True
*Main> eval (Not (And (Val True) (Val False)))
True
Hint:
&&
), (||
), and not
.4. Write a QuickCheck property that expresses the fact that concatenating two lists (i.e. as ++ bs
) gives a new list that has the first list (i.e. as
) as a prefix.
Hint:
isPrefixOf
to check that a list is a prefix of another list.5. Recall the database format from assignment 2. Write a function
lookupDB :: FilePath -> String -> IO String
that given a database file name and a person name, looks up the age of the person in the database.
You can use the function parseDB
from assignment 2 (don’t need to redefine it here).
You can assume that the person to lookup exists in the database.
For example, assume that the file "db.txt"
has the following content:
Ginger Willard,45
Brandon Durand,23
Jeffery Wilkie,15
Adele Winton,68
Judith Stevens,38
Then we get the following example runs of the function:
*Main> lookupDB "db.txt" "Judith Stevens"
"38"
*Main> lookupDB "db.txt" "Brandon Durand"
"23"
Hint:
readFile
, and lookup
.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. Define a function that displays a table in the text terminal:
showTable :: [[String]] -> IO ()
The table is represented as a list of columns. We will use following table as an example:
myTable :: [[String]]
myTable = [ ["Adam", "Bertil", "Cesar"]
, ["Lilla My", "E.T.", "X"]
, ["1", "2", "3"]
]
The first (i.e. left-most) column in myTable
is the list ["Adam", "Bertil", "Cesar"]
.
Each column should be printed next to the previous one, from left to right, and each element in a column should be printed below the previous one. Furthermore, the elements in a column should be left-aligned, and there should be at least one space between each adjacent column.
Printing myTable
should give the following result:
*Main> showTable myTable
Adam Lilla My 1
Bertil E.T. 2
Cesar X 3
You can assume that all columns in the table have the same number of elements.
Hint:
transpose
to get a list of rows.concat
and unlines
useful for turning the list of rows into a single string.7. Your task is to implement a part of a screen saver that shows a ball bouncing around on the screen. The ball can travel in four different directions: north-east, north-west, south-east and south-west, as represented by the following data type:
data Dir = NE | NW | SE | SW
Implement the following function, which returns an infinite list of positions for the ball:
screenSaver :: (Int,Int) -> Dir -> (Int,Int) -> [(Int,Int)]
A call to this function takes the form screenSaver (w,h) dir (x,y)
, where (w,h)
gives the width and height of the screen, dir
gives the initial direction of the ball and (x,y)
is the starting position.
The ball should move one pixel (in both x and y) in each step. Whenever the ball reaches the end of the screen, it should bounce. For example, if the current direction is NE
and it reaches the eastern border, it should go on in the direction NW
. If the ball reaches a corner, it should bounce backwards (i.e. NE
becomes SW
).
You do not need to take the width of the ball into account. The ball reaches a border when its center reaches the border.
Example:
*Main> take 20 $ screenSaver (50,50) NW (3,5)
[(3,5),(2,4),(1,3),(0,2),(1,1),(2,0),(3,1),(4,2),(5,3),(6,4),(7,5),(8,6),(9,7),(10,8),(11,9),(12,10),(13,11),(14,12),(15,13),(16,14)]
Here is a picture that shows how the ball moves in the above example:
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 ()
--------------------------------------------------------------------------