这是一个新加坡的Haskell作业代写
— Assignment 02
— This assignment is on Haskell language. You can use jdoodle to
run the Haskell code.
— https://www.jdoodle.com/execute-haskell-online/
— 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