tree tail recursive in SML/NJ

Question

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.

This might help: https://stackoverflow.com/q/9323036/4996248 — John Coleman, Mar 05 '18 at 12:17
Possible duplicate of [Making a tree code tail recursive in SML/NJ](https://stackoverflow.com/questions/49102648/making-a-tree-code-tail-recursive-in-sml-nj) — molbdnilo, Mar 05 '18 at 13:23
I believe one of your coursemates asked this just a few hours before you. — molbdnilo, Mar 05 '18 at 13:24
This is a duplicate of [Tail-recursion on trees](https://stackoverflow.com/questions/19070577/tail-recursion-on-trees) — sshine, Mar 05 '18 at 14:16

score 1 · Answer 1 · answered Apr 11 '18 at 17:18

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

tree tail recursive in SML/NJ

1 Answers1