Все ли функции Haskell выполняют хвостовые вызовы?

Question

Мне было интересно, что каждая функция в Haskell должна быть хвостовой рекурсивной.

Факториальная функция реализована как не хвостовая рекурсивная функция:

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

Каждый оператор тоже является функцией, так что это эквивалентно

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

Но это, очевидно, вызов мне. Интересно, почему этот код вызывает переполнение стека, если каждый вызов просто создает новый thunk в куче. Разве я не должен получить переполнение кучи?

Answer 1

В коде

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

последний (*) ... это хвостовой вызов, как вы заметили. Последний аргумент fact (n-1) Однако построит Thunk, который сразу же требует (*), Это приводит к нехвостому вызову fact, Рекурсивно, это будет использовать стек.

TL; DR: размещенный код выполняет хвостовой вызов, но (*) не.

(Также "стек" в Haskell - не столь понятное понятие, как в строгих языках. Некоторые реализации Haskell используют что-то более сложное, чем это. Вы можете искать стратегии "push/enter vs eval/apply", если вам нужны подробности.)