--------------------------------------------------------------------
-- CO 2008  Functional Programming                            
-- Created: September 2006, University of Leicester, UK                        
--------------------------------------------------------------------           
-- Student Name
-- Student Number
--------------------------------------------------------------------

module Worksheet3 where 

-- An example of a function on natural numbers defined recursively 

fact :: Int -> Int
fact 0     = 1
fact 1     = 1
fact (n+1) = (n+1)*(fact n)
fact _     = error "Number is negative" 


----------------------------------------------------------------------
---- Exercise 1
---------------------------------------------------------------------
-- Adding the first n natural numbers
-- When the number is negative, give an error.
-- Recall: when testing the function with a negative number
--          the negative number should be written between brackets,
--         addup (-3) and not addup -3
addup :: Int -> Int
addup n
 | n<0 = error "please enter a positive integer"
 | n==0 = 0
 | n==1 = 1
 | n>1 = n + (addup n-1)

-- Adding the first n Fibonnaci numbers (recall Lecture 8 for their 
-- definition fib: Int -> Int)
addFibup :: Int -> Int
addFibup 0 = 0
addFibup 1 = 1
addFibup 2 = 1
addFibup 3 = 2
addFibup (n+2) =(addFibup (n+1))+(addFibup (n))

----------------------------------------------------------------------
---- Exercise 2

---------------------------------------------------------------------
-- A function that gives a line of n stars
-- When the number is negative, give an error.
starline :: Int -> String
starline 0 = ""
starline (n+1) = "*"++starline n
starline _ = error "Number Invalid"


-- A function that given n and m gives a list
-- of n lines of m stars, 
-- When the number n is negative, give an error
rectangle :: Int -> Int -> String
rectangle 0 m = "\n"
rectangle (n+1) m = "\n"++(starline m)++ rectangle n m
rectangle _ _ = error "Number is negative"

-- A function that prints a rectangle

printRectangle:: Int -> Int -> IO()
printRectangle m n  = putStr (rectangle m n)


-- A function that gives the square  
-- When the number is negative, give an error
square :: Int -> String
square n = rectangle n n

-- A function that prints a square

printSquare:: Int -> IO()
printSquare n  = putStr (square n)
 


-- An example of a recursive function on lists 
-- Note the use of patterns [], (x:[]) and (x:xs)
-- Instead of (x:[]) you could write [x]

myLast :: [Int] -> Int
myLast [] = error "Empty list"
myLast (x:[]) = x
myLast (x:xs) = myLast xs


----------------------------------------------------------------------
---- Exercise 3
---------------------------------------------------------------------
-- A function that converts a binary number to decimal system
-- Return an error in case some  integer in the list is not 0 or 1.
binToDec :: [Int] -> Int
binToDec a
 | a==[] = 0
 | head(reverse a) == 0 = 2*binToDec(reverse(tail(reverse a)))
 | head(reverse a) == 1 = 2*binToDec(reverse(tail(reverse a)))+1
 | otherwise = error "please enter an array of binary digits"
  
  
----------------------------------------------------------------------
---- Exercise 4
---------------------------------------------------------------------         
-- A function that removes the nth element in  a string 
-- Return an error in case the number is negative or is larger
-- than the length of the string
remove :: Int -> [a] -> [a] 
remove a b
 | a > length b = error "number too big"
 | a <=0 = error "please enter a positive number"
 | otherwise = take (a-1) b ++ drop a b

----------------------------------------------------------------------
---- Exercise 5
---------------------------------------------------------------------
-- A function that given two strings tests if the first one is
-- a prefix of the second one.
prefix :: String -> String -> Bool
prefix a b
 | take (length a) b == a = True
 | otherwise = False

----------------------------------------------------------------------
---- Exercise 6
---------------------------------------------------------------------
-- A function that given two strings tests if the first one is
-- a suffix of the second one.
suffix :: String -> String -> Bool
suffix a b = prefix (reverse a) (reverse b)


----------------------------------------------------------------------
---- Exercise 7
---------------------------------------------------------------------
-- Plurals in italian

type Word = String

italplural :: Word -> Word
italplural a
 | head(reverse a) == 'o' = reverse ("i" ++ tail (reverse a)) 
 | head(reverse a) == 'e' = reverse ("i" ++ tail (reverse a))
 | head(reverse a) == 'a' = reverse ("e" ++ tail (reverse a))
 | otherwise = a


----------------------------------------------------------------------
---- Exercise 8
---------------------------------------------------------------------
-- Higher order insertion sort
-- Hint: first write a function hoins that inserts an element 
-- in the right place

-- hoins :: Ord b => (a -> b) -> a  -> [a] -> [a]
-- The function hoInsertionSort sorts a list
-- hoInsertionSort :: Ord b => (a -> b)  -> [a] -> [a]

hoins :: Ord b => (a -> b) -> a -> [a] -> [a]
hoins fun item [] = item:[]
hoins fun item (x:xs)
 | fun item <= fun x = (item:x:xs)
 | otherwise = x:(hoins fun item xs)

hoInsertionSort :: Ord b => (a -> b) -> [a] -> [a]
hoInsertionSort fun [] = []
hoInsertionSort fun (x:xs) = hoins fun x (hoInsertionSort fun xs)

----------------------------------------------------------------------
---- Exercise 9
---------------------------------------------------------------------
-- Sorting an address book

type Name = String
type Address = String 
type Phonenumber = Int
type Person = (Name, Address)
type Phonebook = [Person]

toname :: Person -> String
toname (a,b) = a

sortbook :: Phonebook -> Phonebook
sortbook a = hoInsertionSort toname a

mybook :: Phonebook
mybook =  [("Di", "Welford rd 234"),
            ("Jo", "London rd 12"),
             ("Dave","Queens rd 78")]