CSE505 – Assignment 3 – Functional & Logic Programming
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.
WHAT TO SUBMIT:
Prepare a top-level directory named A3_Problem1_UBITId1_UBITId2 if the assignment is done by two students; otherwise, name it as A3_Problem1_UBITId if the assignment is done solo. (Order the UBITId’s in alphabetic order, in the former case.) In this directory, place subst.sml and cat.sml.
Compress the directory and submit the compressed file using the online submission procedure – instructions posted at Resources → Assignments → Online_Submission.pdf. Only one submission per team is required.
