[Haskell-cafe] Ord for partially ordered sets

[Jay Sulzberger]

On Fri, 24 Apr 2015, Ivan Lazar Miljenovic <ivan.miljenovic at gmail.com> 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 at gmail.com
> http://IvanMiljenovic.wordpress.com
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>