4a. The ML type definition below is for a polymorphic tree, called ntree, where each internal node has a list of zero of more subtrees and each leaf node holds a single value:
datatype ‘a ntree = leaf of ‘a | node of ‘a ntree list;
Using the map(f,l) higher-order function, define a function subst(tr,v1,v2) which returns a new ntree in which all occurrences of v1 in the input ntree tr are replaced by v2 in the output tree. For example,
subst(node([leaf(“x”), node([leaf(“y”), leaf(“x”), leaf(“z”)])]), “x”, “a”)
= node([leaf(“a”), node([leaf(“y”), leaf(“a”), leaf(“z”)])])
Save your answer in a file subst.sml.
4b. Express the ‘cat’ function of A2 Problem 3(c) in tail-recursive form using continuation-passing style.
datatype ‘a tree = leaf of ‘a | node of ‘a tree * ‘a tree;
fun cat(leaf(s)) = s
| cat(node(t1, t2)) = cat(t1) ^ “ “ ^ cat(t2);
Define the tail-recursive ‘cat2’ as follows:
fun cat2(tr) = cat_cps(tr, (fn x => x))
The function cat_cps can be defined with two rules, one when tr is a ‘leaf’ and the other when tr is a
‘node’. A nested lambda-expression is needed to translate the two recursive calls on ‘cat’ in the original definition. Use the same test case as in A2 Problem 3(c). Save your answer in a file cat.sml.
