时间戳

首页 > 解决方案 > 通过给定的跟踪 Hakell 查找子树

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

问题描述

我对这个问题很感兴趣。问题是编写一个haskell函数跟踪（包括你答案中的类型声明行），它将一个路径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
   |                                         ^^^^^^^^

标签： haskell

解决方案

Operator==是type classEq的成员，所以如果你想==在你的Dir类型上使用 operator，你必须为它派生Eqtype class：

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

推荐阅读