Is fold left tail recursion?

Question

I wanted to ask, if the function foldl is a tail recursion?

When I look at the source, how foldlis implemented:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

it looks like a tail recursion.

Fold left is always left associated. Assumed I have following expression:

foldl (*) 1 [1..3]

then it will evaluate to:

((1 * 1) * 2) * 3

then write out the steps, I would do like:

foldl (*) 1 [1..3] =
foldl (*) (1 * 1) [2,3]
foldl (*) (1 * 2) [3]
foldl (*) (2 * 3) []
6

not like ((1 * 1) * 2) * 3, or am I wrong?

Haskell doesn't have the concept of tail recursion. It uses lazy evaluation or thunks. — Ricky Han, Jun 14 '17 at 07:14
This link has information on how Haskell optimize recursions. https://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization — Ricky Han, Jun 14 '17 at 07:18
@RickyHan I slightly disagree. Tail recursion (or tail call, in general) does exist in Haskell, except it's not a good idea as in strict functional languages. Indeed, if one is not careful with strictness, one might easily let its tail recursive function to accumulate huge thunks before starting to do the real job. Because of this, I'd say that `foldl` is always a bad idea, and `foldl'` is the "real" left fold, which gives control to the caller so that strictness can be controlled. — chi, Jun 14 '17 at 08:10
Tail recursion just means a function returns the value returned by a recursive call immediately without doing any further work. Tail call *optimization* (TCO) is the language implementation feature that reuses a stack frame for the recursive call because it is known not to be needed any more by the caller. — chepner, Jun 14 '17 at 15:17

Will Ness · Accepted Answer · 2017-06-15T17:04:16.160

foldl expresses tail recursion when f is strict. you are correct, it is much preferable to have

foldl (*) 1 [1,2,3] = 
foldl (*) 1 [2,3]   = 
foldl (*) 2 [3]     = 
foldl (*) 6 []      = 
6

If f is not strict, i.e. leaves its argument expressions as they are, to be calculated later, you end up with the nested expressions like (((1*1)*2)*3), which can even cause stack overflow, needlessly, when they are finally being evaluated, because to evaluate such nested expressions a stack has to be used:

(((1*1)*2)*3) 
=> x * 3 where x = ((1*1)*2)
            => x = y*2 where y = 1*1
                             y <= 1
            => x = 1*2
            <= x = 2
=> 2 * 3
<= 6

and in any case it is a waste of much efforts when the intermediate results could already be evaluated in full.

see also: Does Haskell have tail-recursive optimization?

edit: foldl' must always be used for that, as noted by user:chi in the comments.

Is fold left tail recursion?

1 Answers1