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
