階層データの "レベル"を数える/取得する

Question

これは正しいタイトルかどうかわかりませんが、他の方法を呼び出す方法はわかりません。 私の宿題は私の宿題です。私は数時間働きました。話題は「機能的なデータ構造」であり、私はちょっと固まっていて、どのように続けるのか分かりません。

は、だから私はこのシグネチャを持つ関数を記述する必要があります。

x = 2 
    3  4 
    6 7  5 

x = Node 2 (Node 3 (Node 6 Empty Empty) (Node 7 Empty Empty)) (Node 4 Empty (Node 5 Empty Empty)) 

だから、それはいくつかの「木」であるデータを-thing：

data Heap e t = Heap { 
contains :: e -> t e -> Maybe Int 
} 

はそれを説明するために、私はこのようないくつかの変数を得ました。

contains heap 2 x returns Just 0 
    contains heap 6 x returns Just 2 
    contains heap 42 x returns Nothing 

だから「ヒープ」の背後にある整数Xに存在する場合、yは木の「レベル」であり、「ジャストY」が返されます「が含まれて」。私の例では、2はレベル0,3を、レベル4はレベル1になります。 それは私の問題がどこにあるのか正確です。私は、整数がツリーにあるかどうかを言うことができる関数を持っていますが、私はその "レベル"（私はそれを呼び出す方法がわかりません）を取得する方法がわかりません。

My機能は、次のようになります。それに

contains = \e t -> case (e,t) of 
    (_,Empty) -> Nothing 
    (e , Node x t1 t2) -> 
     if e == (head (heap2list heap (Node x t1 t2))) 
      then Just 0 
      else if ((contains heap e t1) == Just 0) 
        then Just 0 
        else contains heap e t2 

の整数である場合、それは「ちょうど0」を返さないだろうし、他の「何も」。 ところで、自分で書いた "ヘルパー"機能は使用できません。私が使用できる機能は以下の通りです：

empty :: t e    --Just returns an empty heap 
insert :: e -> t e -> t e --insert an element into a heap 
findMin :: t e -> Maybe e --find Min in a heap 
deleteMin :: t e -> Maybe (t e) -- delete the Min in a heap 
merge :: t e -> t e -> t e  -- merges 2 heaps 
list2heap :: Heap x t -> [x] -> t x -- converts a list into a heap 
heap2list :: Heap x t -> t x -> [x] -- converts a heap into a list 

これらの機能があります。 map、foldl、foldr ...も許可されています。私は質問を短くしていたので、情報が不足していれば、私はそれを編集する準備ができています。

私は非常に助けに感謝します。これは宿題であり、本当に自分でそれをやりたいのですが、ここでこの質問をするのが私の最後の選択です。

ワーキングコード：

contains = \e t -> case (e,t) of 
(_,Empty) -> Nothing 
(e , Node x t1 t2) -> 
    if e == (head (heap2list heap (Node x t1 t2))) 
     then Just 0 
     else if (fmap (+1) (contains heap e t1))== Nothing 
        then (fmap (+1) (contains heap e t2)) 
        else (fmap (+1) (contains heap e t1)) 

今すぐコードが動作していると、すべての「宿題-条件が」満たさが、それは私の意見ではかなり醜いコードのように見えている..私は何とかそれを改装することはできますか？

Answer 1

問題は、仕様が現在不完全であることです。解決策は幅優先または左/右に偏った深さ優先のアルゴリズムですか？のみプレリュード機能を使用して

幅優先溶液は、任意のバイアスされた深さ優先を容易に導出されるべきである

-- Example data structure 
data Tree e = Node e (Tree e) (Tree e) | Empty 

-- Actual definition 
contains e (Node c _ _) 
| e == c = Just 0 
contains e (Node _ l r) = fmap (+ 1) $ case (contains e l, contains e r) of 
              (Just a, Just b) -> Just $ min a b 
              (Just a, _) -> Just a 
              (_, b) -> b 
contains _ Empty = Nothing 

-- Given testdata: 
x = Node 2 (Node 3 (Node 6 Empty Empty) (Node 7 Empty Empty)) (Node 4 Empty (Node 5 Empty Empty)) 

contains 2 x -- Just 0 
contains 6 x -- Just 2 
contains 42 x -- Nothing 

-- unspecified example: 
--   1 
--  1  1 
-- 1 2  1 
-- 2     1 
--      2 

x = Node 1 (Node 1 (Node 1 (Node 2 Empty Empty) Empty) (Node 2 Empty Empty)) (Node 1 Empty (Node 1 Empty (Node 1 Empty (Node 2 Empty Empty)))) 
contains 2 x -- Just 2 = breath-first 
contains 2 x -- Just 3 = left biased depth-first 
contains 2 x -- Just 4 = rigth biased depth-first 

あろう。