[Haskell-cafe] ordNub

[Atze van der Ploeg]

> (That said, I don't understand why this discussion is relevant at all.
> The fact that the ordering exists doesn't mean that one would want to
> declare the Ord instance, like with complex numbers.)

It's not relevant, it's just an intellectual exercise.

For any set with a equality relation there exists a total order relation on
that set consistent with the equality relation. The question is then
whether there exists a set with a computable equality relation such that
there is no computable total order.

I think the following computable function shows that it is always possible
(it chooses an order during queries):

Maintain a table, initially emtpy

As soon as (a <= b) is requested, see if a and b are already in the
table (using
the computatble equality function) , if so, use their ordering in the table.
If an element is not in the table, add it.

Hence the table gives a consistent total order (it depends on which
ordering queries are requested, but that is not relevant?)






2015-01-01 16:06 GMT+01:00 Atze van der Ploeg <atzeus at gmail.com>:

> Nope you're right. Indeed uncompatible with the field structure. Now I'm
> confused :)
>
> I now understand your question, but do not immediately know the answer.
> Anyone?
> On Jan 1, 2015 4:02 PM, "Tom Ellis" <
> tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk> wrote:
>
>> On Thu, Jan 01, 2015 at 03:52:26PM +0100, Atze van der Ploeg wrote:
>> > If we do not require that (a <= b) && (a >= b) ==> a == b (where <= is
>> > from the total ordering and == is from the equality relation) then it is
>> > trivial, take the total ordering forall x y.  x <= y that i mentioned
>> > earlier.
>> >
>> > So the compatiblity with equality (you say field structure) is not
>> besides
>> > the point, in fact antisymmetry means that the ordering corresponds to
>> the
>> > equality relation.
>> >
>> > Clear now or did I misunderstand?
>>
>> Here is my proposed equality and ordering on the complex numbers:
>>
>>     data Complex = Complex (Double, Double) deriving (Eq, Ord)
>>
>> Does this violate any of my requested conditions?
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20150101/24371c26/attachment.html>