[Solved] CSE505 Problem1-polymorphic tree

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.