[Haskell-cafe] Ord for partially ordered sets

Ivan Lazar Miljenovic ivan.miljenovic at gmail.com
Fri Apr 24 13:06:07 UTC 2015

What is the validity of defining an Ord instance for types for which
mathematically the `compare` function is partially ordered?

Specifically, I have a pull request for fgl [1] to add Ord instances
for the graph types (based upon the Ord instances for Data.Map and
Data.IntMap, which I believe are themselves partially ordered), and
I'm torn as to the soundness of adding these instances.  It might be
useful in Haskell code (the example given is to use graphs as keys in
a Map) but mathematically-speaking it is not possible to compare two
arbitrary graphs.

What are people's thoughts on this?  What's more important: potential
usefulness/practicality or mathematical correctness?

(Of course, the correct answer is to have a function of type a -> a ->
Maybe Ordering :p)

[1]: https://github.com/haskell/fgl/pull/11

Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com

More information about the Haskell-Cafe mailing list