Хвостовая рекурсия в Хаскеле
Я пытаюсь понять хвостовую рекурсию в Хаскеле. Я думаю, что понимаю, что это такое и как это работает, но я хотел бы убедиться, что я не все испортил.
Вот "стандартное" факториальное определение:
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# мог обнаруживать и преобразовывать хвостовые рекурсивные функции в циклы, я знаю (по крайней мере, то, что я слышал), что в настоящее время он этого не делает. Так что в настоящее время абсолютно бессмысленно делать функции хвостовыми рекурсивными. Это оно?
Спасибо!
2 ответа
Здесь есть два вопроса. Одним из них является хвостовая рекурсия в целом, а другим - как Хаскелл обрабатывает вещи.
Что касается хвостовой рекурсии, у вас, похоже, правильное определение. Полезная часть заключается в том, что, поскольку необходим только конечный результат каждого рекурсивного вызова, более ранние вызовы не нужно хранить в стеке. Вместо того, чтобы "вызывать себя", функция делает что-то ближе к "замене" себя, что в конечном итоге выглядит как итерационный цикл. Это довольно простая оптимизация, которую обычно предоставляют приличные компиляторы.
Второй вопрос - ленивая оценка. Поскольку Haskell оценивает выражение только по мере необходимости, по умолчанию хвостовая рекурсия не совсем работает обычным образом. Вместо того, чтобы заменять каждый вызов по ходу дела, он создает огромную вложенную кучу "блоков", то есть выражений, значение которых еще не было запрошено. Если эта куча становится достаточно большой, это действительно приведет к переполнению стека.
На самом деле в Haskell есть два решения, в зависимости от того, что вам нужно сделать:
Если результат состоит из вложенных конструкторов данных - например, создание списка - тогда вы хотите избежать хвостовой рекурсии; вместо этого поместите рекурсию в одно из полей конструктора. Это позволит сделать результат также ленивым и не приведет к переполнению стека.
Если результат состоит из одного значения, вы хотите строго оценить его, чтобы каждый шаг рекурсии выполнялся, как только требуется конечное значение. Это дает обычную псевдо-итерацию, которую вы ожидаете от хвостовой рекурсии.
Кроме того, имейте в виду, что GHC чертовски умен и, если вы компилируете с оптимизацией, он часто будет определять места, где оценка должна быть строгой, и позаботится об этом за вас. Это не будет работать в GHCi, хотя.
Вы должны использовать встроенные механизмы, тогда вам не нужно думать о том, как сделать вашу функцию хвостовой рекурсивной.
fac 0 = 1
fac n = product [1..n]
Или, если продукт еще не был определен:
fac n = foldl' (*) 1 [1..n]
(см. http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 о том, какую версию Fold... использовать)