Work for CS-381, Programming Language Fundamentals
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 

215 lines
4.4 KiB

-- 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