On Fri, 24 Apr 2015, Ivan Lazar Miljenovic wrote:

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

Of course these type-classes (I hope I am using the word correctly) should be standard: 1. Ord, which is the class of all totally ordered set-like things 2. PoSet, which is the class of all partially ordered set-like things 3. NonStrictPoSet, which is the class of all partially ordered set-like things, but without the requirement that a <= b and b <= a implies a Equal b. 4. Things like above, but with the requirement of a Zero, with the requirement of a One, and the requirement fo both a Zero and a One. oo--JS.

Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe