完全有序的Ord实例用于无方向边缘？

作者: 浮华丶
发布时间: 2025-05-11 03:46:45 (21小时前)
转自：

3 条回复

0#
回复此人
十二* | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 只需将边缘连接的顶点视为无序集（巧合的是卡片2）而不是两个单独的元素以任意顺序： </p> <pre> <code> instance Ord Edge where compare e1@(Edge x1 y1) e2@(Edge x2 y2) = compare (sort [x1,y1]) (sort [x2,y2]) </code> </pre> <P> 甚至使用实际集： </p> <pre> <code> data EdgeS = EdgeS (Set Int) deriving (Show, Eq) instance Ord EdgeS where compare (EdgeS a) (EdgeS b) = compare a b </code> </pre> <P> 甚至可以推导出这个实例（至于 <code> Eq </code> ）。如果你愿意，你可以创建一个特殊的构造函数： </p> <pre> <code> mkEdge : Int -> Int -> EdgeS mkEdge a b = EdgeS (S.fromList [a,b]) </code> </pre> <P> 还有一些测试： </p> <pre> <code> > compare (mkEdge 1 2) (mkEdge 2 1) EQ > compare (mkEdge 1 2) (mkEdge 3 1) LT > compare (mkEdge 1 2) (mkEdge 1 3) LT </code> </pre> </DIV>

编辑
1#
回复此人
Little it | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> <P> 我的答案类似于Thomas的，除了我建议你在构造边缘时进行标准化。 </p> <pre> <code> mkEdge :: Int -> Int -> Edge mkEdge x y | x <= y = Edge x y | otherwise = Edge y x </code> </pre> <P> 现在您知道具有较小索引的顶点首先出现，而且 <code> deriving (Eq, Ord) </code> 实例将完全符合您的要求。你只需要确保你只用它创建边 <code> mkEdge </code> “智能构造”（你可以通过推杆来做到这一点） <code> Edge </code> 在一个模块而不是导出 <code> Edge </code> 构造函数）。 </p> </DIV>

编辑

登录后才能参与评论