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 Raw Permalink Blame History

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