Finden der Anzahl der Vorkommen einer Variablen in einem Binärbaum in Haskell

Question

Ich möchte die Anzahl der Vorkommen einer Zahl in einem Baum zu finden.Und hier ist mein Code, aber es gibt einen Fehler, den ich nicht finden kann, warum es passiert .

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 

Fehlermeldung ist, dass:

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

INput Ausgänge müssen:

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

Answer 1

Hier ist ein Schwanz rekursive 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))) 

Answer 2

Es gibt einen Fehler in der Leitung ist

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

Sie sagen, dass x ist ein Tree ... wirklich nicht wissen, was diese if für ist

Dieser wird wie erwartet:

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: Ich habe nicht Ihre Benennung ändern noch Ihre grundlegenden Algorithmus, aber bitte beachten Sie, dass diese ist nicht sehr stapelfreundlich, da es nicht tail rekursiv ist.

Answer 3

Sie können Ihre Funktion sehr prägnant schreiben:

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

fromEnum eine Enum zu einem Int umwandelt, und zum Glück nicht nur Bool ist eigentlich ein Enum, aber False Karten auf 0 und True bis 1.