У Haskell есть рекурсивная оптимизация?

Ответ 1

Haskell использует ленивую оценку для реализации рекурсии, поэтому рассматривает все как обещание предоставить значение при необходимости (это называется thunk). Thunks уменьшается только столько, сколько необходимо для продолжения, не более того. Это похоже на то, как вы упрощаете выражение математически, поэтому полезно подумать об этом. Тот факт, что порядок оценки не указан вашим кодом, позволяет компилятору делать много даже более умных оптимизаций, чем просто устранение хвостового вызова, к которому вы привыкли. Скомпилируйте с -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
• Рекурсия хвоста хороша только тогда, когда нет наращивания громкости, и добавление строгости обычно помогает предотвратить ее, если и когда это необходимо. Это происходит, когда вы создаете результат, который необходим позже для всех сразу.
• Иногда рекурсия хвоста - плохой план, и охраняемая рекурсия лучше подходит, т.е. когда результат, который вы строите, будет необходимо по частям. См. этот вопрос о 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)...)), потребляя входной список побитно, так что вся вещь способна работать в постоянном пространстве с оптимизацией).}

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

Ответ 2

Следует отметить, что функция fac не является хорошим кандидатом на охраняемую рекурсию. Рекурсия хвоста - это путь сюда. Из-за лени вы не получаете эффект TCO в своей функции fac', потому что аргументы аккумулятора продолжают строить большие трюки, которые при оценке потребуют огромного стека. Чтобы предотвратить это и получить желаемый эффект 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, вероятно, сделает это самостоятельно в фазе строгости.

Ответ 3

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

(И, изучая Haskell, остальные страницы wiki также потрясающие!)

Ответ 4

Если я правильно помню, GHC автоматически оптимизирует простые рекурсивные функции в рекурсивные оптимизированные.