Ответ 1
1. Почему ваша функция не рекурсивна?
Для рекурсивной рекурсивной функции все рекурсивные вызовы должны быть в хвостовом положении. Функция находится в положении хвоста, если это последняя вещь, которую нужно вызвать до возвращения функции. В первом примере у вас есть
depth (Branch _ l r) = 1 + max (depth l) (depth r)
что эквивалентно
depth (Branch _ l r) = (+) 1 (max (depth l) (depth r))
чтобы вы могли видеть, что последняя функция, вызванная до возвращения функции, равна (+), поэтому это не является хвостовой рекурсивной. Во втором примере у вас есть
depthTR d (Branch _ l r) = let dl = depthTR (d+1) l
dr = depthTR (d+1) r
in max dl dr
который эквивалентен (после повторного включения всех операторов let) и переупорядочения бит
depthTR d (Branch _ l r) = max (depthTR (d+1) r) (depthTR (d+1) l)
так что вы видите, что последняя функция, вызванная перед возвратом, max, что означает, что это также не хвостовая рекурсия.
2. Как вы могли бы сделать его хвостом рекурсивным?
Вы можете сделать хвостовую рекурсивную функцию, используя стиль продолжения прохождения. Вместо того, чтобы переписывать свою функцию для получения состояния или аккумулятора, вы передаете функцию (называемую продолжением), которая является инструкцией для того, что делать с вычисленным значением - т.е. вместо того, чтобы немедленно вернуться к вызывающему, вы проходите независимо от того, какое значение вы вычислили для продолжения. Это простой трюк для превращения любой функции в хвостовую рекурсивную функцию - даже функции, которые нужно называть себя несколько раз, как это делает depth. Это выглядит примерно так.
depth t = go t id
where
go Empty k = k 0
go (Branch _ l r) k = go l $ \dl ->
go r $ \dr ->
k (1 + max dl dr)
Теперь вы видите, что последняя функция, вызванная в go до ее возвращения, сама является go, поэтому эта функция является хвостовой рекурсивной.
3. Это то, что?
(NB этот раздел извлекает из ответов на этот предыдущий вопрос.)
Нет! Этот "трюк" только отодвигает проблему обратно в другое место. Вместо не-хвостовой рекурсивной функции, которая использует много пространства стека, теперь у нас есть хвостовая рекурсивная функция, которая ест thunks (непримененные функции), которые потенциально могут занимать много места. К счастью, нам не нужно работать с произвольными функциями - на самом деле есть только три вида
-
\dl -> go r (\dr -> k (1 + max dl dr))(который использует свободные переменныеrиk) -
\dr -> k (1 + max dl dr)(со свободными переменнымиkиdl) -
id(без свободных переменных)
Поскольку существует только конечное число функций, мы можем представить их как данные
data Fun a = FunL (Tree a) (Fun a) -- the fields are 'r' and 'k'
| FunR Int (Fun a) -- the fields are 'dl' and 'k'
| FunId
Нам также нужно написать функцию eval, которая рассказывает нам, как оценивать эти "функции" при определенных аргументах. Теперь вы можете переписать функцию как
depth t = go t FunId
where
go Empty k = eval k 0
go (Branch _ l r) k = go l (FunL r k)
eval (FunL r k) d = go r (FunR d k)
eval (FunR dl k) d = eval k (1 + max dl d)
eval (FunId) d = d
Обратите внимание, что оба go и eval имеют вызовы либо в go, либо eval в хвостовом положении, поэтому они представляют собой пару взаимно-хвостовых рекурсивных функций. Таким образом, мы преобразовали версию функции, которая использовала стиль продолжения-передачи в функцию, которая использует данные для представления продолжений, и использует пару взаимно-рекурсивных функций для интерпретации этих данных.
4. Это звучит действительно скомпилировано
Ну, наверное. Но ждать! Мы можем это упростить! Если вы посмотрите на тип данных Fun a, вы увидите, что это фактически список, где каждый элемент является либо Tree a, который мы собираемся вычислить глубину, или это Int, представляющий которую мы вычислили до сих пор.
Какая польза от этого? Ну, этот список фактически представляет стек вызовов из цепочки продолжений из предыдущего раздела. Нажатие нового элемента в списке вызывает новый аргумент в стек вызовов! Поэтому вы можете написать
depth t = go t []
where
go Empty k = eval k 0
go (Branch _ l r) k = go l (Left r : k)
eval (Left r : k) d = go r (Right d : k)
eval (Right dl : k) d = eval k (1 + max dl d)
eval [] d = d
Каждый новый аргумент, который вы нажимаете на стек вызовов, имеет тип Either (Tree a) Int, а в качестве функции recurse они продолжают вставлять новые аргументы в стек, которые являются либо новыми деревьями, которые нужно изучить (когда вызывается go), или максимальная глубина, найденная до сих пор (когда вызывается eval).
Эта стратегия вызова представляет собой первый шаг по пересечению дерева, как вы можете видеть из-за того, что левое дерево всегда сначала исследуется go, в то время как правильное дерево всегда помещается в стек вызовов, который нужно изучить позже. Аргументы только когда-либо выскакивают из стека вызовов (в eval), когда ветвь Empty достигнута и может быть отброшена.
5. Хорошо... что-нибудь еще?
Ну, как только вы заметили, что вы можете превратить алгоритм продолжения передачи в версию, которая имитирует стек вызовов и сначала пересекает глубину дерева, вы можете начать задаваться вопросом, существует ли более простой алгоритм, который пересекает глубину дерева, отслеживая максимальную глубину, обнаруженную до сих пор.
И действительно, есть. Хитрость заключается в том, чтобы сохранить список ветвей, которые вы еще не изучили, вместе с их глубинами и отслеживать максимальную глубину, которую вы видели до сих пор. Похоже на это
depth t = go 0 [(0,t)]
where
go depth [] = depth
go depth (t:ts) = case t of
(d, Empty) -> go (max depth d) ts
(d, Branch _ l r) -> go (max depth d) ((d+1,l):(d+1,r):ts)
Я думаю, что примерно так же просто, как я могу сделать эту функцию в рамках ограничений, обеспечивающих ее хвостовую рекурсивность.
6. Итак, что я должен использовать?
Честно говоря, ваша оригинальная, не хвостовая рекурсивная версия, вероятно, прекрасна. Новые версии не являются более свободными от пространства (всегда нужно хранить список деревьев, которые вы собираетесь обрабатывать дальше), но у них есть преимущество хранения деревьев, которые будут обрабатываться далее в куче, а не на стек - и там больше места на куче.
Возможно, вы захотите взглянуть на частично хвостовую рекурсивную функцию в ответе Инго, что поможет в случае, когда ваши деревья крайне неуравновешены.