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.