Haskell: Свести бинарное дерево
Я думал о сведении двоичного дерева в список для последующей обработки.
Я впервые подумал об использовании (++) присоединиться к левой и правой ветвям, но потом подумал, что в худшем случае это займет O(n^2) время.
Затем я подумал о создании списка в обратном направлении, используя (:) присоединиться к фронту за линейное время. Однако потом я подумал, что если я отправлю этот список в функцию, похожую на фолд, ему придется подождать, пока не пройдется все дерево, прежде чем он сможет начать сворачивание, и, следовательно, не сможет использовать объединение списков.
Затем я придумал следующее:
data Tree a = Node a (Tree a) (Tree a) | Tip
flatten :: Tree a -> [a]
flatten x = (flatten' x) []
flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l
main =
putStrLn $ show $ flatten $
(Node 2 (Node 1 Tip Tip) (Node 4 (Node 3 Tip Tip) Tip))
Будет ли это работать в O(n) время, взять "пространство стека" не более, чем пропорционально наибольшей глубине дерева, и может ли оно быть объединено с потребляющей функцией (т.е. исключен промежуточный список)? Это "правильный" способ сплющить дерево?
2 ответа
Я не знаю много о слиянии, но я думаю, что рекурсивные функции вообще не могут быть объединены. Но помните, что когда вы работаете со списками в Haskell, промежуточные списки обычно не существуют как единое целое сразу - вы узнаете начало и не вычислили конец, а затем позже выбросите начало и узнаете конец (столько шагов, сколько есть элементов в списке). Это не слияние, это больше похоже на "хорошее поведение потока", и это означает, что требования к пространству будут лучше, если выходные данные потребляются постепенно.
В любом случае, да, я думаю, что это лучший способ сплющить дерево. Когда выходные данные алгоритма представляют собой список, но в остальном список не рассматривается, и происходит объединение, тогда списки различий (DLists) обычно лучший путь. Они представляют список как "функцию prepender", которая устраняет необходимость обхода при добавлении, поскольку добавление - это просто композиция функций.
type DList a = [a] -> [a]
fromList :: [a] -> DList a
fromList xs = \l -> xs ++ l
append :: DList a -> DList a -> DList a
append xs ys = xs . ys
toList :: DList a -> [a]
toList xs = xs []
Это основные элементы реализации, остальное можно извлечь из этого. Наивный алгоритм сглаживания в DLists это:
flatten :: Tree a -> DList a
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right
flatten Tip = fromList []
Давайте сделаем небольшое расширение. Начнем со второго уравнения:
flatten Tip = fromList []
= \l -> [] ++ l
= \l -> l
flatten Tip l = l
Видишь, куда это идет? Теперь первое уравнение:
flatten (Node x left right)
= flatten left `append` fromList [x] `append` flatten right
= flatten left . fromList [x] . flatten right
= flatten left . (\l -> [x] ++ l) . flatten right
= flatten left . (x:) . flatten right
flatten (Node x) left right l
= (flatten left . (x:) . flatten right) l
= flatten left ((x:) (flatten right l))
= flatten left (x : flatten right l)
Что показывает, как DList Формулировка равна вашей функции!
flatten' :: Tree a -> [a] -> [a]
flatten' (Node x left right) l = (flatten' left (x:(flatten' right l)))
flatten' Tip l = l
У меня нет никаких доказательств того, почему DList лучше, чем другие подходы (и в конечном итоге это зависит от того, как вы потребляете свою продукцию), но DList это канонический способ сделать это эффективно, и это то, что вы сделали.
flatten' хвостовой рекурсив, поэтому он не должен занимать место в стеке. Однако он будет спускаться с левой стороны дерева, выплевывая кучу громов в куче. Если вы вызовете его в своем дереве примеров и сократите его до WHNF, вы должны получить что-то похожее на это:
:
/ \
1 flatten' Tip :
/ \
2 flatten' (Node 4) []
/ \
(Node 3) Tip
/ \
Tip Tip
Алгоритм O(N), но он должен изучить Tip а также Node s.
Это выглядит как наиболее эффективный способ упорядочить ваше дерево по порядку. Data.Tree модуль имеет flatten здесь функция, которая делает то же самое, за исключением того, что она предпочитает обход предварительного заказа.
Обновить:
В двигателе сокращения графов flatten в main сгенерирует график следующим образом:
@
/ \
@ []
/ \
/ \
/ \
flatten' Node 2
/ \
/ \
/ \
Node 1 Node 4
/ \ / \
Tip Tip / \
/ \
Node 3 Tip
/ \
Tip Tip
Чтобы уменьшить это до WHNF, механизм сокращения графиков развернет позвоночник, выдвинув [] и Node 2 в стек. Затем он вызовет flatten' функция, которая будет переписывать граф на это:
@
/ \
/ \
/ \
@ :
/ \ / \
/ \ 2 \
/ \ \
flatten' Node 1 \
/ \ \
Tip Tip @
/ \
@ []
/ \
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
И выскочит два аргумента из стека. Корневой узел все еще не находится в WHNF, поэтому механизм сокращения графиков развернет позвоночник, выдвинув 2:... и Node 1 в стек. Затем он вызовет flatten' функция, которая будет переписывать граф на это:
@
/ \
/ \
/ \
@ :
/ \ / \
/ \ 1 \
/ \ \
flatten' Tip @
/ \
/ \
/ :
@ / \
/ \ 2 \
/ Tip @
/ / \
flatten' @ []
/ \
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
И выскочит два аргумента из стека. Корневой узел все еще не находится в WHNF, поэтому механизм сокращения графиков развернет позвоночник, выдвинув 1:... и Tip в стек. Затем он вызовет flatten' функция, которая будет переписывать граф на это:
:
/ \
1 \
\
@
/ \
/ \
/ :
@ / \
/ \ 2 \
/ Tip @
/ / \
flatten' @ []
/ \
/ \
/ \
flatten' Node 4
/ \
/ \
/ \
Node 3 Tip
/ \
Tip Tip
И выскочит два аргумента из стека. Сейчас мы находимся в WHNF, использовав не более двух записей стека (при условии, что Tree узлы не были thunks, которые требовали дополнительного стекового пространства для оценки).
Так, flatten' хвост рекурсивный. Он заменяет себя без необходимости оценивать дополнительные вложенные переопределения. Второй flatten' остается куча в куче, а не в стеке.