5 ms·

In the example case, and many others, the tail-recursive version is the simple application of an accumulator. So for the factorial example, an accumulator versi

In the example case, and many others, the tail-recursive version is the simple application of an accumulator. So for the factorial example, an accumulator version would be (in haskell since I don't know the example language very well): fac1 0 = 1 fac1 n = (*) n (fac1 ((-) n 1)) -- tail-recursive fac2 0 acc = acc fac2 n acc = fac2 ((-)n 1) ((*) acc n) To me, something in with a pattern of: f v = g v (f (t v)) where f, g and t are functions (t is a transform on a, in the factorial case it is (-), Can usually be turned into the form (mechanically even): f v acc = f (t v) (g v acc) Does this hold for all cases or am i missing something? If it does hold, could a language just implement the TCO for it, and therefore couldn't we just consider the very first implementation of fac1 to be tail-recursive? edit: It is ugly but changed my exmple code to match the pattern i describe exactly.

Psyonic 16y ago
I believe this has some issues if the operation isn't commutative. For example: blah 0 = [] blah n = (++) [n] (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((++) [n] acc) -- blah2 5 [] -> [1,2,3,4,5] If we changed the tail to: blah2 (n-1) ((++) acc [n]) it would work in this case, but then we've flipped the arguments, and I have a feeling we could come up with a function where simply flipping the arguments won't work, though I can't think of one at the moment.
- sophacles 16y ago
  Good point! It becomes hard to do mechanical transforms like I suggested when you have to keep track of properties like this for every function. Thanks!
  - Psyonic 16y ago
    Ya that's the problem. Here's what I originally intended to write, but couldn't think of how to do cons in haskell so I used list addition. With cons (:), you can't rewrite it with the arguments swapped, so no simple mechanical transform will be able to fix this. blah 0 = [] blah n = (:) n (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((:) n acc) -- blah2 5 [] -> [1,2,3,4,5]
calcnerd256 16y ago
As you most likely realize, f base needs to equal the identity function. After that, it looks like t is your iterator and g is the function you want to fold. It looks like f is an iterator-friendly fold function.

Psyonic 16y ago

I believe this has some issues if the operation isn't commutative. For example: blah 0 = [] blah n = (++) [n] (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((++) [n] acc) -- blah2 5 [] -> [1,2,3,4,5] If we changed the tail to: blah2 (n-1) ((++) acc [n]) it would work in this case, but then we've flipped the arguments, and I have a feeling we could come up with a function where simply flipping the arguments won't work, though I can't think of one at the moment.

sophacles 16y ago
Good point! It becomes hard to do mechanical transforms like I suggested when you have to keep track of properties like this for every function. Thanks!
- Psyonic 16y ago
  Ya that's the problem. Here's what I originally intended to write, but couldn't think of how to do cons in haskell so I used list addition. With cons (:), you can't rewrite it with the arguments swapped, so no simple mechanical transform will be able to fix this. blah 0 = [] blah n = (:) n (blah ((-) n 1)) -- blah 5 -> [5,4,3,2,1] blah2 0 acc = acc blah2 n acc = blah2 ((-) n 1) ((:) n acc) -- blah2 5 [] -> [1,2,3,4,5]

calcnerd256 16y ago

As you most likely realize, f base needs to equal the identity function. After that, it looks like t is your iterator and g is the function you want to fold. It looks like f is an iterator-friendly fold function.