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)

fromEnum将 an 转换Enum为 an Int，幸运的是不仅Bool实际上是 an Enum，而且False映射到 0 和True1。

于 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 回答