Does every Haskell function do tail calls?

Question

I wondered that every function in Haskell should be tail recursive.

The factorial function implemented as a non tail recursive function:

fact 0 = 1
fact n = n * fact (n - 1)

Every operator is a function too, so this is equivalent to

fact 0 = 1
fact n = (*) n (fact (n - 1))

But this is clearly a tail call to me. I wonder why this code causes stack overflows if every call just creates a new thunk on the heap. Shouldn't i get a heap overflow?

It can only a be a tail call if the function call is in the tail position. — leppie, Mar 30 '15 at 08:08
Oh. You're right. GHC rewrites the pattern matching to case expressions. But even there it could be possible to do a tail call because the call is in the last place in the function — Karroffel, Mar 30 '15 at 08:18
There is indeed a tail call. The `fact` function will tail call the `(*)` function. — augustss, Mar 30 '15 at 11:10
[Related](https://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization) — Silvio Mayolo, Feb 01 '18 at 03:09

score 2 · Accepted Answer · edited Mar 30 '15 at 08:23

2

In the code

fact 0 = 1
fact n = (*) n (fact (n - 1))

the last (*) ... is a tail call, as you observed. The last argument fact (n-1) however will build a thunk which is immediately demanded by (*). This leads to a non-tail call to fact. Recursively, this will consume the stack.

TL;DR: the posted code performs a tail call, but (*) does not.

(Also "the stack" in Haskell is a not so clear notion as in strict languages. Some implementations of Haskell use something more complex than that. You can search for "push/enter vs eval/apply" strategies if you want some gory details.)

edited Mar 30 '15 at 08:23

Sibi

47,472
16
95
163

answered Mar 30 '15 at 08:16

chi

111,837
3
133
218

So it's the nature of the `(+)` operator. Maybe the `(+)` implementation keeps the value on the stack and that's why i get a stack overflow and not a heap overflow – Karroffel Mar 30 '15 at 08:29
1

@dosenfrucht, thinking about tail calls in Haskell may lead you astray, because Haskell's evaluation model is very different from Scheme's or ML's. However, the fact that `*` is strict in its second argument means that you will face the same problem as a result of `fact (n-1)` not being in tail position as you would in a strict language. – dfeuer Apr 02 '15 at 01:09

Does every Haskell function do tail calls?

1 Answers1