```-- Author: Danila Fedorin, Thursday, January 10 ``` ```module HW1 where ``` ``` ``` ``` ``` ```-- | Integer-labeled binary trees. ``` ```data Tree ``` ``` = Node Int Tree Tree -- ^ Internal nodes ``` ``` | Leaf Int -- ^ Leaf nodes ``` ``` deriving (Eq,Show) ``` ``` ``` ```-- | An example binary tree, which will be used in tests. ``` ```t1 :: Tree ``` ```t1 = Node 1 (Node 2 (Node 3 (Leaf 4) (Lea 5)) ``` ``` (Leaf 6)) ``` ``` (Node 7 (Leaf 8) (Leaf 9)) ``` ``` ``` ```-- | Another example binary tree, used in tests. ``` ```t2 :: Tree ``` ```t2 = Node 6 (Node 2 (Leaf 1) (Node 4 (Leaf 3) (Leaf 5))) ``` ``` (Node 8 (Leaf 7) (Leaf 9)) ``` ``` ``` ```-- | Right associative fold. ``` ```-- The best way here would be to add a foldable instance for Tree. ``` ```-- however, since Tree doesn't take a type parameter, this is not possible. ``` ```-- We settle for these functions. ``` ```treeFoldr :: (Int -> a -> a) -> a -> Tree -> a ``` ```treeFoldr f a (Leaf i) = f i a ``` ```treeFoldr f a (Node i l r) = treeFoldr f (f i (treeFoldr f a r)) l ``` ``` ``` ```-- | foldr for non-empty lists. ``` ```treeFoldr1 :: (Int -> Int -> Int) -> Tree -> Int ``` ```treeFoldr1 _ (Leaf i) = i ``` ```treeFoldr1 f (Node i l r) = treeFoldr f (f i (treeFoldr1 f r)) l ``` ``` ``` ```-- | Left associative fold. ``` ```treeFoldl :: (Int -> a -> a) -> a -> Tree -> a ``` ```treeFoldl f a (Leaf i) = f i a ``` ```treeFoldl f a (Node i l r) = treeFoldl f (f i (treeFoldl f a l)) r ``` ``` ``` ```-- | foldl for non-empty lists. ``` ```treeFoldl1 :: (Int -> Int -> Int) -> Tree -> Int ``` ```treeFoldl1 _ (Leaf i) = i ``` ```treeFoldl1 f (Node i l r) = treeFoldl f (f i (treeFoldl1 f l)) r ``` ``` ``` ```-- | In-order traversal fold. ``` ```treeFold :: (Int -> a -> a) -> a -> Tree -> a ``` ```treeFold f a (Leaf i) = f i a ``` ```treeFold f a (Node i l r) = f i \$ treeFold f (treeFold f a r) l ``` ``` ``` ```-- | The integer at the left-most node of a binary tree. ``` ```-- ``` ```-- >>> leftmost (Leaf 3) ``` ```-- 3 ``` ```-- ``` ```-- >>> leftmost (Node 5 (Leaf 6) (Leaf 7)) ``` ```-- 6 ``` ```-- ``` ```-- >>> leftmost t1 ``` ```-- 4 ``` ```-- ``` ```-- >>> leftmost t2 ``` ```-- 1 ``` ```-- ``` ```leftmost :: Tree -> Int ``` ```leftmost = treeFoldr1 (\a _ -> a) ``` ``` ``` ```-- | The integer at the right-most node of a binary tree. ``` ```-- ``` ```-- >>> rightmost (Leaf 3) ``` ```-- 3 ``` ```-- ``` ```-- >>> rightmost (Node 5 (Leaf 6) (Leaf 7)) ``` ```-- 7 ``` ```-- ``` ```-- >>> rightmost t1 ``` ```-- 9 ``` ```-- ``` ```-- >>> rightmost t2 ``` ```-- 9 ``` ```-- ``` ```rightmost :: Tree -> Int ``` ```rightmost = treeFoldl1 (\a _ -> a) ``` ``` ``` ```-- | Get the maximum integer from a binary tree. ``` ```-- ``` ```-- >>> maxInt (Leaf 3) ``` ```-- 3 ``` ```-- ``` ```-- >>> maxInt (Node 5 (Leaf 4) (Leaf 2)) ``` ```-- 5 ``` ```-- ``` ```-- >>> maxInt (Node 5 (Leaf 7) (Leaf 2)) ``` ```-- 7 ``` ```-- ``` ```-- >>> maxInt t1 ``` ```-- 9 ``` ```-- ``` ```-- >>> maxInt t2 ``` ```-- 9 ``` ```-- ``` ```maxInt :: Tree -> Int ``` ```maxInt = treeFoldr1 max ``` ``` ``` ``` ``` ```-- | Get the minimum integer from a binary tree. ``` ```-- ``` ```-- >>> minInt (Leaf 3) ``` ```-- 3 ``` ```-- ``` ```-- >>> minInt (Node 2 (Leaf 5) (Leaf 4)) ``` ```-- 2 ``` ```-- ``` ```-- >>> minInt (Node 5 (Leaf 4) (Leaf 7)) ``` ```-- 4 ``` ```-- ``` ```-- >>> minInt t1 ``` ```-- 1 ``` ```-- ``` ```-- >>> minInt t2 ``` ```-- 1 ``` ```-- ``` ```minInt :: Tree -> Int ``` ```minInt = treeFoldr1 min ``` ``` ``` ``` ``` ```-- | Get the sum of the integers in a binary tree. ``` ```-- ``` ```-- >>> sumInts (Leaf 3) ``` ```-- 3 ``` ```-- ``` ```-- >>> sumInts (Node 2 (Leaf 5) (Leaf 4)) ``` ```-- 11 ``` ```-- ``` ```-- >>> sumInts t1 ``` ```-- 45 ``` ```-- ``` ```-- >>> sumInts (Node 10 t1 t2) ``` ```-- 100 ``` ```-- ``` ```sumInts :: Tree -> Int ``` ```sumInts = treeFoldr1 (+) ``` ``` ``` ``` ``` ```-- | The list of integers encountered by a pre-order traversal of the tree. ``` ```-- ``` ```-- >>> preorder (Leaf 3) ``` ```-- [3] ``` ```-- ``` ```-- >>> preorder (Node 5 (Leaf 6) (Leaf 7)) ``` ```-- [5,6,7] ``` ```-- ``` ```-- >>> preorder t1 ``` ```-- [1,2,3,4,5,6,7,8,9] ``` ```-- ``` ```-- >>> preorder t2 ``` ```-- [6,2,1,4,3,5,8,7,9] ``` ```-- ``` ```preorder :: Tree -> [ Int ] ``` ```preorder = treeFold (:) [] ``` ``` ``` ```-- | The list of integers encountered by an in-order traversal of the tree. ``` ```-- ``` ```-- >>> inorder (Leaf 3) ``` ```-- [3] ``` ```-- ``` ```-- >>> inorder (Node 5 (Leaf 6) (Leaf 7)) ``` ```-- [6,5,7] ``` ```-- ``` ```-- >>> inorder t1 ``` ```-- [4,3,5,2,6,1,8,7,9] ``` ```-- ``` ```-- >>> inorder t2 ``` ```-- [1,2,3,4,5,6,7,8,9] ``` ```-- ``` ```inorder :: Tree -> [ Int ] ``` ```inorder = treeFoldr (:) [] ``` ``` ``` ``` ``` ```-- | Check whether a binary tree is a binary search tree. ``` ```-- ``` ```-- >>> isBST (Leaf 3) ``` ```-- True ``` ```-- ``` ```-- >>> isBST (Node 5 (Leaf 6) (Leaf 7)) ``` ```-- False ``` ```-- ``` ```-- >>> isBST t1 ``` ```-- False ``` ```-- ``` ```-- >>> isBST t2 ``` ```-- True ``` ```-- ``` ```isBST :: Tree -> Bool ``` ```isBST tree = snd \$ treeFoldl accCompare (firstNum, True) tree ``` ``` where ``` ``` accCompare v (p, b) = (v, b && v >= p) ``` ``` firstNum = leftmost tree ``` ``` ``` ```-- | Check whether a number is contained in a binary search tree. ``` ```-- (You may assume that the given tree is a binary search tree.) ``` ```-- ``` ```-- >>> inBST 2 (Node 5 (Leaf 2) (Leaf 7)) ``` ```-- True ``` ```-- ``` ```-- >>> inBST 3 (Node 5 (Leaf 2) (Leaf 7)) ``` ```-- False ``` ```-- ``` ```-- >>> inBST 4 t2 ``` ```-- True ``` ```-- ``` ```-- >>> inBST 10 t2 ``` ```-- False ``` ```-- ``` ```inBST :: Int -> Tree -> Bool ``` ```inBST i = treeFoldr (\v acc -> acc || (v == i)) False ```