1

i want to find the number of occurrences of some number in any tree.And here is my code but it gives an error which i can not find why it happens.

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 message is that:

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

INput Outputs must be :

occurst 1 t -> 6
occurst 2 t -> 2
occurst 3 t ->1
occurst 4 t ->0
oiyio
  • 5,219
  • 4
  • 42
  • 54
  • Why does the `Node` need a tuple? What's wrong with `Node a (Tree a) (Tree a)`? – pat Apr 04 '12 at 15:24

3 Answers3

3

You can write your function very concisely:

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

fromEnum converts an Enum to an Int, and fortunately not only Bool is actually an Enum, but False maps to 0 and True to 1.

Landei
  • 54,104
  • 13
  • 100
  • 195
2

There is a bug in the line

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

you are saying that x is a Tree ... really don't know what this if is for

This one will work as expected:

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)

BTW: I did not change your naming nor your basic algorithm but please note that this one is not very stack-friendly as it's not tail-recursive.

Random Dev
  • 51,810
  • 9
  • 92
  • 119
  • 2
    They don't need to tell Haskell that Tree is an instance of Eq --- the whole trying-to-compare-a-Tree thing is a bug (in this function). – dave4420 Apr 04 '12 at 11:38
  • Dave is right sorry - that what you get if you just do what the compiler tells you ;) – Random Dev Apr 04 '12 at 12:09
  • How would you make this tail recursive? Would you accumulate a list of sub-trees yet to be visited? Is that more efficient than just letting the stack to it? – pat Apr 04 '12 at 15:23
  • Continuations don't magically turn a linear space algorithm into a constant space one. – Luis Casillas Apr 04 '12 at 19:16
  • the question was for a tail-recursive algorithm ... but never mind, that was and is not the subject here (you can find a question on that subject here: http://stackoverflow.com/questions/9323036/tail-recursive-function-to-find-depth-of-a-tree-in-ocaml) – Random Dev Apr 04 '12 at 20:20
1

Here's a tail recursive version:

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)))
pat
  • 12,587
  • 1
  • 23
  • 52