[Haskell-cafe] ordNub

[Roman Cheplyaka]

The set of all values of the type is always enumerable (it's even
recursive, since otherwise you wouldn't be able to tell if something is
a value or not).

Since it's enumerable, you can enumerate all values of that type:

  v1, v2, v3, ...

Take x1 < x2 iff x1 precedes x2 in the above sequence. This is obviously
computable.

Roman

On 01/01/15 17:31, Atze van der Ploeg wrote:
>> (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
> <mailto: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
>     <mailto: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 <mailto:Haskell-Cafe at haskell.org>
>         http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>