On 24 April 2015 at 23:17, Tom Ellis wrote:

On Fri, Apr 24, 2015 at 11:06:07PM +1000, Ivan Lazar Miljenovic wrote:

...

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

I'm confused. What is supposed to be the result of `g1 <= g2` when `g1` and `g2` are not comparable according to the partial order?

With the proposed patch, it's the result of <= on the underlying [Int]Maps. Does the definition of Ord on Data.Map make sense? e.g. what should be the result of (fromList [(1,'a'), (2,'b'), (3, 'c')]) <= (fromList [(1,'a'), (4,'d')])? What about (fromList [(1,'a'), (2,'b'), (3, 'c')]) <= (fromList [(1,'a'), (2,'e')])? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com

On Fri, Apr 24, 2015 at 10:23 AM, Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com> wrote:

On 25 April 2015 at 00:01, Henning Thielemann wrote:

...

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

...

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

...

...

which I believe are themselves partially ordered), and I'm torn as to

Data.IntMap, the

...

...

soundness of adding these instances.

In an application we needed to do some combinatorics of graphs and thus needed Set Graph.

Nonetheless, I think that graph0 < graph1 should be a type error. We can still have a set of Graphs using a newtype.

This could work; the possible problem would be one of efficiency: if it's done directly on the graph datatypes they can use the underlying (ordered) data structure; going purely by the Graph API, there's no guarantees of ordering and thus it would be needed to call sort, even though in practice it's redundant.

Not to endorse any particular decision on the topic of the thread, but I'd point out that there is no problem here from a technical point of view. The Graph API can export a function `compareGraphs :: Graph -> Graph -> Ordering` which uses the underlying representation, but not provide an Ord instance which uses it. Then a user of the library can use `compareGraphs` in an Ord instance for a newtype wrapper, or as an argument to functions like `sortBy`. Regards, Reid Barton

I would be hesitant about adding an Ord instance normally, because there's no clear semantics for it. If we just pass it through to the underlying data structure, it might behave differently depending on how you implement the graph, which is something fgl should ideally abstract over. Maybe you could provide them in a newtype yourself, in the library? You could call it something like GrKey to make it clear that it has an Ord instance for practical reasons rather than because graphs are meaningfully orderable. This just forces people who need the capability to be a bit more explicit about it. On Fri, Apr 24, 2015 at 7:47 AM, Andreas Abel wrote:

On 04/24/2015 03:06 PM, Ivan Lazar Miljenovic wrote:

...

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

I'd say this is harmful, as functions like min and max (and others) rely on the totality of the ordering.

Partial orderings are useful in itself, I implemented my own library

https://hackage.haskell.org/package/Agda-2.4.2/docs/Agda-Utils-PartialOrd.ht...

mainly to use it for maintaining sets of incomparable elements:

https://hackage.haskell.org/package/Agda-2.4.2/docs/Agda-Utils-Favorites.htm...

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

-- Andreas Abel <>< Du bist der geliebte Mensch.

Department of Computer Science and Engineering Chalmers and Gothenburg University, Sweden

andreas.abel@gu.se http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

While this is a bit off-topic, I'd like to add my 5 cents that often adding instances for common type-classes might be "bad" even when it's totally defined for all values, one example is a Monoid instance for HashMap. So, I'd say that if you might be in doubt -- it's better to not add instance at all, since your users have no ability to remove it from their projects (or redefine). 26 квіт. 2015 04:10 "wren romano" пише:

On Fri, Apr 24, 2015 at 9:06 AM, Ivan Lazar Miljenovic wrote:

...

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

Defining Ord instances for types which are not totally ordered is *wrong*.

For example, due to the existence of NaN values, Double/Float are not totally ordered and therefore their Ord instances are buggy. In my logfloat package I have to explicitly add checks to work around the issues introduced by the buggy Ord Double instance. This is why I introduced the PartialOrd class, and I'm not the first one to create such a class. We really ought to have an official PartialOrd class as part of base/Prelude. The only question is whether to use Maybe Ordering or a specially defined PartialOrdering type (the latter optimizing for space and pointer indirection; the former optimizing for reducing code duplication for manipulating the Ordering/PartialOrdering types).

-- Live well, ~wren _______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries