DAY: October 28, 2014 | TIME: 14:00–18:00 | PLACE: H-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 assignment, 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
urls :: String -> [String]
that given a text (as a string), returns a list with all web addresses (URLs) in that text. We say that web addresses are words that start with the string “http://”.
Examples:
*Main> urls "I tried loading http://www.chalmers.se and http://www.google.com but I didn't succeed."
["http://www.chalmers.se","http://www.google.com"]
*Main> urls "It's fun to stay at the Y.M.C.A."
[]
Hint:
words
, isPrefixOf
and filter
.3. Consider the following recursive data type which represents roads:
data Road
= City String
| Fork Road Road
City c
represents a road that goes straight to the city c
.
Fork l r
represents a road on which turning left leads to another road l
and turning right leads to the road r
.
Here is an example road:
middleOfNowhere :: Road
middleOfNowhere =
Fork
( City "Mora" )
( Fork
( Fork
( City "Kiruna" )
( City "Gävle" )
)
( City "Stockholm" )
)
Turning left on this road takes us straight to Mora, while turning right, then left, then right leads to Gävle.
Now, implement a function
reachable :: String -> Road -> Bool
that checks whether a given city is reachable from the given road.
Examples:
*Main> reachable "Kiruna" middleOfNowhere
True
*Main> reachable "Jukkasjärvi" middleOfNowhere
False
(Optional: Since apparently every road leads to Rome, make reachable
always return True
for the argument "Rome"
.)
4. The function and
checks that all elements in a list are True
. In other words, and
returns True
if and only if there is no False
element in the list. Write a QuickCheck property that expresses this fact about and
. Use the standard function notElem
to check that False
is absent from the list.
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. In assignment 3, you saw a data type for representing roads. When a new road is built around a city, the map of roads need to be updated.
Implement a function
insertRoad :: (Road,LR) -> String -> Road -> Road
which inserts a new road before a city.
A call to this function takes the form insertRoad (new,lr) city old
, where new
is the new road to be inserted, lr
determines whether the new road is entered by a left turn or a right turn (the LR
type is defined below), city
gives the name of the city before which the road should be inserted, and old
is the original map of roads.
The LR
type represents left or right turns, and is defined as follows:
data LR = L | R
Example:
*Main> insertRoad (City "Enköping",L) "Stockholm" middleOfNowhere
Fork (City "Mora") (Fork (Fork (City "Kiruna") (City "Gävle")) (Fork (City "Enköping") (City "Stockholm")))
7. 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 after each key press. (I.e. the 5th string in the result list is the text displayed after the 5th key press, the 6th string after the 6th key, and so on.)
Example:
*Main> putStr $ unlines $ lineEdit [Chr 'a', Chr 'b', GoLeft, Back, Chr 'c']
a
ab
ab
b
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.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 ()
--------------------------------------------------------------------------