Variants & structural ordering

Variants & structural ordering

[Damien Guichard]

[-- Attachment #1: Type: text/plain, Size: 544 bytes --]


Hi everybody,

Typically, when you declare:

type card =
  | Card of int
  | Jack
  | Queen
  | King
  | Ace
  ;;

The relation you wish is:

Card(2) < ...< Card(10) < Jack < Queen < King < Ace

And that's what you get when using F#.

However when using OCaml here is what you get:

Jack < Queen < King < Ace < Card(2) < ...< Card(10)

And the work-around is: 

type card =
  | Card of int
  | Jack of unit
  | Queen of unit
  | King of unit
  | Ace of unit
  ;;

Is this a bug or a feature ?
Will it change in a foreseable future ?

- damien

[-- Attachment #2: Type: text/html, Size: 1238 bytes --]

Re: [Caml-list] Variants & structural ordering

[Berke Durak]

Damien Guichard a écrit :

> Hi everybody,

Hello

> Typically, when you declare:
>  
> type card =
>   | Card of int
>   | Jack
>   | Queen
>   | King
>   | Ace
>   ;;
>  
> The relation you wish is:
>  
> Card(2) < ...< Card(10) < Jack < Queen < King < Ace
>  
> And that's what you get when using F#.

Thanks for this bit of knowledge about F#.

> However when using OCaml here is what you get:
>  
> Jack < Queen < King < Ace < Card(2) < ...< Card(10)
>  
> And the work-around is:
>  
> type card =
>   | Card of int
>   | Jack of unit
>   | Queen of unit
>   | King of unit
>   | Ace of unit
>   ;;
>  
> Is this a bug or a feature ?

Neither:  You are not supposed to assume anything on the way compare orders non-primitive types.

Constructors without arguments are represented as integers, which, as primitive types,
come before blocks, which are used to represent the values of constructors with arguments.

The "compare" functions give an ad-hoc order, the only guarantee being that it
will be a good ordering.  I think you can safely assume that it won't change accross Ocaml
releases (unless you start using a new VM.)

In practice, people often assume that the components of tuples and records are compared
in the same order as their components are given.  Relying on the order of enumerated types
is more risky: you provide a good example of this.

> Will it change in a foreseable future ?

I really don't think so and even if it did, there is no reason why it would change in the
way that would be useful to you in that particular case, and even then, it would be risky
to depend on that behaviour, and, besides, what's the point?  Simply use something like:

let max_card = 10

let int_of_card = function
| Card n -> assert(n < max_card); n
| Jack -> max_card
| Queen -> max_card + 1
| King -> max_card + 2

let compare c1 c2 = compare (int_of_card c1) (int_of_card c2)
-- 
Berke DURAK

Re: [Caml-list] Variants & structural ordering

[Oliver Bandel]

Zitat von Damien Guichard <alphablock@orange.fr>:

[...]
> Is this a bug or a feature ?
[...]

It's F# ;-)


Ciao,
   Oliver

Re: [Caml-list] Variants & structural ordering

[Jon Harrop]

On Tuesday 05 February 2008 08:21:21 Damien Guichard wrote:
> Hi everybody,
>
> Typically, when you declare:
>
> type card =
>
>   | Card of int
>   | Jack
>   | Queen
>   | King
>   | Ace
>
>   ;;
>
> The relation you wish is:
>
> Card(2) < ...< Card(10) < Jack < Queen < King < Ace
>
> And that's what you get when using F#.

Comparison is OCaml's achilles heel and this is one (minor) manifestation of 
that. The ability to develop a program and break a use of polymorphic 
comparison buried within it without knowing is far more serious and has 
caused many people untold grief in the past.

SML's equality types are a slight improvement but F# and Haskell's solutions 
are the best way forward AFAICT. OCaml will never be fixed in this sense but, 
hopefully, a next-generation FPL implementation will solve these problems 
without sacrificing OCaml's other benefits.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e

Re: [Caml-list] Variants & structural ordering

[Michaël Grünewald]

"Damien Guichard" <alphablock@orange.fr> writes:

> Hi everybody,
>  
> Typically, when you declare:
>  
> type card =
>   | Card of int
>   | Jack
>   | Queen
>   | King
>   | Ace
>   ;;
>  
> The relation you wish is:
>  
> Card(2) < ...< Card(10) < Jack < Queen < King < Ace
>  
> And that's what you get when using F#.
>  
> However when using OCaml here is what you get:
>  
> Jack < Queen < King < Ace < Card(2) < ...< Card(10)
>  
> And the work-around is:
>  
> type card =
>   | Card of int
>   | Jack of unit
>   | Queen of unit
>   | King of unit
>   | Ace of unit
>   ;;
>  
> Is this a bug or a feature ?
> Will it change in a foreseable future ?

Conventions are always a bit arbitrary, aren't they? To me, the
natural order with cards are:
  Card(7) < Card(8) < Queen < King < Card(10)< Ace < Card(9) < Jack
and
  Card(7) < Card(8) < Card(9) < Jack < Queen < King < Card(10)< Ace
(yes there are two natural orders).

Furthermore, I tried your program on a host whose native charset is
KOBAIA-8 (a weird variation on EBCDIC), hold your breath:
  F# behaves there just like OCaml does on your host, and vice-versa!

Computers are good at doing what they are told to, so why don't you
tell them?

The only purpose of a generic `compare' procedure os the easy use of
`Set.Make' and `Map.Make' with random types, isnt't it? It is very bad
to assume it giving any sensible order on non basic types, you sure
have to define `sensible' yourself.
-- 
Michaël

Re: [Caml-list] Variants & structural ordering

[Damien Doligez]

On 2008-02-05, at 09:21, Damien Guichard wrote:

> The relation you wish is:
>
> Card(2) < ...< Card(10) < Jack < Queen < King < Ace

That's funny, depending on the suit I would wish one of the following:

   Card(7) < ... < Card(9) < Jack < Queen < King < Card(10) < Ace
   Card(7) < Card(8) < Queen < King < Card(10) < Ace < Card(9) < Jack

... And no fixed comparison function will ever be able to guess
whether you're comparing trumps.

-- the other Damien

Re: [Caml-list] Variants & structural ordering

[Stéphane Lescuyer]

2008/2/5 Damien Guichard <alphablock@orange.fr>:
> And the answer is: OCaml variants are certainly treated as an initial
> algebra, but not exactly as an enumeration, thus their relative order is not
> meaningfull to the compare function.

Actually it *is* meaningful, but as Berke pointed out, constant
constructors and variant expecting some arguments are treated (and
ordered) separately.
This is explained in detail in Sec. 18.3.4 of the manual
[http://caml.inria.fr/pub/docs/manual-ocaml/manual032.html], and this
is why adding dummy arguments of type unit does the trick.
My point is that it's not as bad as it looks, since you have a way to
"control" (or at least predict) what the order between your different
values will be. This is a difference with polymorphic variants for
instance.
--
Stéphane L.
http://www.lri.fr/~lescuyer

Re: [Caml-list] Variants & structural ordering

[Damien Guichard]

[-- Attachment #1: Type: text/plain, Size: 478 bytes --]


Thanks to all for your answers.

I am aware my code exemple is quite artificial, certainly integers are simpler in this particular case.

My more profound question was: are variants treated as an enumeration or not ?
And the answer is: OCaml variants are certainly treated as an initial algebra, but not exactly as an enumeration, thus their relative order is not meaningfull to the compare function.
And it will not change in near future.

Ok, i can live with that.

- damien

[-- Attachment #2: Type: text/html, Size: 883 bytes --]