{- Haskell examples from week 2 -}

{- Factorial of a non-negative integer -}
factorial 0 = 1
factorial n 
    | n > 0 = n * factorial (n-1)

{- Raising an integer to the power of an integer -}
{- Type declaration -}
power :: Int -> Int -> Int

power a 0  = 1
power a n 
    |n > 0 = a * power a (n-1)

{- Function to append two lists -}
{- Polymorphic type declaration; the element type is immaterial -}
append :: [t] -> [t] -> [t]

append [] l' = l'
append (a:l) l' = a:(append l l') 

{- Function to reverse a list -}
rev :: [t] -> [t]

rev [] = []
rev (a:l) = append (rev l) [a]

{- Faster program to reverse a list -}
rev1 :: [t] -> [t]

rev1 l = rev' l []

rev' :: [t] -> [t] -> [t]
rev' [] l'    = l'
rev' (a:l) l' = rev' l (a:l')

{- Insert an element in a sorted list in the correct place -}

insert :: Int -> [Int] -> [Int]

insert x [] = [x]
insert x (a:l) = if x <= a then x:a:l
                 else a:(insert x l)