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. Значит, это все?
(Обратите внимание, что этот раздел основан на ответах на this предыдущий вопрос.)
Нет! Этот трюк только отодвигает проблему в другое место. Вместо функции без хвостовой рекурсии, которая использует много места в стеке, теперь у нас есть функция с хвостовой рекурсией, которая потребляет санки (непримененные функции), которые потенциально сами могут занимать много места. К счастью, нам не нужно работать с произвольными функциями — на самом деле их всего три вида.
\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, и по мере рекурсии функций они продолжают помещать в стек новые аргументы, которые представляют собой либо новые деревья для исследования (всякий раз, когда вызывается 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. Так вот что я должен использовать?
Честно говоря, ваша оригинальная версия без хвостовой рекурсии, вероятно, в порядке. Новые версии не более эффективны с точки зрения использования пространства (они всегда должны хранить список деревьев, которые вы собираетесь обрабатывать следующими), но у них есть то преимущество, что деревья, которые будут обрабатываться следующими, хранятся в куче, а не в стек - и в куче гораздо больше места.
Возможно, вы захотите взглянуть на частично хвостовую рекурсивную функцию в ответе Инго, которая поможет в случае, когда ваши деревья крайне несбалансированы.
person
Chris Taylor
schedule
18.01.2014
depthTailRecдля получения результата, будет неdepthTailRec, аmax. - person Ingo schedule 18.01.2014