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) раз, принять "пространство стека" не более чем пропорционально наибольшей глубине дерева и может ли оно быть слито с потребляющей функцией (т.е. промежуточным списком исключено)? Это "правильный" способ сгладить дерево?

Ответ 1

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

В любом случае, да, я думаю, что это лучший способ сгладить дерево. Когда выход алгоритма представляет собой список, но в остальном список не изучен, и происходит конкатенация, тогда списки различий (DList s) обычно являются наилучшим способом идти. Они представляют собой список как "функцию препинания", что устраняет необходимость обхода при добавлении, поскольку добавление - это просто составная функция.

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 []

Это суть реализации, остальная часть может быть получена из этого. Наивный алгоритм сглаживания в DList:

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 - это канонический способ сделать это эффективно, и это что ты наделал.

Ответ 2

flatten' является хвостом рекурсивным, поэтому он не должен занимать пространство стека. Это, однако, будет идти по левой стороне дерева, выплевывая кучу громил в куче. Если вы вызываете его в дереве примеров и сводите его к WHNF, вы должны получить что-то похожее на это:

  :
 / \
1  flatten' Tip :
               / \
              2   flatten' (Node 4) []
                           /      \
                         (Node 3) Tip
                        /       \
                       Tip      Tip

Алгоритм O(N), но он должен изучить Tip, а также Node s.

Это выглядит как наиболее эффективный способ сглаживания дерева в порядке. Модуль Data.Tree имеет flatten функцию здесь, которая делает то же самое, за исключением того, что предпочитает обход предварительного порядка.

Update:

В двигателе сокращения графа 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

И вытащите два аргумента из стека. Корень node по-прежнему не находится в WHNF, поэтому механизм сокращения графа разворачивает позвоночник, нажимая 2:... и Node 1 на стек. Затем он вызовет функцию flatten', которая перепишет график для этого:

                 @
                / \
               /   \
              /     \
             @       :
            / \     / \
           /   \   1   \
          /     \       \
       flatten' Tip      @
                        / \
                       /   \
                      /     :
                     @     / \
                    / \   2   \
                   /  Tip      @
                  /           / \
               flatten'      @  []
                            / \
                           /   \
                          /     \
                       flatten' Node 4
                                /   \
                               /     \
                              /       \
                           Node 3     Tip
                           /   \
                          Tip  Tip

И вытащите два аргумента из стека. Корень node все еще не находится в WHNF, поэтому механизм сокращения графа будет разворачивать позвоночник, нажимая 1:... и Tip на стек. Затем он вызовет функцию flatten', которая перепишет график для этого:

                 :
                / \
               1   \
                    \
                     @
                    / \
                   /   \
                  /     :
                 @     / \
                / \   2   \
               /  Tip      @
              /           / \
           flatten'      @  []
                        / \
                       /   \
                      /     \
                   flatten' Node 4
                            /   \
                           /     \
                          /       \
                       Node 3     Tip
                       /   \
                      Tip  Tip

И вытащите два аргумента из стека. Теперь мы находимся в WHNF, потребляя максимум две записи в стеке (предполагая, что узлы Tree не были разрывами, для которых требуется дополнительное пространство стека для оценки).

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