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
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
There is indeed a tail call. The fact function will tail call the (*) function. — augustss

chi chi · Accepted Answer · 2015-03-30T08:16:24

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.)

Does every Haskell function do tail calls?

1 Answers