Haskell:重载==图ADT

Question

我有一个图形声明,我需要在Haskell中重载"=="运算符(本书中的问题).

data Node a = Node {
label :: a,
adjacent :: [(a,Int)]
} deriving Show

data Network a = Graph [Node a] deriving Show

基本上,如果它们具有相同的顶点和边缘,则两个图是相等的(但是网络数据类型中的节点可以是不同的顺序以及节点数据类型中的相邻顶点的列表).有一些困难,任何帮助将不胜感激.

提前致谢.

注意:我的问题是使用等式检查,而不是使用类型类实例的语法.

Answer 1

如果你不能只使用deriving (Eq, Show)那么你必须手动实现它.

instance (Eq a) => Eq (Node a) where
    n1 == n2 = (* Implement the equality check here *)

instance (Eq a) => Eq (Network a) where
    g1 == g2 = (* Implement the equality check here *)

这就是派生声明自动为您做的事情.

如果你想要更多关于类型类的话,我喜欢学习Haskell的解释.

如果您需要有关实际相等性检查的帮助,请使用Data.Map该fromList函数.

至于节点,这个代码片段应该这样做

(==) = (==) `on` label

或者更明确

n1 == n2 = label n1 == label n2

Answer 2

这是你在找什么？

import Data.Function (on)
import qualified Data.Map as M

instance Ord a => Eq (Network a) where
    (==) = (==) `on` f where
        f :: Ord a => Network a -> M.Map a (M.Map a Int)
        f (Graph nodes) = M.fromList $ map g nodes
        g :: Ord a => Node a -> (a, M.Map a Int)
        g node = (label node, M.fromList $ adjacent node)

这个实现的作用:

• 将每个网络转换为地图
• 测试这些地图是否相等

由于地图是无序的(并且原始列表不包含重复项),原始列表的顺序不会影响输出.

您甚至可以更好地更改您的Node和Network陈述以使用Maps.