haskell - 通过给定的跟踪查找子树 Haskell

Question

我对这个问题很了解。问题是编写一个 haskell 函数跟踪(包括答案​​中的类型声明行)，这将以 Path p 和 BTree 作为输入，返回通过跟踪路径到达的子树树。请注意，(trace p Empty) 应始终返回 Empty。这是我到目前为止的解决方案

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

然后我得到

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
   |                                         ^^^^^^^^

Answer 1

操作符==是type class Eq的成员，因此，如果您想在 Dir 类型上使用运算符 ==，则必须为其派生 Eq 类型类:

data Dir = Lft | Rght deriving Eq

但是，更好的方法是使用模式匹配而不是与 == 进行比较:

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