[Solved] CSE505 Problem3-recursive definitions into tail-recursive

3 Convert the following recursive definitions into tail-recursive definitions.

1. fun f(1) = 1

| f(n) = n*n + f(n-1); (* assume n > 1 *)

Name the tail-recursive function as f2.

1. fun flatten([ ]) = [ ]

| flatten(h::t) = h @ flatten(t);

Name the tail-recursive function as flatten2.

1. 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