这是一个新加坡的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