Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-15 Thread Conor McBride
Hi On 14 Mar 2008, at 21:39, Aaron Denney wrote: On 2008-03-14, Conor McBride [EMAIL PROTECTED] wrote: Hi On 13 Mar 2008, at 23:33, Aaron Denney wrote: On 2008-03-13, Conor McBride [EMAIL PROTECTED] wrote: For a suitable notion of = on quotients, and with a suitable abstraction barrier at

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-14 Thread Conor McBride
Hi On 14 Mar 2008, at 03:48, Roman Leshchinskiy wrote: Adrian Hey wrote: I would ask for any correct Eq instance something like the law: (x==y) = True implies x=y (and vice-versa) which implies f x = f y for all definable f which implies (f x == f y) = True (for expression types which are

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-14 Thread Adrian Hey
Dan Weston wrote: 6.3.2 (The Ord Class): The Ord class is used for totally ordered datatypes. This *requires* that it be absolutely impossible in valid code to distinguish equivalent (in the EQ sense, not the == sense) things via the functions of Ord. The intended interpretation of these

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-14 Thread Roman Leshchinskiy
Conor McBride wrote: Hi On 14 Mar 2008, at 03:48, Roman Leshchinskiy wrote: Adrian Hey wrote: I would ask for any correct Eq instance something like the law: (x==y) = True implies x=y (and vice-versa) which implies f x = f y for all definable f which implies (f x == f y) = True (for

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-14 Thread John Meacham
Note that even if you wanted Eq to mean observational equality, you still can't perform that kind of reordering or 'sort' optimizations without running into trouble. for a not contrived at all example: data Id = Id { idIdent :: Int, idFreeVarCache :: [Id] } instance Eq Id where x == y =

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Adrian Hey
[EMAIL PROTECTED] wrote: G'day all. Adrian Hey wrote: This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a function which can discriminate

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Luke Palmer
On Thu, Mar 13, 2008 at 1:00 AM, Adrian Hey [EMAIL PROTECTED] wrote: AFAICT the report is ambiguous about this, or at least the non-intutive equality semantics are not at all clear to me from what I can see in the Eq class definition (para 6.3.1). I think an the absence of any clear and

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Luke Palmer
On Thu, Mar 13, 2008 at 3:02 AM, Adrian Hey [EMAIL PROTECTED] wrote: The report doesn't state that for all Ints, (x==y = True) implies that x=y. There's no reason to suppose the Int instance is in any way special, so do you really seriously consider the possibility that this might not hold

Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-13 Thread Adrian Hey
Hello All, I'm top posting because I'm getting bored and frustrated with this thread and I don't want to respond detail to everything Aaron has said below. Aaron: Where are you getting this equivalence stuff from? Searching the report for the word equivalence the only remotely relevant section

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Adrian Hey
Luke Palmer wrote: On Thu, Mar 13, 2008 at 1:00 AM, Adrian Hey [EMAIL PROTECTED] wrote: AFAICT the report is ambiguous about this, or at least the non-intutive equality semantics are not at all clear to me from what I can see in the Eq class definition (para 6.3.1). I think an the absence of

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Adrian Hey
Luke Palmer wrote: On Thu, Mar 13, 2008 at 3:02 AM, Adrian Hey [EMAIL PROTECTED] wrote: The report doesn't state that for all Ints, (x==y = True) implies that x=y. There's no reason to suppose the Int instance is in any way special, so do you really seriously consider the possibility that

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Adrian Hey
Aaron Denney wrote: so do you really seriously consider the possibility that this might not hold in your Int related code? if (x==y) then f x else g x y might not mean the same as.. if (x==y) then f y else g x y In Int code, of course not, because I know the types, and I know the behaviour

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-13 Thread Conor McBride
Hi folks I'm late into this thread, so apologies if I'm being dim. On 13 Mar 2008, at 16:17, [EMAIL PROTECTED] wrote: Adrian Hey [EMAIL PROTECTED] wrote: I would ask for any correct Eq instance something like the law: (x==y) = True implies x=y (and vice-versa) I wish I knew what =

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread David Menendez
On Wed, Mar 12, 2008 at 4:29 PM, Aaron Denney [EMAIL PROTECTED] wrote: When defining max, yes, you must take care to make sure it useable for cases when Eq is an equivalence relation, rather than equality. If you're writing library code, then it won't generally know whether Eq means true

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread ajb
G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: I take it you mean something like .. Err... yes, I did. Where's the Eq instance for OrdWrap? Omitted for brevity. This may or may not satisfy the law: (compare a b) = EQ implies (a == b) = True. I think everbody agrees about that, but I

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Conor McBride
Hi On 13 Mar 2008, at 22:28, [EMAIL PROTECTED] wrote: G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: What's disputed is whether or not this law should hold: (a == b) = True implies a = b Apart from possibly your good self, I don't think this is disputed. Quotient types, as noted

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Adrian Hey
[EMAIL PROTECTED] wrote: What's disputed is whether or not this law should hold: (a == b) = True implies a = b Apart from possibly your good self, I don't think this is disputed. If that's supposed it imply you think I'm in a minority of one I don't think you've been following this thread

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread ajb
G'day all. Quoting Conor McBride [EMAIL PROTECTED]: How depressing! Sorry, I don't understand that. Quotient types are good, but they're not the whole story. They just happen to be one use case with a solid history behind them. it's just that we need to manage information hiding

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Conor McBride
Hi On 13 Mar 2008, at 23:33, Aaron Denney wrote: On 2008-03-13, Conor McBride [EMAIL PROTECTED] wrote: Hi On 13 Mar 2008, at 22:28, [EMAIL PROTECTED] wrote: G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: What's disputed is whether or not this law should hold: (a == b) = True implies a

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread ajb
G'day all. Quoting Adrian Hey [EMAIL PROTECTED]: If that's supposed it imply you think I'm in a minority of one I don't think you've been following this thread very well. Sorry, that was a bit of hyperbole. Even the report uses the word equality in the prose. Indeed, and the only

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-13 Thread Conor McBride
Hi On 13 Mar 2008, at 23:42, [EMAIL PROTECTED] wrote: Conor McBride [EMAIL PROTECTED] responded to my comment: (mapMonotonic should of course be removed, too, or specified to fail (preferably in some MonadZero) if the precondition is violated, which should still be implementable in linear

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-13 Thread Robert Dockins
On Thursday 13 March 2008 07:33:12 pm Aaron Denney wrote: [snip] I've seen mention of difficulties with Data.Map, and edison, but not in enough detail to really grasp what the problems are. Until I do, my natural bias (which I'm trying to resist, really) is that it's a matter of lazy coding,

Re: Some clarity please! (was Re: [Haskell-cafe] Re: (flawed?) benchmark : sort)

2008-03-13 Thread Roman Leshchinskiy
Adrian Hey wrote: I would ask for any correct Eq instance something like the law: (x==y) = True implies x=y (and vice-versa) which implies f x = f y for all definable f which implies (f x == f y) = True (for expression types which are instances of Eq). This pretty much requires structural

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Denis Bueno
On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey [EMAIL PROTECTED] wrote: and sorting is meant to be a permutation, so we happily have the situation where this has a correct answer: 2. Anything else is incorrect. Isn't 3 also a permutation? Why is it incorrect? Because it is not

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Adrian Hey
Denis Bueno wrote: On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey [EMAIL PROTECTED] wrote: and sorting is meant to be a permutation, so we happily have the situation where this has a correct answer: 2. Anything else is incorrect. Isn't 3 also a permutation? Why is it incorrect?

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Derek Gladding
Speaking as someone who often has to answer questions along the lines of why isn't my code generating the results I want on your system?, I wouldn't call it evil, just commonly mistaken for Real. NaN breaks most assumptions about ordering: (NaN = _) == false (NaN == _) == false (NaN = _) ==

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Remi Turk
On Tue, Mar 11, 2008 at 01:43:36AM -0400, Brandon S. Allbery KF8NH wrote: On Mar 11, 2008, at 0:20 , Chaddaï Fouché wrote: 2008/3/11, David Menendez [EMAIL PROTECTED]: I think Adrian is just arguing that a == b should imply f a == f b, for all definable f, in which case it doesn't *matter*

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Ketil Malde
Adrian Hey [EMAIL PROTECTED] writes: So really I think the docs have this backwards. It's sortBy that implements a stable sort (assuming a suitably sane comparison function I guess) and apparently sort is whatever you get from (sortBy compare). But this is unduly restrictive on possible

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Jules Bean
Adrian Hey wrote: Denis Bueno wrote: On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey [EMAIL PROTECTED] wrote: and sorting is meant to be a permutation, so we happily have the situation where this has a correct answer: 2. Anything else is incorrect. Isn't 3 also a permutation? Why is

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Jules Bean
Derek Gladding wrote: Speaking as someone who often has to answer questions along the lines of why isn't my code generating the results I want on your system?, I wouldn't call it evil, just commonly mistaken for Real. Yes, of course. Double is an excellent example since it indicates that

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Adrian Hey
Ketil Malde wrote: Adrian Hey [EMAIL PROTECTED] writes: So really I think the docs have this backwards. It's sortBy that implements a stable sort (assuming a suitably sane comparison function I guess) and apparently sort is whatever you get from (sortBy compare). But this is unduly restrictive

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Lennart Augustsson
I agree, I view == as some kind of equivalence relation in Haskell, and not a congruence relation (which would force x==y = f x == f y). Of course, the Haskell type system isn't strong enough to enforce anything more than it being a function returning a boolean. -- Lennart On Wed, Mar 12, 2008

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Adrian Hey
Jules Bean wrote: Adrian Hey wrote: This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a function which can discriminate between

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Adrian Hey
Remi Turk wrote: I wouldn't bet on it either: Prelude 0.0 == -0.0 True Prelude isNegativeZero 0.0 == isNegativeZero (-0.0) False Although isNegativeZero might be considered a ``private, internal interface that exposes implementation details.'' Interesting example. So is the correct

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Adrian Hey
Aaron Denney wrote: On 2008-03-11, Adrian Hey [EMAIL PROTECTED] wrote: Having tried this approach myself too (with the clone) I can confirm that *this way lies madness*, so in future I will not be making any effort to define or respect sane, unambiguous and stable behaviour for insane Eq/Ord

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Lennart Augustsson
I'd say that any polymorphic code that assumes that x==y implies x=y is broken. But apart from that, floating point numbers break all kinds of laws that we might expect to hold. Even so, they are convenient to have instances of various classes. On Wed, Mar 12, 2008 at 7:31 PM, Adrian Hey [EMAIL

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread ajb
G'day all. Adrian Hey wrote: This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a function which can discriminate between [a,a],[a,b],[b,a],[b,b]

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Krzysztof Skrzętnicki
In OCaml you have sort and fastsort - the latter doesn't have to be stable. It currently is, because fastsort = sort. I think it is a good thing to leave people an option, if there is something important to choose. On Thu, Mar 13, 2008 at 12:48 AM, [EMAIL PROTECTED] wrote: G'day all. Adrian

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread David Menendez
On Wed, Mar 12, 2008 at 7:48 PM, [EMAIL PROTECTED] wrote: Adrian Hey wrote: This might be a reasonable thing to say about *sortBy*, but not sort as the ordering of equal elements should not be observable (for any correct instance of Ord). It should be impossible to implement a

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread ajb
G'day all. Quoting David Menendez [EMAIL PROTECTED]: Adrian is arguing that compare a b == EQ should imply compare (f a) (f b) == EQ for all functions f (excluding odd stuff). Thus, the problem with your example would be in the Ord instance, not the sort function. Understood, and the

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-12 Thread Dan Licata
On Mar12, [EMAIL PROTECTED] wrote: G'day all. Quoting David Menendez [EMAIL PROTECTED]: Adrian is arguing that compare a b == EQ should imply compare (f a) (f b) == EQ for all functions f (excluding odd stuff). Thus, the problem with your example would be in the Ord instance, not the sort

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-11 Thread Don Stewart
ok: On 11 Mar 2008, at 12:27 pm, Krzysztof Skrzętnicki wrote: I've written little framework to work on. See sortbench.hs and sortbench.py attachments. Furthermore, I checked Yhc's implementation of sort: it is indeed very fast: I took his earlier code and plugged yhc's sort into

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-11 Thread Adrian Hey
Jonathan Cast wrote: On 10 Mar 2008, at 4:00 AM, Adrian Hey wrote: Neil Mitchell wrote: 2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there are, and

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-11 Thread Krzysztof Skrzętnicki
Are you really sure that your results are correct? I obviously did all my tests with -O2 on. Please rerun your tests on the new framework. Also note that this one contains tests for three cases: - sorted - revsorted - randomized From previous results I can guess that with randomized input Yhc's

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-11 Thread Ketil Malde
Krzysztof Skrzętnicki [EMAIL PROTECTED] writes: The above results are for 100 Ints x 10 runs, but I don't expect any drastic changes in longer run. I leave the interpretation up to you. Might I suggest (also) testing with numbers of smaller magnitude? Lots of collisions is another killer

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi 2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there are, and expanding at the end. That would be wrong. Consider: data Foo = Foo Int Int instance Ord

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi Can whoever picks this up please try the sort code from Yhc in their comparisons. In my benchmarks it ran up to twice as fast as the GHC code. http://darcs.haskell.org/yhc/src/packages/yhc-base-1.0/Data/List.hs I think what we really need is first quickCheck and timing framework for measuring

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Malcolm Wallace
On 10 Mar 2008, at 08:36, Neil Mitchell wrote: Can whoever picks this up please try the sort code from Yhc in their comparisons. In my benchmarks it ran up to twice as fast as the GHC code. http://darcs.haskell.org/yhc/src/packages/yhc-base-1.0/Data/List.hs I believe the Yhc sort

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Neil Mitchell wrote: 2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there are, and expanding at the end. That would be wrong. Consider: data Foo = Foo Int

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Luke Palmer
On Mon, Mar 10, 2008 at 11:00 AM, Adrian Hey [EMAIL PROTECTED] wrote: Neil Mitchell wrote: 2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b I would consider such an Ord instance to be hopelessly broken, and I don't think it's the responsibility of authors of functions with Ord constraints in their sigs (such as sort) to consider such possibilities

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Adrian Hey wrote: or specify and control the behaviour of their behaviour for such instances. Urk, sorry for the gibberish. I guess I should get into the habit of reading what I write before posting :-) Regards -- Adrian Hey ___ Haskell-Cafe

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Neil Mitchell wrote: Hi instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b I would consider such an Ord instance to be hopelessly broken, and I don't think it's the responsibility of authors of functions with Ord constraints in their sigs (such as sort) to consider

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Dan Doel
On Monday 10 March 2008, Neil Mitchell wrote: That would be wrong. Consider: data Foo = Foo Int Int instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b sort [Foo 1 2, Foo 1 -2] must return the original list back, in that order. You cannot delete things and duplicate them

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi The Eq instance you've given violates the law that (x == y) = True implies x = y. Of course the Haskell standard doesn't specify this law, but it should. Wrong. It shouldn't, it doesn't, and I don't think it even can! The Haskell standard doen't even specify that compare x y = EQ

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Neil Mitchell wrote: Hi The Eq instance you've given violates the law that (x == y) = True implies x = y. Of course the Haskell standard doesn't specify this law, but it should. Wrong. It shouldn't, Should too it doesn't, indeed and I don't think it even can! Well we need to be

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Ketil Malde
Adrian Hey [EMAIL PROTECTED] writes: But seriously, once you admit the possibility that even if x == y it still matters which of x or y is used in expressions than all hell breaks loose. I shudder to think just how much Haskell code there must be out there that is (at best) ambiguious or just

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Bulat Ziganshin wrote: Hello Adrian, Monday, March 10, 2008, 2:00:18 PM, you wrote: instance Ord Foo where compare (Foo a _) (Foo b _) = compare a b I would consider such an Ord instance to be hopelessly broken, and I h. for example, imagine files in file manager sorted by size

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Denis Bueno
On Mon, Mar 10, 2008 at 10:10 AM, Adrian Hey [EMAIL PROTECTED] wrote: The Eq instance you've given violates the law that (x == y) = True implies x = y. Of course the Haskell standard doesn't specify this law, but it should. Unless I'm missing something obvious, the example Neil gave

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Ketil Malde wrote: Adrian Hey [EMAIL PROTECTED] writes: But seriously, once you admit the possibility that even if x == y it still matters which of x or y is used in expressions than all hell breaks loose. I shudder to think just how much Haskell code there must be out there that is (at best)

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi We're talking about *semantic correctness*, not efficiency. If you want to fine tune your code like this you shouldn't be relying on overloaded general purpose function implementations. E.G. the COrdering type used by AVL lib is one way to do this. This lets a combining comparison

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Denis Bueno wrote: On Mon, Mar 10, 2008 at 10:10 AM, Adrian Hey [EMAIL PROTECTED] wrote: The Eq instance you've given violates the law that (x == y) = True implies x = y. Of course the Haskell standard doesn't specify this law, but it should. Unless I'm missing something obvious, the

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Denis Bueno
On Mon, Mar 10, 2008 at 12:19 PM, Adrian Hey [EMAIL PROTECTED] wrote: Denis Bueno wrote: On Mon, Mar 10, 2008 at 10:10 AM, Adrian Hey [EMAIL PROTECTED] wrote: The Eq instance you've given violates the law that (x == y) = True implies x = y. Of course the Haskell standard doesn't

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Kalman Noel
Neil Mitchell wrote: instance Eq Foo where (==) (Foo a _) (Foo b _) = (==) a b [...] Please give the sane law that this ordering violates. I can't see any! The (non-existant) law would be (Eq1) x == y = f x == f y, for all f of appropriate type which is analogous to this

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Neil Mitchell wrote: Hi We're talking about *semantic correctness*, not efficiency. If you want to fine tune your code like this you shouldn't be relying on overloaded general purpose function implementations. E.G. the COrdering type used by AVL lib is one way to do this. This lets a

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Dan Weston
Unfortunately the Haskell standards don't currently specify sane laws for Eq and Ord class instances, but they should. In fact there are requirements in the Haskell98 report: 6.3 Standard Haskell Classes Note the word reasonable in the paragraph below: Default class method declarations

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Krzysztof Skrzętnicki
Ok, my turn now. Let's think about algorithm that takes equivalence relation EQ, ordering relation ORD on abstraction classes generated by this equivalence ( - equivalence classes ) and divides given input elements XS into appropriate classes and then prints them out according to given ordering

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Dan Weston
On the other hand, though the behavior of == is not defined by the Report, it does require in 6.3.1 that if compare is defined, then == must be defined. That strongly implies a semantic causal link (in the Free Theorem kind of way), that the semantics of Ord completely specify the semantics of

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi The Ord class is used for totally ordered datatypes. This *requires* that it be absolutely impossible in valid code to distinguish equivalent (in the EQ sense, not the == sense) things via the functions of Ord. The intended interpretation of these functions is clear and can be taken

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Denis Bueno
On Mon, Mar 10, 2008 at 3:12 PM, Neil Mitchell [EMAIL PROTECTED] wrote: Hi The Ord class is used for totally ordered datatypes. This *requires* that it be absolutely impossible in valid code to distinguish equivalent (in the EQ sense, not the == sense) things via the

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Krzysztof Skrzętnicki
It certainly makes perfect sense, because total order antisymmetry law states that IF a = b AND b = a THEN a = b However it should rather be written IF a = b AND b = a THEN a ~= b, since = could be any equivalence class. However, we can also specify the Ord on type type Foo = Foo Int

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Daniel Fischer
Am Montag, 10. März 2008 20:12 schrieb Neil Mitchell: Hi The Ord class is used for totally ordered datatypes. This *requires* that it be absolutely impossible in valid code to distinguish equivalent (in the EQ sense, not the == sense) things via the functions of Ord. The intended

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Krzysztof Skrzętnicki
No, '=' should not mean an identity but any equivalence relation. Therefore, we can use whatever equivalence relation suits us. The reasoning you provided is IMHO rather blur. Anyway, having possibility of using different equivalence relations is great because they mean different abstraction

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi But antisymmetry means that (x = y) (y = x) == x = y, where '=' means identity. Now what does (should) 'identity' mean? I think you are using the word identity when the right would would be equality. Hence, the answer is, without a doubt, (==). If you define equality, then you are

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Dan Weston
If x = y y = x does not imply that x == y, then Ord has no business being a subclass of Eq. By your logic, there is absolutely no constructive subclassing going on here, only an existence proof of (==) given (=). What is the rational basis of such an existence claim, unless == has the obvious

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi If x = y y = x does not imply that x == y, then Ord has no business being a subclass of Eq. By your logic, there is absolutely no constructive subclassing going on here, only an existence proof of (==) given (=). What is the rational basis of such an existence claim, unless == has

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Adrian Hey
Krzysztof Skrze;tnicki wrote: Ok, my turn now. Let's think about algorithm that takes equivalence relation EQ, ordering relation ORD on abstraction classes generated by this equivalence ( - equivalence classes ) and divides given input elements XS into appropriate classes and then prints them

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Neil Mitchell
Hi (sort [a,b]) in the case we have: (compare a b = EQ) Which of the following 4 possible results are correct/incorrect? 1- [a,a] 2- [a,b] 3- [b,a] 4- [b,b] Fortunately the Haskell sort is meant to be stable, and sorting is meant to be a permutation, so we happily have the situation

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Krzysztof Skrzętnicki
On Mon, Mar 10, 2008 at 10:13 PM, Adrian Hey [EMAIL PROTECTED] wrote: (sort [a,b]) in the case we have: (compare a b = EQ) Which of the following 4 possible results are correct/incorrect? 1- [a,a] 2- [a,b] 3- [b,a] 4- [b,b] I'd say 2 and 3 are sane, while 2 is correct - because we need

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Daniel Fischer
Am Montag, 10. März 2008 21:34 schrieb Neil Mitchell: Hi But antisymmetry means that (x = y) (y = x) == x = y, where '=' means identity. Now what does (should) 'identity' mean? I think you are using the word identity when the right would would be equality. Hence, the answer is, without

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread ajb
G'day all. Quoting Dan Weston [EMAIL PROTECTED]: 6.3.2 (The Ord Class): The Ord class is used for totally ordered datatypes. So... Double shouldn't be there, then? As previously noted, nowhere is it even required that x /= y should do the same thing as not (x == y). Cheers, Andrew Bromage

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Krzysztof Skrzętnicki
I've written little framework to work on. See sortbench.hs and sortbench.pyattachments. Furthermore, I checked Yhc's implementation of sort: it is indeed very fast: [EMAIL PROTECTED] sorting]$ python sortbench.py Benchmark type: OnSorted [1 of 1] Compiling Main ( sortbench.hs,

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Jonathan Cast
On 10 Mar 2008, at 4:00 AM, Adrian Hey wrote: Neil Mitchell wrote: 2) What does it do with duplicate elements in the list? I expect it deletes them. To avoid this, you'd need to use something like fromListWith, keeping track of how many duplicates there are, and expanding at the end.

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Richard A. O'Keefe
On 11 Mar 2008, at 12:27 pm, Krzysztof Skrzętnicki wrote: I've written little framework to work on. See sortbench.hs and sortbench.py attachments. Furthermore, I checked Yhc's implementation of sort: it is indeed very fast: I took his earlier code and plugged yhc's sort into it. Compiling

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-10 Thread Chaddaï Fouché
2008/3/11, David Menendez [EMAIL PROTECTED]: I think Adrian is just arguing that a == b should imply f a == f b, for all definable f, in which case it doesn't *matter* which of two equal elements you choose, because there's no semantic difference. (Actually, it's probably not desirable to

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-09 Thread Dan Doel
On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote: Ok, I did some search and found Data.Map, which can be used to implement pretty fast sorting: import qualified Data.Map as Map treeSort :: Ord a = [a] - [a] treeSort = map (\(x,_) - x ) . Map.toAscList . Map.fromList . map (\x-(x,()))

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-09 Thread Don Stewart
dan.doel: On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote: Ok, I did some search and found Data.Map, which can be used to implement pretty fast sorting: import qualified Data.Map as Map treeSort :: Ord a = [a] - [a] treeSort = map (\(x,_) - x ) . Map.toAscList . Map.fromList .

Re: [Haskell-cafe] Re: (flawed?) benchmark : sort

2008-03-09 Thread Duncan Coutts
On Sun, 2008-03-09 at 23:04 -0400, Dan Doel wrote: On Sunday 09 March 2008, Krzysztof Skrzętnicki wrote: What do you think about this particular function? Some thoughts: 1) To get your function specifically, you could just use Data.Set.Set a instead of Map a (). 2) What does it do