Q:

Why is one fold tail-recursive and the other one is not?

fun fold1 f acc lst =
    case lst of
         [] => acc
       | hd::tl => fold1 f (f (acc,hd)) tl

fun fold2 f acc lst =
    case lst of
         [] => acc
       | hd::tl => f (fold2 f acc tl, hd)

Why first one is tail-recursive and the other is not?
I think both of them are tail-recursive.

A:

The first one is tail-recursive because the recursive call (to fold1) appears at the end of the function body (it forms the "tail"):
fold1 f (f (acc,hd)) tl

calls f (acc,hd) first, then passes the result (along with f and tl) to fold1. This is the last thing the function does; the result of the recursive fold1 call is passed through to our caller.

The second one is not tail-recursive because the recursive call (to foldl2) is not the last thing the function does:
f (fold2 f acc tl, hd)

calls fold2 f acc tl first, then makes a tuple from the result and hd, then passes that tuple to f.
There are two things that happen after the recursive fold2 call: Tuple construction ((..., hd)) and another function call (f ...). In particular, the result of calling fold2 is not passed straight through to our caller. That's why this code is not tail-recursive.

