Ответ 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)...)), потребляя входной список побитно, так что вся вещь способна работать в постоянном пространстве с оптимизацией).
Вам может потребоваться настроить количество нулей в зависимости от того, какое оборудование вы используете.