2 
data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Eq, Show)

unfoldTree:: (b -> Maybe (b, a, b)) -> b -> Tree a
unfoldTree f b =
    case f b of
      Nothing -> Leaf
      Just (lt, x, rt) -> Node (unfoldTree f lt) x (unfoldTree f rt)

上記の2つの情報を踏まえて、ツリー構築関数を実装するように求められます。

そして私の試みは

treeBuild :: Integer -> Tree Integer
treeBuild 0 = Leaf
treeBuild n = treeUnfold (\b -> if b < 2^n-1 
                then Just(2*b, b + 1, 2*b + 1) 
                else Nothing) 
                0

基本ケースはn=0で正常に機能しますが、関数が完全に間違っていることはわかっています。誰かが私にどのように機能するかを再説明できますか3-tuple Just？通常の展開では、aの最初Justの要素は必要な要素であり、2番目の要素は展開を続行するために使用されますが、これは3タプルでどのように機能しますか？

出力例として： treeBuild 2 ----> Node (Node Leaf 0 Leaf) 1 (Node Leaf 2 Leaf)

Just(2*b, b + 1, 2*b + 1)編集： bが0から始まる場合、ここでJustがどのように機能するかは完全にはわかりませんが、次のようになりJust(0, 1, 0)ますか？実際にbをインクリメントするにはどうすればよいですか？

4

1 に答える 1

5

の定義を貼り付けるときにスペースを省略したと思いますunfoldTree。これでいいの？

unfoldTree fb =
    ... のケース fb

について本質的に意味のあるものは何もありませんが、この特定のケースでは、タプル内の項目が、、およびにバインドされてMaybe (b, a, b)いることがわかります。中間の値は、ノードを作成するために使用され、への再帰呼び出しをシードするために使用されます。unfoldTreeltxrtxltrtunfoldTree

n出力例を説明するために、は常に にバインドされていることに注意してください2。への最初の0引数treeUnfoldは、(\b -> ...)関数が最初にチェック0 < 2^n-1し、次に生成することを意味しますJust (2*0, 0+1, 2*0+1)。

中央0+1の値は、ツリーのルート ノードの値です。b左のサブツリーはis nowを除いて同様に構築され2*0、右のサブツリーは as で構築さbれ2*0+1ます。

2^n - 1これは、ノードでツリーを構築することになっている宿題だと言いました。Leaf値はカウントされず、これらのノードに幅優先の順序で番号を付けたいと思います。うまくいけば、この例があなたを近所に連れて行ってくれるでしょう。その方法は次のとおりです。

treeBuild :: Int -> Tree Int
treeBuild n = treeUnfold (\b -> if b < 2^n - 1
                                   ちょうど (2*b+1, b, 2*b+2)
                                   それ以外はなし) 0

これにたどり着いた方法は、深さ 3 のバイナリ ツリーを描画することです。ルートから始まる0ノードに 、左側のノード1、右側のノード として番号を付けました2。下部のノードには、左から右に で始まり で4終わる番号が付けられ7ます。

これでパターンが表示されます。現在のノードに番号が付けられている場合b、その左と右のノードにはそれぞれ2*b+1との番号が付けられ2*b+2ます。2^n - 1は depth のツリー内のノードの総数であり、n幅優先の順序でノードに番号を付けてNothingいb >= 2^n-1ますn。

于 2013-03-21T02:56:45.950 に答える