haskellのバイナリツリー内の変数の出現数を調べる

Question

私は任意のtree.Andでいくつかの数字の出現数を見つけたいと思いますが、ここに私のコードですが、なぜそれが起こるのかわからないエラーが出ます。

ERROR "treeExample.hs":95 - Cannot infer instance 
*** Instance : Eq (Tree a) 
*** Expression : occurst 

入力出力がなければなりません：

data Tree a = Empty | Node (a ,Tree a,Tree a) deriving (Show) 

occurst _ Empty = 0  -- this line occurs error 
occurst a (Node (x,left,right)) = if x==Empty then 0 
      else if a==x then 1 + (occurst a left) + (occurst a right) 
      else (occurst a left) + (occurst a right) 


j=let t = Node (3 , Node (2 , Node (1 , Empty , Empty) , Node (1 , Empty , Empty)),Node  (1 , Node (2 , Node (1 , Empty , Empty) , Node (1 , Empty , Empty)),Node (1,Empty,Empty))) 
    in occurst 1 t 

エラーメッセージということです

occurst 1 t -> 6 
occurst 2 t -> 2 
occurst 3 t ->1 
occurst 4 t ->0 

Answer 1

1.へ

ここには尾の再帰バージョンがあります：

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) 

occurst x t = go 0 [t] where 
    go n [] = n 
    go n (t:ts) = case t of 
        Empty  -> go n ts 
        Node a l r -> let n' = n + fromEnum (a==x) 
           in n' `seq` go n' (l:r:ts) 

j = occurst 1 t where 
    t = (Node 3 
     (Node 2 
      (Node 1 Empty Empty) 
      (Node 1 Empty Empty)) 
     (Node 1 
      (Node 2 
      (Node 1 Empty Empty) 
      (Node 1 Empty Empty)) 
      (Node 1 Empty Empty))) 

Answer 2

はあなたがxことを言っている

occurst a (Node (x,left,right)) = if x==Empty then 0 

ラインにバグがありますですところで

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

occurst _ Empty = 0 
occurst a (Node (x,left,right)) = 
      if a==x then 1 + (occurst a left) + (occurst a right) 
      else (occurst a left) + (occurst a right) 

：私はあなたの命名も、あなたの基本的なアルゴリズムを変更しなかったが、この1がありますのでご注意ください...本当にこのifが

のためにこの1つは期待どおりに動作しますが何であるかを知りませんテール再帰的ではないので、非常にスタックに優しいわけではありません。

Answer 3

あなたは非常に簡潔にあなたの関数を書くことができます。

occurst _ Empty = 0 
occurst a (Node (x,left,right)) = 
    fromEnum (x==a) + (occurst a left) + (occurst a right) 

fromEnumがIntからEnumを変換し、幸いだけでなくBool実際Enumですが、Falseマップ0へとTrue