Хвостовая рекурсия в Хаскеле

Question

Я пытаюсь понять хвостовую рекурсию в Хаскеле.Я думаю, что понимаю, что это такое и как это работает, но я хотел бы убедиться, что я не напутал.

Вот «стандартное» факториальное определение:

factorial 1 = 1
factorial k = k * factorial (k-1)

При запуске, например, factorial 3, моя функция будет вызывать себя 3 раза (дать или взять).Это может создать проблему, если я хочу вычислить факториал 99999999, поскольку у меня может быть переполнение стека.После того как я доберусь до factorial 1 = 1, мне придется «вернуться» в стеке и умножить все значения, поэтому у меня есть 6 операций (3 для вызова самой функции и 3 для умножения значений).

ТеперьЯ представляю вам еще одну возможную факториальную реализацию:

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

Эта тоже рекурсивная.Это будет называть себя 3 раза.Но у него нет проблемы с тем, чтобы по-прежнему приходиться «возвращаться» для вычисления умножения всех результатов, поскольку я уже передаю результат в качестве аргумента функции.

Это для чегоЯ понял, что такое Tail Recursion.Теперь он кажется немного лучше, чем первый, но вы все равно можете легко переполняться стеками.Я слышал, что компилятор Haskell преобразует функции Tail-Recursive в циклы for за кулисами.Я полагаю, это является причиной того, что выполнение хвостовых рекурсивных функций окупается?

Если это причина, то совершенно не нужно пытаться делать функции хвостовыми рекурсивными, если компилятор не собирается делать это умнотрюк - я прав?Например, хотя в теории компилятор C # мог обнаруживать и преобразовывать хвостовые рекурсивные функции в циклы, я знаю (по крайней мере, то, что я слышал), что в настоящее время он этого не делает.Таким образом, в настоящее время абсолютно бессмысленно делать функции хвостовыми рекурсивными.Это так?

Спасибо!

Answer 1

Здесь есть две проблемы. Одним из них является хвостовая рекурсия в целом, а другим - как Хаскелл обрабатывает вещи.

Что касается хвостовой рекурсии, вы, похоже, правильно поняли определение. Полезная часть заключается в том, что, поскольку необходим только конечный результат каждого рекурсивного вызова, более ранние вызовы не нужно хранить в стеке. Вместо того, чтобы «вызывать себя», функция делает что-то ближе к «замене» себя, что в конечном итоге выглядит как итеративный цикл. Это довольно простая оптимизация, которую обычно предоставляют приличные компиляторы.

Второй выпуск - Ленивая оценка . Поскольку Haskell оценивает выражение только по мере необходимости, по умолчанию хвостовая рекурсия не совсем работает обычным образом. Вместо того, чтобы заменять каждый вызов по мере необходимости, он создает огромную вложенную кучу «блоков», то есть выражений, значение которых еще не было запрошено. Если эта куча становится достаточно большой, это действительно приведет к переполнению стека.

На самом деле в Haskell есть два решения, в зависимости от того, что вам нужно сделать:

• Если результат состоит из вложенных конструкторов данных - например, создание списка - тогда вы хотите избежать хвостовой рекурсии; вместо этого поместите рекурсию в одно из полей конструктора. Это позволит сделать результат также ленивым и не приведет к переполнению стека.

• Если результат состоит из одного значения, вы хотите оценить его строго , чтобы каждый шаг рекурсии выполнялся, как только требуется окончательное значение. Это дает обычную псевдо-итерацию, которую вы ожидаете от хвостовой рекурсии.

Кроме того, имейте в виду, что GHC чертовски умен и, если вы компилируете с оптимизацией, он часто будет определять места, где оценка должна быть строгой, и позаботится о вас. Это не сработает в GHCi.

Answer 2

Вы должны использовать встроенные механизмы, тогда вам не нужно думать о том, как сделать свою функцию хвостовой рекурсивной

fac 0 = 1
fac n = product [1..n]

Или, если продукт еще не определен:

fac n = foldl' (*) 1 [1..n]

(см. http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 о том, какую версию Fold ... использовать)