[Haskell-cafe] Ord for partially ordered sets
jays at panix.com
Fri Apr 24 19:19:10 UTC 2015
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  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)
> : 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.
> Ivan.Miljenovic at gmail.com
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe