find subtree by given trace Hakell

user_7180149 0
Viewed 63

I am stock on this problem. The problem is Write a haskell function trace (including the type declaration line in your answer), which will take a Path p and a BTree as input, returns the subtree that you arrive at by tracing the path in tree. Note that (trace p Empty) should always return Empty. Here is my solution so far 

data BTree a = Empty 
             | BNode a ( BTree a ) ( BTree a ) deriving (Show)
data Dir = Lft |Rght
type Path = [Dir]

tree = BNode 1 (  BNode 2 (BNode 4 (Empty) (Empty)) (BNode 5 (Empty) (Empty)) ) ( BNode 3 Empty Empty)

tree1 = BNode 1 (  BNode 2 (BNode 4 (Empty) (Empty)) (BNode 5 (Empty) (Empty)) ) (  BNode 2 (BNode 4 (Empty) (Empty)) (BNode 5 (BNode 3 Empty Empty) (Empty)) )

-- 1.
trace :: Path -> BTree a -> BTree a
trace  p Empty =  Empty 
trace [] a =  a 
trace  (x:xs) (BNode b left right) = if x == Lft then trace xs left else trace xs right

then i got 

No instance for (Eq Dir) arising from a use of ‘==’

    • In the expression: x == Lft
      In the expression:
        if x == Lft then trace xs left else trace xs right
      In an equation for ‘trace’:
          trace (x : xs) (BNode b left right)
            = if x == Lft then trace xs left else trace xs right
   |
14 | trace  (x:xs) (BNode b left right) = if x == Lft then trace xs left else trace xs right
   |                                         ^^^^^^^^
haskell
1 Answers

Operator == is a member of type class Eq, so if you want to use operator == on your Dir type, you have to derive the Eq type class for it:

data Dir = Lft | Rght deriving Eq

However, a better way would be to use pattern matching instead of comparing with ==:

trace  p Empty =  Empty 
trace [] a =  a 
trace (Lft:xs) (BNode _ left _) = trace xs left 
trace (Rght:xs) (BNode _ _ right) = trace xs right
user_1802860
Related