ExerciseThree.hs

import Test.QuickCheck
import Data.List(sort, nub)

data BinaryTree = Branch Integer BinaryTree BinaryTree
                | Leaf
                deriving (Show, Ord, Eq)

isBST :: BinaryTree -> Bool
isBST Leaf = True
isBST (Branch v l r) = allTree (< v) l && allTree (>= v) r && isBST l && isBST r
  where allTree :: (Integer -> Bool) -> BinaryTree -> Bool
        allTree f (Branch v l r) = f v && allTree f l && allTree f r
        allTree f (Leaf) = True

insertBST :: Integer -> BinaryTree -> BinaryTree
insertBST i Leaf = Branch i Leaf Leaf
insertBST i (Branch v l r) 
  | i < v = Branch v (insertBST i l) r
  | otherwise = Branch v l (insertBST i r)   

insert1 :: Integer -> BinaryTree -> BinaryTree
insert1 i Leaf = Leaf
insert1 i (Branch v l r) 
    | i < v = Branch v (insert1 i l) r
    | otherwise =  Branch v l (insert1 i r)

insert2 :: Integer -> BinaryTree -> BinaryTree
insert2 i Leaf = Branch i Leaf Leaf
insert2 i (Branch v l r) 
    | i < v = Branch v (insert2 i l) r
    | i > v = Branch v l (insert2 i r)

insert3 :: Integer -> BinaryTree -> BinaryTree
insert3 i Leaf = Branch i Leaf Leaf
insert3 i (Branch v l r) 
    | i < v = Branch v (insert3 i l) r
    | i == v = Branch v l r
    | i > v = Branch v l (insert3 i r)

insert4 :: Integer -> BinaryTree -> BinaryTree
insert4 i Leaf = Branch i Leaf Leaf
insert4 i (Branch v l r) 
    | i < v = Branch v l (insert4 i r)
    | otherwise = Branch v (insert4 i l) r

searchTrees :: Gen BinaryTree
searchTrees = sized searchTrees'
  where 
   searchTrees' 0 = return Leaf
   searchTrees' n = do 
      v <- (arbitrary :: Gen Integer)
      fmap (insertBST v) (searchTrees' $ n - 1)

-- Search a binary search tree
search :: Integer -> BinaryTree -> Bool
search i Leaf = False
search i (Branch j l r)
    | i == j = True
    | i < j = search i l
    | i > j = search i r

size :: BinaryTree -> Integer
size Leaf = 0
size (Branch i l r) = 1 + size l + size r

prop_searchTrees = forAll searchTrees isBST

prop_insert_on_empty_tree insertFunction integer = insertFunction integer Leaf == Branch integer Leaf Leaf
prop_insert_on_non_empty_tree insertFunction integer = 
    forAll searchTrees $ \tree -> search integer (insertFunction integer tree) 
    && isBST tree
    && size (insertFunction integer tree) - size tree == 1
prop_insert_existing_elements_on_empty_tree insertFunction integer = 
    tempTree == Branch integer (Branch integer Leaf Leaf) Leaf || tempTree == Branch integer Leaf (Branch integer Leaf Leaf)
    where
        tempTree = insertFunction integer (insertFunction integer Leaf)    
prop_insert_existing_elements_on_non_empty_tree insertFunction integer = 
    forAll searchTrees $ \tree -> search integer (insertFunction integer (insertFunction integer tree))
    && isBST tree
    && size (insertFunction integer (insertFunction integer tree)) - size (insertFunction integer tree) == 1