ハスケルの枝の深さはどうすればわかりますか？

Question

私はツリーからすべての枝の深さを与え、深さの整数をリストにパックする関数を実装したいと思います。 私は最大と最小を見つける方法を知っていますが、他のものを見つける方法はわかりません。

例の木と私のコード：

data NBaum a = NBlatt a | NKnoten a [NBaum a] 
    deriving(Eq,Show) 

例ツリー：

NKnoten "Sonne"[NKnoten "Jupiter" [NBlatt "Io", NBlatt "Europa", NBlatt "Ganymed", NBlatt "Kallisto"],NKnoten "Mars" [NBlatt "Phobos", NBlatt "Deimos"],NBlatt "Merkur", NBlatt "Venus", NKnoten "Erde" [NBlatt "Mond"]] 

最大深さ：

tdepth (NBlatt a) = 1 
tdepth (NKnoten _ b) = 1 + maximum [tdepth branch | branch <- b] 

最小深さ：私の木のInit

tdepth (NBlatt a) = 1 
tdepth (NKnoten _ b) = 1 + minimum [tdepth branch | branch <- b] 

私が持つツリーの解答は、[2,2,3,3,3,3,3,3,3]です。リストの要素は別の順序を持​​つことができます。

Answer 1

解決策を自分で解決したいかのように聞こえますが、ここではヒントがあります：順序や深さ優先のトラバーサル関数をまだ書いていますか？

トラバーサル関数に深さを記憶する別のパラメータを与えることができます。各再帰呼び出しはそれをインクリメントします。ノードの内容をリストに追加する代わりに、深さを追加します。

まだそれに慣れていない場合は、その関数を書く良い方法は、リストを構成する累積パラメータを追加することです。あなたは空のリストと深さ1でルートから始め、葉ノードに達するたびに、リストの最後に現在の深さを追加します。親ノードでは、現在の深さを、娘の関数を呼び出すことから戻ったリストと連結します。

Answer 2

私は実装されていない再帰呼び出しを左おそらく、このシェルが役立つことがあります。

depths :: (Num b) => NBaum a -> [b] 
depths = go 1 
    where 
    go n (NBlatt _) = [n] 
    go n (NKnoten _ xs) = error "depths.go: not implemented" 

Answer 3

をしてください、それをチェックアウト。考えられるのは、同じ機能がNKnotenの各サブツリーに適用され、結果がconcatを使用して1つのリストにまとめられているということです。

depths :: (Num b) => NBaum a -> [b] 
depths = go 1 
    where 
    go n (NBlatt _) = [n] 
    go n (NKnoten _ xs) = concat (map (go (n+1)) xs)