-- Part 1 ----------------------------------------------------------------------

merge :: (t -> t -> Bool) -> [t] -> [t] -> [t]

split :: [a] -> ([a], [a])

mergeSort :: (a -> a -> Bool) -> [a] -> [a]

mergeSortDecreasing :: [Integer] -> [Integer]
mergeSortDecreasing = mergeSort (>)

-- A True value in the list means the test passed.
-- Define more tests of your own by adding expressions to the list!
-- Fortunately GHCi's tab-completion saves you from typing the whole name. :)
part1testResults = [
  split [1,2,3,4,5] == ([1,2],[3,4,5]),
  merge (<) [1,3] [2,4] == [1,2,3,4],
  mergeSortDecreasing [2,1,3] == [3,2,1]]

-- Part 2 ----------------------------------------------------------------------

divides :: (Integral a) => a -> a -> Bool

divisors :: (Integral a) => a -> [a]

isPrime :: (Integral a) => a -> Bool

primes :: [Integer]

part2testResults = [
  divides 2 4,
  divisors 3 == [1,3],
  not (isPrime 1)]

-- Part 3 ----------------------------------------------------------------------

data BinaryTree a b = Branch a (BinaryTree a b) (BinaryTree a b)
                    | Leaf b deriving (Show, Eq)
data BinOp = Add | Sub | Mult
instance Show BinOp where
  show Add = "+"
  show Sub = "-"
  show Mult = "*"

getFunction :: (Num a) => BinOp -> a -> a -> a

showParenPre :: (Show a) => a -> [Char] -> [Char] -> [Char]

showPost :: (Show a) => a -> [Char] -> [Char] -> [Char]

treeApply :: (t -> t2 -> t2 -> t2) -> (t1 -> t2) -> BinaryTree t t1 -> t2

-- These functions use the ones you define above.
showScheme :: (Show a, Show b) => BinaryTree a b -> String
showScheme = treeApply showParenPre show

showRPN :: (Show a, Show b) => BinaryTree a b -> String
showRPN = treeApply showPost show

eval :: BinaryTree BinOp Integer -> Integer
eval = treeApply getFunction id

part3testResults = [
  eval exp1 == 5,
  showScheme exp1 == "(- (* 3 2) 1)",
  showRPN exp1 == "3 2 * 1 -"]
    where
      exp1 = Branch Sub (Branch Mult (Leaf 3) (Leaf 2)) (Leaf 1)