[Haskell-cafe] ordNub
Roman Cheplyaka
roma at ro-che.info
Thu Jan 1 16:37:45 UTC 2015
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
>
More information about the Haskell-Cafe
mailing list