Totally ordered Ord instance for directionless Edge?

I'm trying to create an instance of a data type for a directionless edge. Edge 1 2 == Edge 2 1 (i.e. Edge from 1 to 2 is the same as Edge from 2 to 1, direction doesn't matter).

Here's an example of of the data type, and Eq instance and an attempt at an Ord instance:

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 ????

Any idea how to get a totally ordered Ord instance in this case?

My answer is similar to Thomas's, except I recommend that you normalize when you construct the edge.

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

Now you know that the vertex with the smaller index appears first, and the deriving (Eq, Ord) instances will do exactly what you want. You just have to make sure you only create edges with the mkEdge "smart constructor" (you can do this by putting Edge in a module and not exporting the Edge constructor).

Just think of the vertices the edge connects as unordered sets (coincidentally of cardinallity 2) instead of two individual elements in an arbitrary order:

instance Ord Edge where
  compare e1@(Edge x1 y1) e2@(Edge x2 y2) = compare (sort [x1,y1]) (sort [x2,y2])

Or even use actual sets:

data EdgeS = EdgeS (Set Int) deriving (Show, Eq)

instance Ord EdgeS where
    compare (EdgeS a) (EdgeS b) = compare a b

And this instance can even be derived (as for Eq). If you'd like, you can make a special constructor:

mkEdge : Int -> Int -> EdgeS
mkEdge a b = EdgeS (S.fromList [a,b])

And some tests:

> compare (mkEdge 1 2) (mkEdge 2 1)
EQ
> compare (mkEdge 1 2) (mkEdge 3 1)
LT
> compare (mkEdge 1 2) (mkEdge 1 3)
LT