haskell - 无方向边缘的完全有序的 Ord 实例？

Question

我正在尝试为无方向的边缘创建数据类型的实例。Edge 1 2 == Edge 2 1(即从 1 到 2 的边与从 2 到 1 的边相同，方向无关紧要)。

这是数据类型的示例，Eq 实例和 Ord 实例的尝试:

data Edge = Edge Int Int deriving Show
instance Eq Edge where
    (Edge x1 y1) == (Edge x2 y2) = ((x1 == x2 && y1 == y2) || (x1 == y2 && y1 == x2))
instance Ord Edge where
    compare e1@(Edge x1 y1) e2@(Edge x2 y2) = if e1 == e2 
                                              then EQ 
                                              else ????

知道如何获得 totally ordered在这种情况下是 Ord 实例吗？

Answer 1

我的回答与 Thomas 的类似，只是我建议您在构建边时进行归一化。

mkEdge :: Int -> Int -> Edge
mkEdge x y | x <= y    = Edge x y
           | otherwise = Edge y x

现在您知道索引较小的顶点首先出现，deriving (Eq, Ord) 实例将完全按照您的要求执行。您只需确保只使用 mkEdge“智能构造函数”创建边(您可以通过将 Edge 放入模块而不导出 Edge 来实现 构造函数)。