algorithm - Haskell：二分木を平らにする

Question

後者の処理のために、バイナリツリーをリストにフラット化することを考えていました。

最初は(++)左右の枝をつなぐことを考えましたが、最悪の場合はO(n^2)時間がかかると思いました。

(:)次に、線形時間で前に追加するために使用して、リストを逆方向に作成することを考えました。ただし、このリストをfold-like関数に送信すると、ツリー全体がトラバースされるまで待機してから折り畳みを開始できるため、listfusionを使用できないと思いました。

それから私は次のことを思いついた：

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 でリストを扱っている場合、通常、中間リストは一度に全体として存在するわけではないことに注意してください。最初はわかっていても、最後は計算していないので、後で最初を捨ててわかることになります。最後（リストの要素と同じ数のステップで）。これはフュージョンではなく、「ストリームの適切な動作」に似ており、出力が段階的に消費される場合に必要なスペースが改善されることを意味します。

とにかく、はい、これが木を平らにする最良の方法だと思います。アルゴリズムの出力がリストであるが、それ以外の場合はリストが検査されておらず、連結が行われている場合、差分リスト( DLists) が通常最善の方法です。それらはリストを「プリペンダー関数」として表します。これにより、追加するときにトラバーサルの必要がなくなります。追加は単なる関数合成であるためです。

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

これらは実装の要点であり、残りはそこから導き出すことができます。sの単純な平坦化アルゴリズムDListは次のとおりです。

flatten :: Tree a -> DList a
flatten (Node x left right) = flatten left `append` fromList [x] `append` flatten right
flatten Tip = fromList []

少し拡張してみましょう。2 番目の方程式から始めます。

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' is tail recursive, so it shouldn't take any stack space. It will however walk down the left side of the tree, spitting out a bunch of thunks in the heap. If you invoke it on your example tree, and reduce it to WHNF, you should get something that looks like this:

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

The algorithm is O(N), but it has to examine the Tips as well as the Nodes.

This looks to be the most efficient way to flatten your tree in-order. The Data.Tree module has a flatten function here which does much the same thing, except it prefers a pre-order traversal.

Update:

In a graph reduction engine, the flatten in main will generate a graph like this:

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

In order to reduce this to WHNF, the graph reduction engine will unroll the spine, pushing the [] and the Node 2 onto the stack. It will then invoke the flatten' function, which will rewrite the graph to this:

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

And will pop the two arguments from the stack. The root node is still not in WHNF, so the graph reduction engine will unroll the spine, pushing the 2:... and the Node 1 onto the stack. It will then invoke the flatten' function, which will rewrite the graph to this:

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

And will pop the two arguments from the stack. The root node is still not in WHNF, so the graph reduction engine will unroll the spine, pushing the 1:... and the Tip onto the stack. It will then invoke the flatten' function, which will rewrite the graph to this:

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

And will pop the two arguments from the stack. We are now in WHNF, having consumed a maximum of two stack entries (assuming the Tree nodes were not thunks that required additional stack space to evaluate).

So, flatten' is tail-recursive. It replaces itself without having to evaluate additional nested redexes. The second flatten' remains a thunk in the heap, not the stack.