CODEWITHSUNDEEP
smlsmlnj
sailedapple002
sailedapple002

Reputation: 11

tree tail recursive in SML/NJ

I have a following function that defines a tree：

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);

The cat function is used to concatenates strings input to the string tree. I know it is not tail recursive since the definition use the function itself for recursion. Now I am thinking if there is any way to make it in the ways of tail recursive? Thanks in advance for any helps.

Upvotes: 1

Views: 515

Answers (1)

CarManuel
CarManuel

Reputation: 325

Here would be the tail recursive version

fun cat'(leaf(s), acc) = s^acc
  | cat'(node(t1, node(t2, acc))

You can also do it as a continuation passing style function

fun cat'' (leaf(s)) k = k(s)
  | cat'' (node(t1, t2)) k = cat''(t1) (fn res => k(res ^ cat''(t2)))

Hope this helps!! :D

Upvotes: 1

Related Questions