import List
-- Question 1
--------------
-- Type them in and try them yourself. Make sure you understand
-- why the answer is what it is! And yes, you can reasonably assume
-- the List.hs has been imported.
-- Question 2
--------------
-- Part 1
-- Here is the script from the exam. Execute the five function
-- evaluations to see what the script does.
whiteSpace ch = elem ch " \n\t"
wordChar ch = (not.whiteSpace) ch
tolower ch
| ('A' <= ch) && (ch <= 'Z') = chr (ord ch + offset)
| otherwise = ch
where
offset = ord 'a' - ord 'A'
f text = map tolower text
g text
| trimmed == [] = []
| otherwise = first : g rest
where
trimmed = dropWhile whiteSpace text
first = takeWhile wordChar trimmed
rest = dropWhile wordChar trimmed
h text = map (length) (g text)
j = minimum . h
k = maximum . h
m text
= fromInt (sum hs) / fromInt (length hs)
where hs = h text
text1 = "Two words"
text2 = "A short sentence"
text3 = "A rather-longer sentence"
-- Part 2
-- Here is the original script from the exam, without the crossings out
-- Return the maximum of a list of numbers
max1 :: [Int] -> Int
max1 [] = error "maximum of empty list"
max1 [x] = x --- a
max1 (x:xs)
| x >= max1Rest = x --- b
| otherwise = max1Rest
where
max1Rest = max1 xs
-- Return the maximum of a list of numbers
-- using accumulator recursion
max2 :: [Int] -> Int
max2 (x:xs) = max' xs x
where
max' [] a = a --- c
max' (x:xs) a
| a > x = max' xs a --- d
| otherwise = max' xs x
--Return the string with all lower case letter replaced by upper
--case letter using `toUpper' and ordinary recursion
allUpper1 :: [Char] -> [Char]
allUpper1 [] = [] --- e
allUpper1 (c:cs) = toUpper c : allUpper1 cs --- f
--Return the string with all lower case letter replaced by upper
--case letter using `map' and `toUpper'
allUpper2 :: [Char] -> [Char]
allUpper2 cs = map toUpper cs --- g
--Return the string with all lower case letter replaced by upper
--case letter using `toupper' and list comprehensions
allUpper3 :: [Char] -> [Char]
allUpper3 cs = [toUpper c | c <- cs] --- h
-- Question 3
--------------
-- Part 1
nChooseK :: Int -> Int -> Int
nChooseK n k = factorial n `div` (factorial k * factorial (n-k))
where
factorial n = product [1..n]
-- Part 2
nthRow1 :: Int -> [Int]
nthRow1 n = map (nChooseK n) [0..n]
-- Or, if you didn't understand that you could use map,
-- nthRow1 n = [nChooseK n k | k <- [0..n]]
-- Part 3
nthRow2 :: [Int] -> [Int]
nthRow2 xs = [1] ++ [ x1+x2 | (x1,x2) <- zip xs (tail xs)] ++ [1]
-- (Or using some other combination of functions)
-- Part 4
-- Pretty print of Pascal's triangle
pascalTriangle :: Int -> [Char]
pascalTriangle n
= unlines [ cjustify width (showrow k) | k <- [0..n]]
where
width = length (showrow n)
showrow = concat . (map display) . nthRow1
-- display one number in 4 cols
display :: Int -> [Char]
display = (rjustify 4) . show
-- the next four functions take from the Lecture Notes so that
-- this script can be checked. You didn't need to write them in
-- the exam (in Miranda they are library functions :-)
-- centre str in a field of width fwidth
cjustify :: Int -> String -> String
cjustify fwidth str
| tspaces < 0 = str
| otherwise
= spaces lspaces ++ str ++
spaces rspaces
where
tspaces = fwidth - length str
lspaces = tspaces `div` 2
rspaces = tspaces - lspaces
spaces :: Int -> String
spaces n = replicate n ' '
-- left justify str in a field of width fwidth
ljustify :: Int -> String -> String
ljustify fwidth str
| tspaces < 0 = str
| otherwise = str ++ spaces tspaces
where
tspaces = fwidth - length str
-- right justify str in a field of width fwidth
rjustify :: Int -> String -> String
rjustify fwidth str
| tspaces < 0 = str
| otherwise = spaces tspaces ++ str
where
tspaces = fwidth - length str
-- Question 4
--------------
type John = [Float]
type Jane = [(Float,Int)]
-- Part 1
-- write a little story about John being good for dense polynomials
-- (most coefficients non-zero) and Jane being better for sparse
-- polynomials (most coefficients zero).
-- Part 2
-- convert poly of type John (dense) to type Jane (sparse)
john2Jane :: John -> Jane
john2Jane [] = []
john2Jane (c:cs)
| c /= 0 = (c, length cs) : john2Jane cs
| otherwise = john2Jane cs
-- Part 3
johnPlus :: John -> John -> John
-- polynomial addition for John-style polynomials
johnPlus xs ys
= filter (/=0) ((take fromx xs) ++ (take fromy ys) ++
(johnPlus' (drop fromx xs) (drop fromy ys)))
where
fromx = max (nxs - nys) 0
fromy = max (nys - nxs) 0
nxs = length xs
nys = length ys
johnPlus' [] [] = []
johnPlus' (x:xs) (y:ys)
= (x+y) : johnPlus' xs ys
-- Part 4
normalise :: Jane -> Jane
-- Convert poly of type Jane to standard form
normalise = stage3 . stage2 . stage1
stage1 :: Jane -> Jane
stage1
= reverse . (map swap) . sort . (map swap)
where
swap (a,b) = (b,a)
stage2 :: Jane -> Jane
stage2 ((c1,e1):(c2,e2):ces)
| e1 == e2 = stage2 ((c1+c2,e1):ces)
| otherwise = (c1,e1) : stage2 ((c2,e2):ces)
stage2 ces = ces
stage3 :: Jane -> Jane
stage3 = filter ((/=(fromInt)0) . fst)
-- Part 5
-- (Note in this part how easy it is to pick up further marks in a
-- question, even if you haven't tackled all of the functions)
-- Add together two Janes
janePlus :: Jane -> Jane -> Jane
janePlus xs ys = normalise (xs ++ ys)
-- Part 6 (Phew, this was actually a very long question...)
-- Convert poly of type Jane to poly of type John
jane2John :: Jane -> John
jane2John = jane2John' . normalise
jane2John' [] = []
jane2John' [(c,e)]
= c : zeroes e
jane2John' ((c1,e1):(c2,e2):ces)
= c1 : zeroes (e1-e2-1) ++ jane2John' ((c2,e2):ces)
zeroes n = take n (repeat 0)
-- Question 5
--------------
type FirstName = String
type FamilyName = String
type PhoneNum = Int
data Person = MakePerson FirstName FamilyName PhoneNum
deriving (Eq, Ord, Show)
type PersonList = [Person]
data PersonTree = Tree PersonTree Person PersonTree | Empty
deriving (Eq, Show)
-- Part 1
-- a Person is a structure or package that is created by applying
-- the MakePerson constructor function to three components of types
-- String, String, and Int respectively.
-- a PersonTree is a binary search tree structure for efficiently
-- maintaining a (possibly large) set of Person structures.
-- Part 2
-- Ordering of two Person's
personBefore :: Person -> Person -> Bool
personBefore (MakePerson fir1 fam1 n1) (MakePerson fir2 fam2 n2)
= (fam1 < fam2) || (fam1 == fam2 && fir1 < fir2)
-- Part 3
-- Sort a list of persons by converting them into a tuple
-- that can be sorted, and then converting back
sortPersons :: PersonList -> PersonList
sortPersons
= (map build) . sort . (map dump)
where
dump (MakePerson fir fam n) = (fam,fir,n)
build (fam,fir,n) = MakePerson fir fam n
-- Part 4
-- build a balanced PersonTree from a (sorted) PersonList
buildPersonTree :: PersonList -> PersonTree
buildPersonTree ps = (buildPersonTree' . sortPersons) ps
buildPersonTree' [] = Empty
buildPersonTree' xs
= Tree (buildPersonTree' leftList)
mid
(buildPersonTree' rightList)
where
half = (length xs) `div` 2
mid = xs !! half
leftList = take half xs
rightList = drop (half+1) xs
-- Part 5
-- write something intelligent about searching a (balanced) BST being
-- very much faster than searching a list, even when the list is sorted.
-- In the case of Telstra, the set of Persons is millions big, and a
-- list would be dreadfully slow for phone number lookup, but searching
-- in a balanced tree would take only a few dozens of checkes of items
-- to find the information about someone.