— Assignment 02

— This assignment is on Haskell language. You can use jdoodle to

— 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

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司