Сегодня я обнаружил команду 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. В чем причина этого?
haskell
optimization
lazy-evaluation
tail-recursion
tail-call-optimization
мошенник Haskell
источник
источник
facболее или менее знакомыproduct [n,n-1..1]с тем, как ghc вычисляет с помощью вспомогательной функцииprod, но, конечно, этоproduct [1..n]было бы проще. Я могу только предположить, что они не сделали его строгим во втором аргументе на том основании, что ghc очень уверен в том, что это именно то, что может скомпилировать до простого аккумулятора.Ответы:
Haskell использует ленивую оценку для реализации рекурсии, поэтому обрабатывает все как обещание предоставить значение, когда это необходимо (это называется преобразователем). Преобразователи сокращаются ровно настолько, насколько это необходимо для продолжения работы, не более того. Это похоже на математическое упрощение выражения, поэтому полезно думать об этом именно так. Тот факт, что порядок оценки не указан в вашем коде, позволяет компилятору выполнять множество еще более умных оптимизаций, чем просто устранение хвостового вызова, к которому вы привыкли. Скомпилируйте,
-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вызовов функций, которые ждут завершения - каждое сокращение применяется и исчезает, оставляя фрейм стека в своем wake (это потому, что(*)является строгим и поэтому запускает оценку его второго аргумента).Рекурсивные функции Haskell не вычисляются очень рекурсивно! Единственная куча вызовов - это сами умножения. Если
(*)рассматриваются как строго конструктора данных, это то , что известно как охраняемая рекурсия (хотя обычно называют такие с не конструкторами данных -strict, где то , что осталось на своем пути являются конструкторы данных - при вынужденном пути дальнейшего доступа).Теперь посмотрим на хвостовую рекурсию
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, но и создает вложенный преобразователь (показан здесь как{...}) - для которого требуется дополнительное пространство, - который описывает будущие вычисления и выполняемые вложенные умножения.Затем этот преобразователь раскрывается, просматривая его до самого низа, воссоздавая вычисление в стеке. Здесь также существует опасность переполнения стека при очень долгих вычислениях для обеих версий.
Если мы хотим оптимизировать это вручную, все, что нам нужно сделать, это сделать его строгим. Вы можете использовать строгий оператор приложения
$!для определения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Думаю, именно этого вы и хотели достичь.
Резюме
-O2foldrи,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)...)), потребляя ввод list по крупицам, так что все это может работать в постоянном пространстве с оптимизацией).Возможно, вам потребуется настроить количество нулей в зависимости от того, какое оборудование вы используете.
источник
Следует отметить, что
facфункция не подходит для защищенной рекурсии. Хвостовая рекурсия - это то, что вам нужно. Из-за лени вы не получаете эффекта TCO в своейfac'функции, потому что аргументы-накопители продолжают создавать большие переходы, которые при оценке потребуют огромного стека. Чтобы предотвратить это и получить желаемый эффект от совокупной стоимости владения, вам необходимо сделать эти аргументы аккумулятора строгими.{-# 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, вероятно, он сделает это самостоятельно на этапе анализа строгости .источник
$!чем понятнее, чем сBangPatterns, но это хороший ответ. Особенно упоминание об анализе строгости.Вам следует ознакомиться со статьей вики о хвостовой рекурсии в Haskell . В частности, из-за оценки выражений желаемый вид рекурсии является охраняемой рекурсией. Если вы проработаете детали того, что происходит под капотом (в абстрактной машине для Haskell), вы получите то же самое, что и с хвостовой рекурсией в строгих языках. Наряду с этим у вас есть единый синтаксис для ленивых функций (хвостовая рекурсия привяжет вас к строгой оценке, тогда как защищенная рекурсия работает более естественно).
(И в изучении Haskell остальные вики-страницы тоже великолепны!)
источник
Если я правильно помню, GHC автоматически оптимизирует простые рекурсивные функции в оптимизированные с хвостовой рекурсией.
источник