(a) The binary tree data type describes a binary tree for any type, but does not include the empty tree (i.e., each tree of this type must have at least a root node). Write a function maptree that takes a function as an argument and returns a function that maps trees to trees by mapping the values at the leaves to new values, using the function passed in as a parameter. In more detail, if f is a function that can be applied to the leaves of tree t and t is the tree on the left, then maptree f t should result in the tree on the right:

For example, if f is the function fun f( x) = x + 1 then maptree f (NODE( NODE( LEAF 1, LEAF 2), LEAF 3)) should evaluate to NODE( NODE( LEAF 2, LEAF 3), LEAF 4). Explain your definition in one or two sentences.

(b)

What is the type ML gives to your function? Why is it not the expected type ( a ? a) ? a tree ? a tree?

fil fin) . f(m) fi f(r) In Im