ハスケル：二分木を平らにする

Question

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

私は最初に(++)を使用して左右の分岐を結合すると考えましたが、悪い場合にはO(n^2)時間かかると考えました。

私はリストを後方に構築することを考えて、(:)を使用して線形時間で追加しました。しかし、私はこのリストを折りたたみ式の関数に送ると、折り畳みを開始する前にツリー全体が横断されるまで待たなければならないと考えて、list fusionを使うことはできません。

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)時間のこの作品は、木の最大の深さに比例したに過ぎない「スタック領域」を取るだろうし、それを消費すると融合することができます。

は、私はその後followingを思い付きました関数（つまり、中間リストは削除されます）？これは木を平坦化する "正しい"方法ですか？

Answer 1

私は融合についてはよく分かりませんが、一般的に再帰関数は融合できないと思います。しかし、あなたがハスケルでリストを扱っているときには、中間リストは通常​​、全体として一度に存在しないことを覚えておいてください - あなたは始まりを知って終わりを計算していないでしょう。終わり（リストの要素と同じくらい多くのステップで）。これは融合ではなく、これは「ストリームの良好な振る舞い」に似ており、出力が段階的に消費される場合はスペース要件が優れていることを意味します。

とにかく、はい、私はこれがツリーを平坦化する最良の方法だと思います。アルゴリズムの出力がリストで、それ以外の場合はリストが未検査で連結が行われている場合、通常はdifference lists（DList秒）が最適な方法です。それらは、「プリペア関数」としてリストを表します。これは、追加するときにトラバースする必要がなくなります。

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

少し拡張しましょう。 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'は末尾再帰型なので、スタックスペースを取らないようにしてください。しかし、それは木の左側を歩いて、ヒープの束を吐き出します。あなたはあなたの例の木の上にそれを起動し、WHNFにそれを減らす場合は、このようなものを取得する必要があります：

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

アルゴリズムはO(N)あるが、それはTipのと同様にNode Sを検討しています。

これは、順番にツリーを平坦化する最も効率的な方法です。 Data.Treeモジュールはflattenの機能hereを持っていますが、これは予約注文トラバーサルを好む以外は同じことをします。

更新：グラフ低減エンジンで

、mainでflattenこのようなグラフが生成されます。WHNFにこれを低減するために

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

を、グラフ低減エンジンは、アンロールされます背骨は[]とNode 2をスタックに押し込む。

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

そして、スタックから2つの引数をポップします。それは、このにグラフを書き換えますflatten'関数を呼び出します。ルートノードはまだWHNFにはないので、グラフリダクションエンジンは背骨を展開し、2:...とNode 1をスタックにプッシュします。

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

そして、スタックから二つの引数をポップアップ表示されます：それは、これにグラフを書き換えますflatten'機能を呼び出します。 WHNFにないルートノードはですが、であるため、グラフリダクションエンジンは背骨を展開し、1:...とTipをスタックにプッシュします。

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

そして、スタックから二つの引数をポップアップ表示されます：それは、これにグラフを書き換えますflatten'機能を呼び出します。現在、WHNFには最大2つのスタックエントリを消費しています（Treeのノードは、追加のスタック領域を必要とするサンクではありません）。

したがって、flatten'は、テール再帰型です。追加のネストされたredexesを評価することなく、自身を置き換えます。 2番目のflatten'は、スタックではなくヒープのサンクのままです。