DAY: October 22, 2013  TIME: 14:00–18:00  PLACE: Vsalar 
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
totalPrice :: (Item > Int) > [Item] > Int
that given a price function and an item list calculates the total price of the items in the list. The price function Item > Int
gives the price of a single item. Items are represented as strings:
type Item = String
For the examples, we will use the following price function:
priceOf :: String > Int
priceOf "milk" = 10
priceOf "butter" = 18
priceOf "potatoes" = 22
priceOf "chocolate" = 16
Examples:
*Main> totalPrice priceOf ["milk", "milk", "butter"]
38
*Main> totalPrice priceOf ["chocolate", "butter"]
34
2. When paying invoices using online banking, there is always a risk that one mistypes the OCR number. For this reason, OCR numbers typically include a check sum which makes it easy to discover most incorrectly typed numbers. A simple method to discover incorrect numbers is to look at the sum of the digits. In this assignment, we will say that a correct OCR number has a digit sum that ends with 7.
For example, the number 123452 is correct because 1+2+3+4+5+2 = 17, and the last digit of 17 is 7.
Implement a function
correctOCR :: [Integer] > Bool
that, given an OCR number (represented as a list of digits), checks whether or not it is correct.
Examples:
*Main> correctOCR [1,2,3,4,5,2]
True
*Main> correctOCR [1,2,3,4,5,6]
False
Hint:
show
, sum
and last
.mod
.3. Consider the following recursive data type, used to store integers in a tree shape.
data Store
= Empty
 Join Int Store Store
Implement a function
maxStore :: Store > Int
that finds the largest integer element in the tree.
Examples:
*Main> maxStore Empty
0
*Main> maxStore (Join 3 Empty (Join 7 Empty Empty))
7
4. Write a QuickCheck property that expresses that the result of sorting a list is the same if the list is first reversed, and then sorted.
prop_reverse_sort :: [Int] > Bool
...
Use the standard function sort
.
5. The wellknown UNIX command head
prints out the first 10 lines in a file. Implement a Haskell function:
unixHead :: FilePath > IO ()
that given a file name, prints out the first 10 lines in that file.
Example:
*Main> unixHead "Functions.hs"
{
This is a list of selected functions from the standard Haskell modules:
Prelude
Data.List
Data.Maybe
Data.Char
}

(Functions.hs is the file containing the appendix of this exam.)
Hint:
readFile
, unlines
, and lines
.Part II
Do not 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 radiocontrolled 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. Imagine that you have been given 100 kr and want to spend as much of it as possible. You go into a store where they sell the following:
Magazine: 44 kr
Ice cream: 33 kr
Umbrella: 59 kr
Candy: 15 kr
Soda: 19 kr
You are allowed to buy at most one of each item. What’s the maximum amount you can spend in this store?
(Answer: 96 kr (magazine, ice cream and soda).)
Write a function
maxSpend :: Int > [Int] > Int
that, given a maximal amount, and a list of item prices, computes the maximal spendable amount. Remember that you are allowed to buy each item at most once.
Examples:
*Main> maxSpend 100 [44,33,59,15,19]
96
*Main> maxSpend 100 [44,33]
77
*Main> maxSpend 10 [44,33]
0
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

 input/output
putStr :: String > IO ()
getLine :: IO String
readFile :: FilePath > IO String
writeFile :: FilePath > String > IO ()
