如何使用树实例创建类型类 Eq？

Question

我想为 Eq 的实例创建一个带有节点标签 n 的三叉树。不仅应该使两棵相同的树相等，而且应该使两棵树通过翻转操作变得相同。所以我想到了这样的事情：

data TernaryTree n = Leaf | Node n (TernaryTree n) (Ternarytree n) (TernaryTree n)

instance Eq TernaryTree where
     Node n l m r == Node n l r m == Node n m l r == Node n m r l == Node n r l m == Node n r m l = True

错误消息是：模式解析错误：(Node n l m r) == (Node n l r m)

Answer 1

你的定义是错误的，因为它类似于以下内容

f :: Int -> Int
f (f (f x)) = x
-- compare it with x == y == z = True

以上代码毫无意义：如何评价它？此外，您甚至不能在同一模式中多次使用一个变量：例如

f :: Int -> Int -> Int
f x x = x    -- wrong

您需要做的是：

instance Eq n => Eq (TernaryTree n) where
  Node n l m r == Node n' l' m' r' =   -- all the variables MUST have distinct names
       (n==n' && l==l' && r==r' && m==m') ||
       (n==n' && l==l' && r==m' && m==r') ||   -- last 2 flipped
       ...                                     -- add all cases here
  Leaf         == Leaf             = True
  _            == _                = False

如果语法看起来令人困惑，您可以将 (==) 放在前缀位置：

instance Eq n => Eq (TernaryTree n) where
  (==) (Node n l m r) (Node n' l' m' r') =
       (n==n' && l==l' && r==r' && m==m') ||
       ...                                     -- add all cases here
  (==) Leaf           Leaf               = True
  (==) _              _                  = False

Answer 2

(==) 只是一个函数。现在，让我们假设它是一个名为 f 的前缀函数。在那种情况下，我们定义一个具体的例子 f 为：

f :: Maybe a -> a
f (Just x) = x
f Nothing = error "nothing!"

因此我们可以对 f 有多个定义。

在你的情况下，这看起来像这样：

instance Eq n => Eq (TernaryTree n) where
  (Node n1 l1 m1 r1) == (Node n2 l2 m2 r2) = (n1 == n2) && ( 
    ((l1 == l2) && (m1 == m2) && (r1 == r2)) ||
    ((l1 == m2) && (l2 == m1) && (r1 == r2)) ||
    ...)

Answer 3

这和其他所有的一样，也许慢一点，但代码更少。

import Data.List (permutations)

data TernaryTree n = Leaf
                   | Node n (TernaryTree n) (Ternarytree n) (TernaryTree n)

instance Eq n => Eq (TernaryTree n) where
  (Node n1 l1 m1 r1) == (Node n2 l2 m2 r2)
    | n1 /= n2 = False
    | otherwise = any (== [l1,m1,r1]) (permutations [l2,m2,r2])

如何使用树实例创建类型类 Eq？

How do I create typeclass Eq by using instance for tree?

tree

haskell

types