Haskell: сгладить двоичное дерево

Question

Я думал о выравнивании двоичного дерева в списке, для последней обработки.

Сначала я подумал об использовании (++), чтобы присоединиться к левым и правым ветвям, но затем подумал, что в худшем случае это займет O(n^2) раз.

Я подумал о том, чтобы создать список назад, используя (:), чтобы добавить к фронту в линейном времени. Однако тогда я подумал, что если я отправлю этот список в функцию, подобную складке, ему придется подождать, пока все дерево не пройдет, прежде чем оно начнет складываться, и, следовательно, не может использовать list fusion.

я тогда придумал following:

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

Answer 1

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

В любом случае, да, я думаю, что это лучший способ сгладить дерево. Когда выход алгоритма представляет собой список, но в остальном список не изучен, и происходит конкатенация, тогда difference lists (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 канонический способ сделать это эффективно, и это что ты наделал.

Answer 2

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

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

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

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

Обновление:

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

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