CSE505 – Assignment 2 – Problem 3
(to be done by the same team as for Problems 1 and 2)
3 Convert the following recursive definitions into tail-recursive definitions.
a. fun f(1) = 1
| f(n) = n*n + f(n-1); (* assume n 1 *)
Name the tail-recursive function as f2.
b. fun flatten([ ]) = [ ]
| flatten(h::t) = h @ flatten(t);
Name the tail-recursive function as flatten2.
c. 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);
Name the tail-recursive function as cat2.
How to run ML on Timberlake (you may also install and run ML on your personal computer)
Place all function definitions in one file, called A2_Problem3.sml. Run the program as follows.
timberlake% /util/bin/sml A2_Problem3.sml
- f(5);
- f2(5); (* should give same answer as f(5) *)
-
- flatten( [[1,2], [3,4,5], [ ], [6,7,8]] );
- flatten2( [[1,2], [3,4,5], [ ], [6,7,8]] ); (* should give same answer as flatten *)
-
- … similarly test cat and cat2 - use the tree shown in Lecture 14 slide 15 …
- Ctrl-d to exit
What to Submit
Prepare a top-level directory named A2_Problem3_UBITId1_UBITId2 if the assignment was done by two students (list UBITId’s in alphabetic order); otherwise, name it as A2_Problem3_UBITId if the assignment was done solo. In this directory place the file A2_Problem3.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.
