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 [hidden email] http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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? _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 24 April 2015 at 23:17, Tom Ellis
<[hidden email]> 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 [hidden email] http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On Fri, Apr 24, 2015 at 11:27:46PM +1000, Ivan Lazar Miljenovic wrote:
> On 24 April 2015 at 23:17, Tom Ellis > <[hidden email]> 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. Ah, so it's a case of adding a valid Ord instance that isn't a natural one for the particular datatype. If you really need something like that, for example to add your graphs to a Data.Set, then I would suggest a newtype might be appropriate. Tom _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Ivan Lazar Miljenovic
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 > Data.IntMap, which I believe are themselves partially ordered), and I'm > torn as to 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. _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 25 April 2015 at 00:01, Henning Thielemann
<[hidden email]> 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 Data.IntMap, >> which I believe are themselves partially ordered), and I'm torn as to 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. -- Ivan Lazar Miljenovic [hidden email] http://IvanMiljenovic.wordpress.com _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Ivan Lazar Miljenovic
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.html mainly to use it for maintaining sets of incomparable elements: https://hackage.haskell.org/package/Agda-2.4.2/docs/Agda-Utils-Favorites.html > 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 [hidden email] http://www2.tcs.ifi.lmu.de/~abel/ _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
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 <[hidden email]> wrote: On 04/24/2015 03:06 PM, Ivan Lazar Miljenovic wrote: _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Tom Ellis
>> 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? > >False. The operators aren't a problem for this reason. The real problem is what does `compare` return? On Fri, Apr 24, 2015 at 1:32 PM, Ertugrul Söylemez <[hidden email]> wrote: >> 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? > > False. > > > Greets, > Ertugrul > > _______________________________________________ > Haskell-Cafe mailing list > [hidden email] > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe > Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Ivan Lazar Miljenovic
hrm, wouldn't your proposed extension be largely accomplished by using Record pun and Record WildCards? eg {-# LANGUAGE RecordWildCards #-} {-# LANGUAGE RecordPuns #-} module Foo where data Relation a = Rel{related :: a -> a ->Bool,unrelated :: a -> a -> Bool} foo :: Relation A -> A -> A -> Bool foo Rel{..} x y = related x y ------ or am i over looking something? I do realize this may not quite be what youre suggesting, and if so, could you help me understand better? :) On Fri, Apr 24, 2015 at 4:26 PM, Ertugrul Söylemez <[hidden email]> wrote: > 3. NonStrictPoSet, which is the class of all partially ordered _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
On 25/04/15 15:51, Ertugrul Söylemez wrote:
>> hrm, wouldn't your proposed extension be largely accomplished by using >> Record pun and Record WildCards? > > A part of it would, but it wouldn't preserve operators. For example > instead of `x r.<> y` you would have to write `(<>) r x y`. Not at all. {-# LANGUAGE RecordWildCards #-} import Prelude hiding (sum) data Monoid a = Monoid { empty :: a, (<>) :: a -> a -> a } sum :: Num a => Monoid a sum = Monoid 0 (+) three :: Integer three = let Monoid{..} = sum in 1 <> 2 > Other class features are not accessible, > most notably type-level features like associated types. Associated types become additional type variables of the record type. A class class C a where type T a is essentially equivalent to class C a t | a -> t But the functional dependency is not enforceable on the value level (isn't the whole point of this discussion not to restrict what "instances" can be defined), so you end up with class C a t, a simple MPTC. > Also defaults are not available. Now this is a good point. > The idea is that a record would be completely equivalent to a class with > the only difference being that you define values instead of instances, > that there are no constraints on which values can exist and that those > values must be passed explicitly to functions as regular arguments. Except we already have regular records (aka data types) which satisfy 90% of the requirements, and adding another language construct to satisfy those remaining 10% feels wrong to me. I'd rather improve the existing construct. Roman _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries signature.asc (836 bytes) Download Attachment |
Isn't your associated type here more like a dependent record field/ existential that we can kinda expose?
This does seem to veer into first class module territory. Especially wrt needing first class types in a fashion. Have you had a chance to peruse the Andreas Rossberg 1ml paper on embedding first class modules into f omega that has been circulating? Perhaps there are ideas There that could be adapted. Especially since core is an augmented f omega
On Saturday, April 25, 2015, Ertugrul Söylemez <[hidden email]> wrote: >>> hrm, wouldn't your proposed extension be largely accomplished by _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Ivan Lazar Miljenovic
On Fri, Apr 24, 2015 at 9:06 AM, Ivan Lazar Miljenovic
<[hidden email]> 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 [hidden email] 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" <[hidden email]> пише:
On Fri, Apr 24, 2015 at 9:06 AM, Ivan Lazar Miljenovic _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Ivan Lazar Miljenovic
On Fri, Apr 24, 2015 at 10:23 AM, Ivan Lazar Miljenovic <[hidden email]> wrote:
On 25 April 2015 at 00:01, Henning Thielemann 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 _______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |