— Assignment 02
— This assignment is on Haskell language. You can use jdoodle to run the Haskell code.
— https://www.jdoodle.com/execute-haskell-online/
Copyright By PowCoder代写 加微信 powcoder
— Question 1
— Consider a polymorphic binary tree type that may be empty below
data BTree a = Empty | Leaf a | Fork a (BTree a) (BTree a)
deriving (Show) — val val left right
tree1 :: BTree Int
tree1 = Leaf 3
tree2 :: BTree Int
tree2 = Fork 4 tree1 tree1
tree3 :: BTree Int
tree3 = Fork 6 Empty tree2
tree = (Fork 1 (Fork 2 (Leaf 3) Empty) (Leaf 4))
— tree is visually as follows:
— 1
— / \
— 2 4
— / \
— 3 X
— where X is empty
— [2 marks]
— a) We want to include this type into a Functor typeclass
— To do that, we need to instantiate the fmap function
— Recap that type of fmap is: fmap :: Functor f => (a -> b) -> f a -> f b
— In this case, f is of a kind * -> * and our BTree fits this
— The expected behaviour is to apply the function (a -> b) to
— every element of the BTree while preserving the order
— in other words, left subtree will remain as left subtree
— Additionally, Empty will not be operated on
— e.g., given a tree = (Fork 1 (Fork 2 (Leaf 3) Empty) (Leaf 4))
— the result of fmap (\ x -> x+1) tree is
— (Fork 2 (Fork 3 (Leaf 4) Empty) (Leaf 5))
— 1 2
— / \ / \
— 2 4 ==> 3 5
— / \ / \
— 3 X 4 X
— [2 marks]
— b) We want to find the largest value in the tree
— However, as we may have an Empty tree, we need to use Maybe type
— In this case, we simply restrict ourselves into Integer type
— If the tree is empty, we simply return Nothing
— Otherwise, we return the largest element in the tree
— Implement the following function to find the largest element in the tree
— using declarative style programming
maxTree :: BTree Integer -> Maybe Integer
maxTree t = error “to do”
— [2 marks]
— c) Next, we want to “flatten” our tree into a list by traversing it (i.e., visit every element)
— There are many ways to traverse a tree but what we want is to traverse it in prefix order
— In prefix order, we first traverse recursively to the left subtree
— followed by traverse recursively to the right subtree
— and finally we will visit the value
— e.g., given a tree = (Fork 1 (Fork 2 (Leaf 3) Empty) (Leaf 4))
— the result of prefixBTree tree is
— [3, 2, 4, 1]
— The order of traversal is shown in curly bracket
— 1{5}
— / \
— 2{3} 4{4}
— / \
— {1}3 X{2}
prefixBTree t = error “to do”
— [1 mark]
— d) What is the most general type of prefixBTree (no need to include any typeclass)?
— We will now define a variant of fold called foldBTree function especially for our binary tree as follows:
foldBTree _ init Empty = init
foldBTree f init (Leaf v) = f init v init
foldBTree f init (Fork v l r) = f (foldBTree f init l) v (foldBTree f init r)
— [1 mark]
— e) What is the most general type of foldBTree (no need to include any typeclass)?
— [2 marks]
— f) The second type of “flatten” is by travering in a postfix order
— In postfix order, the traversal order is:
— 1) right subtree
— 2) left subtree
— 3) value
— Implement postfixBTree using foldBTree
— e.g., given a tree = (Fork 1 (Fork 2 (Leaf 3) Empty) (Leaf 4))
— the result of postfixBTree tree is
— [4, 3, 2, 1]
— The order of traversal is shown in curly bracket
— 1{5}
— / \
— 2{4} 4{1}
— / \
— {3}3 X{2}
postfixBTree t = error “to do” — you need to call foldBTree here
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com