1

私は任意のツリーでいくつかの数字の出現回数を見つけたいと思っています.そして、ここに私のコードがありますが、なぜそれが起こるのか分かりません。

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

エラーメッセージは次のとおりです。

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

入力出力は次のようにする必要があります:

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

3 に答える 3

3

関数を非常に簡潔に書くことができます。

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

fromEnumEnumは anを に変換しますInt。幸いなことBoolに、 は実際には であるだけでなく、0 と 1EnumにもFalseマップされますTrue。

于 2012-04-04T13:21:00.620 に答える
2

行にバグがあります

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

あなたはそれxが...本当にこれがTree何のためにあるのか分からないと言っていますif

これは期待どおりに機能します：

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)

ところで: 私はあなたの命名も基本的なアルゴリズムも変更しませんでしたが、これは末尾再帰ではないため、スタックにあまり適していないことに注意してください。

于 2012-04-04T11:15:37.423 に答える
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)))
于 2012-04-04T15:33:25.687 に答える