У Haskell есть хвостовая рекурсивная оптимизация?
Сегодня я обнаружил команду "time" в unix и подумал, что буду использовать ее для проверки разницы во времени выполнения между хвостовой и обычной рекурсивной функциями в Haskell.
Я написал следующие функции:
--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
fac' 1 y = y
fac' x y = fac' (x-1) (x*y)
--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)
Они действительны, имея в виду, что они предназначены исключительно для использования с этим проектом, поэтому я не стал проверять наличие нулей или отрицательных чисел.
Тем не менее, после написания основного метода для каждого, компиляции и запуска их с помощью команды "time", оба имели одинаковое время выполнения с обычной рекурсивной функцией, вытесняющей хвостовую рекурсивную. Это противоречит тому, что я слышал о хвостовой рекурсивной оптимизации в lisp. В чем причина этого?
4 ответа
Haskell использует ленивую оценку для реализации рекурсии, поэтому воспринимает все как обещание предоставить значение при необходимости (это называется thunk). Сливки уменьшаются только столько, сколько необходимо для продолжения, не более. Это похоже на то, как вы математически упрощаете выражение, поэтому полезно думать об этом так. Тот факт, что порядок оценки не определен вашим кодом, позволяет компилятору выполнять множество даже более умных оптимизаций, чем то, к чему вы привыкли. Компилировать с -O2 если хочешь оптимизации!
Посмотрим, как мы оцениваем facSlow 5 в качестве примера:
facSlow 5
5 * facSlow 4 -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3) -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2)) -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120
Так что, как вы и беспокоились, у нас есть наращивание чисел до того, как произойдут какие-либо вычисления, но, в отличие от вас, нет стека facSlow вызовы функций зависают в ожидании завершения - каждое сокращение применяется и уходит, оставляя после себя кадр стека (потому что (*) является строгим и поэтому запускает оценку своего второго аргумента).
Рекурсивные функции Haskell оцениваются не очень рекурсивно! Единственная пачка вызовов, лежащая вокруг, - это сами умножения. Если (*) рассматривается как строгий конструктор данных, это то, что известно как защищенная рекурсия (хотя это обычно упоминается как таковое для нестрогих конструкторов данных, где то, что остается на их пути, - это конструкторы данных - при форсированном последующем доступе).
Теперь давайте посмотрим на хвост-рекурсив fac 5:
fac 5
fac' 5 1
fac' 4 {5*1} -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}} -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}} -- the thunk "{...}"
(2*{3*{4*{5*1}}}) -- is retraced
(2*(3*{4*{5*1}})) -- to create
(2*(3*(4*{5*1}))) -- the computation
(2*(3*(4*(5*1)))) -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120
Таким образом, вы можете видеть, как рекурсия хвоста сама по себе не сэкономила вам ни времени, ни пространства. Мало того, что требуется больше шагов в целом, чем facSlow 5, он также создает вложенный Thunk (показано здесь как {...}) - нуждается в дополнительном пространстве для него - который описывает будущие вычисления, вложенные умножения, которые должны быть выполнены.
Затем этот поток разбрасывается путем его обхода до конца, воссоздавая вычисления в стеке. Здесь также существует опасность переполнения стека при очень длинных вычислениях для обеих версий.
Если мы хотим оптимизировать это вручную, все, что нам нужно сделать, это сделать это строгим. Вы можете использовать строгий оператор приложения $! определить
facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
facS' 1 y = y
facS' x y = facS' (x-1) $! (x*y)
Это силы facS' быть строгим во втором аргументе. (Это уже строгое в первом аргументе, потому что это должно быть оценено, чтобы решить, какое определение facS' применять.)
Иногда строгость может очень помочь, иногда это большая ошибка, потому что лень более эффективна. Вот хорошая идея:
facSlim 5
facS' 5 1
facS' 4 5
facS' 3 20
facS' 2 60
facS' 1 120
120
Я думаю, чего ты хотел достичь.
Резюме
- Если вы хотите оптимизировать свой код, первый шаг - это скомпилировать
-O2 - Хвостовая рекурсия хороша только в том случае, если нет наращивания thunk, и добавление строгости обычно помогает предотвратить ее, если и где это уместно. Это происходит, когда вы строите результат, который необходим позже сразу.
- Иногда хвостовая рекурсия - это плохой план, и защищенная рекурсия лучше подходит, т. Е. Когда результат, который вы создаете, будет необходим по частям, порциями. Смотрите этот вопрос о
foldrа такжеfoldlнапример, и проверить их друг против друга.
Попробуйте эти два:
length $ foldl1 (++) $ replicate 1000
"The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000
"The number of reductions performed is more important than tail recursion!!!"
foldl1 хвостовой рекурсивный, тогда как foldr1 выполняет защищенную рекурсию, так что первый элемент немедленно представляется для дальнейшей обработки / доступа. (Первые "скобки" слева сразу, (...((s+s)+s)+...)+s - полностью довести свой входной список до конца и построить большой поток будущих вычислений гораздо раньше, чем требуются его полные результаты; второе заключает в скобки вправо постепенно, s+(s+(...+(s+s)...)) , потребляя входной список побитно, так что все это может работать в постоянном пространстве, с оптимизацией).
Возможно, вам придется настроить количество нулей в зависимости от того, какое оборудование вы используете.
Следует отметить, что fac Функция не является хорошим кандидатом для защищенной рекурсии. Хвостовая рекурсия - путь сюда. Из-за лени вы не получаете эффект TCO в вашем fac' функция, потому что аргументы аккумулятора продолжают создавать большие thunks, что при оценке потребует огромного стека. Чтобы предотвратить это и получить желаемый эффект TCO, вы должны сделать эти аргументы аккумулятора строгими.
{-# LANGUAGE BangPatterns #-}
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
fac' 1 y = y
fac' x !y = fac' (x-1) (x*y)
Если вы компилируете, используя -O2 (или просто -O) GHC, вероятно, сделает это самостоятельно на этапе анализа строгости.
Вы должны проверить статью вики о хвостовой рекурсии в Haskell. В частности, из-за оценки выражений желаемая рекурсия - это защищенная рекурсия. Если вы проработаете детали того, что происходит под капотом (в абстрактной машине для Haskell), вы получите то же самое, что и с хвостовой рекурсией на строгих языках. Наряду с этим у вас есть унифицированный синтаксис для ленивых функций (хвостовая рекурсия свяжет вас со строгой оценкой, тогда как защищенная рекурсия работает более естественно).
(И в изучении Haskell, остальные эти вики-страницы тоже потрясающие!)
Если я правильно помню, GHC автоматически оптимизирует простые рекурсивные функции в хвостовые рекурсивные.