On Fri, Oct 18, 2013 at 3:03 PM, Andreas Abel <[hidden email]> wrote:
Implement support for mutually recursive modules? ;) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Niklas Hambüchen
On Thu, Oct 17, 2013 at 2:52 PM, Niklas Hambüchen <[hidden email]> wrote:
> Can the Data.List <-> Data.Set issue be resolved? > > Is it OK to introduce a cyclic dependency between the two, making use of > a .boot.hs file? Data.List and Data.Set aren't even members of the same package. So hs-boot files won't help. -- Dan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> Data.List and Data.Set aren't even members of the same package. So
> hs-boot files won't help. Damn, you are right. I even mentioned this myself earlier. It would need a set in base. I wonder if it was ok to use the Data.Set implementation internally in base, without exposing it. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Niklas Hambüchen wrote:
> It would need a set in base. I wonder if it was ok to use the Data.Set > implementation internally in base, without exposing it. Ah yes, this is what stopped previous attempts at getting ordNub in. The GHC team is very keen on getting more things *out* of base. Unless something has changed, getting them to include new things in base, even if hidden, would be extremely difficult. Adding additional dependencies and maintenance burdens would add extra work for the overburdened GHC team and slow the GHC release cycle. How about adding a module named something like Data.List.Nub to containers and putting ordNub in there? Or just go back to the idea of putting it in Data.Set. -Yitz _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
With such a big speedup and not a lot of downside, I'd really rather it wind up central enough to be used in preference to nub wherever possible (including in base!). Perhaps they can duplicate the minimum functionality necessary from Data.Set, internally behind the scenes? Alternatively, maybe we can move nub out of base? On Fri, Oct 18, 2013 at 11:47 AM, Yitzchak Gale <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
David Thomas wrote:
> With such a big speedup and not a lot of downside That is far from proven, and frankly, almost certainly untrue. But again, it isn't the point here. There *are* case where you do need nubOrd, and those cases are common enough for it to make sense to get it into the libraries. > I'd really rather it wind up central enough to be used in > preference to nub wherever possible You are welcome to your own preference. I, and many other experienced Haskellers I know, prefer nub in many cases. Let's just make both easily available please. > (including in base!). I wouldn't mind having ordNub in base. But let's at least get it in somewhere convenient and easily usable. If you focus the energy on trying to get it into base, this proposal will likely die the same death as all previous attempts. > Perhaps they can duplicate the minimum functionality > necessary from Data.Set, internally behind the scenes? Why should the GHC team agree to the maintenance burden of that? They have enough of a challenge keeping up with the work they already have. But you know what, give it a try. Just don't get stuck on that point if you meet with resistance. > Alternatively, maybe we can move nub out of base? No. nub is part of the Haskell standard, so it's required to be there. Even if you disagree with my view that it should be there on its own merits. -Yitz _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by David Thomas
On Fri, Oct 18, 2013 at 3:13 PM, David Thomas <[hidden email]> wrote:
> With such a big speedup and not a lot of downside, I'd really rather it wind > up central enough to be used in preference to nub wherever possible > (including in base!). Perhaps they can duplicate the minimum functionality > necessary from Data.Set, internally behind the scenes? Alternatively, maybe > we can move nub out of base? The string 'nub' does not appear anywhere (that I can find) in base outside of Data.List. All occurrences of 'nub' in Data.List are in the definition and export of nub and nubBy, except one use of nubBy in unionBy, which cannot switch to ordNub, and would have to have its own alternate function. Of all the libraries packaged with GHC, the only one I see that uses nub outside of tests is Cabal, which already depends on containers. And in fact, one of the libraries I grepped through _was_ containers, because it's already about as close as you can get to being in base without actually being there, and is certainly as close as many other things will be once we split up base into more packages. I don't think it's really accurate to suggest that containers is less core than base. It's not just, 'some library.' -- Dan _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Clark Gaebel-2
On Mon, Jul 15, 2013 at 11:21:39PM -0400, Clark Gaebel wrote:
> As a tangent, can anyone think of a data structure for which you can > write an Ord instance but Hashable/Eq is impossible (or prove > otherwise)? How about the converse? A conversation on #haskell brought back to mind this question, which I'm not sure was ever answered. Is there a type with an Eq instance for which on Ord instance could not also be provided (i.e. I'm interested in Clark's "converse")? One answer is that I could write data A = A deriving Eq and then not export the constructor. That would make it impossible to write an Ord instance. However, I'm more interested in the question "morally" or "in principle". If we think about algebraic datatypes built from sums and products of base types, which have both Eq and Ord, and the function type construct, which prevents both Eq and Ord, it seems that the two always go together, in principle. Am I missing anything more exotic? IORef's have Eq but not Ord. Is there a good reason for that? Would Ord break "referential transparency" somehow? I doubt it. How about STRef? It seems more likely they shouldn't have Ord. Any thoughts? Tom _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Niklas Hambüchen
I think ordNub in Data.Set, hashNub in Data.HashSet or somewhere, and bitsNub in Data.Bits (for FiniteBits things). On Jul 14, 2013 7:21 AM, "Niklas Hambüchen" <[hidden email]> wrote:
tldr: nub is abnormally slow, we shouldn't use it, but we do. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Er.. that last might be to hard. But Data.IntSet can support its own nub version. On Jan 1, 2015 8:42 AM, "David Feuer" <[hidden email]> wrote:
_______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Niklas Hambüchen
Tom Ellis wrote: > Is there a type with an Eq instance for which on Ord instance could not also > be provided (i.e. I'm interested in Clark's "converse")? Of course. One of the very many examples is Complex. One can say we can compare complex numbers, by their absolute value. That is true; however we end up in a position where compare x y returns EQ but x==y returns False. In general, Ord represents total order. There are many structures on which total order cannot be established. Take nodes in the tree, the Tree data type. One can compare nodes by taking a parent to be less than any of its children. But then two brothers are not comparable. Searching for "partial orders" and pre-orders gives many more examples. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, Jan 01, 2015 at 08:58:35AM -0500, [hidden email] wrote:
> Tom Ellis wrote: > > Is there a type with an Eq instance for which on Ord instance could not also > > be provided (i.e. I'm interested in Clark's "converse")? > > Of course. One of the very many examples is Complex. One can say we > can compare complex numbers, by their absolute value. That is true; > however we end up in a position where compare x y returns EQ but x==y > returns False. I don't understand your objection. `Complex a` isomorphic to `(a, a)` which can be totally ordered. (The complex field cannot be given a total order *compatible with the field structure*, but that's not relevant to my question.) > In general, Ord represents total order. There are many structures on > which total order cannot be established. Take nodes in the tree, the > Tree data type. One can compare nodes by taking a parent to be less > than any of its children. But then two brothers are not > comparable. Searching for "partial orders" and pre-orders gives many > more examples. I think you may be missing the intent of my question. I am merely asking whether there is a type which supports a (law abiding) Eq instance that cannot support a (law abiding) Ord instance. Whether that Ord instance is compatible with additional structures on that type is beside the point. Tom _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Instance Ord a where Is law abiding for any type. So there is no type that cannot support a law abiding Ord instance. On Jan 1, 2015 3:04 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 08:58:35AM -0500, [hidden email] wrote: _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, Jan 01, 2015 at 03:12:15PM +0100, Atze van der Ploeg wrote:
> Instance Ord a where > _ <= _ = True > > Is law abiding for any type. So there is no type that cannot support a law > abiding Ord instance. So let me clarify that I want (<=) to be a total order in the sense that it is * reflexive * symmetric * transitive and `(x <= y) && (y <= x)` implies that `x == y`. Tom _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Taking Instance Eq a where Then it has all the properties you mentoined On Jan 1, 2015 3:14 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:12:15PM +0100, Atze van der Ploeg wrote: _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Tom Ellis
On Thu, Jan 01, 2015 at 02:14:16PM +0000, Tom Ellis wrote:
> So let me clarify that I want (<=) to be a total order in the sense that it > is > > * reflexive > * symmetric > * transitive > > and `(x <= y) && (y <= x)` implies that `x == y`. (*) Correction: I mean "antisymmetric" not "symmetric". Anti-symmetry is exactly this condition (*). Futhermore I want (==) to be at least as fine-grained as extensional equivalence. Tom _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
In reply to this post by Atze van der Ploeg
On Thu, Jan 01, 2015 at 03:17:13PM +0100, Atze van der Ploeg wrote:
> Taking > > Instance Eq a where > _ == _ = True > > Then it has all the properties you mentoined Right, hence my latest clarification that "Futhermore I want (==) to be at least as fine-grained as extensional equivalence.". _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
> i want it to be at least as fine grained as extensional equivalence Then see Oleg's comment or am i missing something here? On Jan 1, 2015 3:19 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:17:13PM +0100, Atze van der Ploeg wrote: _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
On Thu, Jan 01, 2015 at 03:22:55PM +0100, Atze van der Ploeg wrote:
> > i want it to be at least as fine grained as extensional equivalence > > Then see Oleg's comment or am i missing something here? Perhaps you could explain Oleg's comment. I don't understand it. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Your question is if I understand correctly, whether we can think of a type that has a law abiding Eq instance that gives equality as fine grained as extensional equality (meaning structural equality?) but for which no law abing instance of Ord can be given such that a <= b && a >= b ==> a == b This boils down to the question whether on each set with an equality relation defined on it a total ordering (consistent with the equality relation) can also be defined. One counterexample is the complex numbers. Does that answer your question? Cheers! On Jan 1, 2015 3:27 PM, "Tom Ellis" <[hidden email]> wrote:
On Thu, Jan 01, 2015 at 03:22:55PM +0100, Atze van der Ploeg wrote: _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe |
Free forum by Nabble | Edit this page |