Annoying behaviour of OCaml

Annoying behaviour of OCaml

[Thomas Fischbacher]

Yesterday, we were bitten quite badly by a rude surprise where OCaml
behaved in a rather different way from what we would have expected:

===>

compare "cat" "dog";; (* gives -1, just as strcmp would do *)

compare "def" "abcde";; (* gives 1, again, as expected *)

compare (1,5) (1,7);;  (* gives -1, comparison seems to be
			  lexicographic on containers... *)

compare [|1;2;3|] [|4;5|];; (* ...but actially is not: this gives 1,
			       supposedly because the second list is
			       shorter than the first.
			    *)

compare ((17,23),[|8;9;10|]) ((12,21),[|8;9|]);;

(* This situation is quite similar to the one where encountered
    the problem. We tried to use Array.sort in conjunction with
    "compare" to sort some abstract specifications of contributions
    to a sparse matrix of the form ((row,column),array_of_factors)
    by row, assuming that "compare" would do the job through
    lexicographical order, but actually, it does not. In this case,
    the result is +1 rather than -1!
*)

compare ((17,23),[8;9;10]) ((12,21),[8;9]);;

(* Interestingly, this also gives +1, so using "compare" and replacing
    arrays by lists commutes. This is rather strange, as walking a list
    to determine its length certainly is more effort than implementing
    lexicographical comparison...
*)

<===

Let us see for comparison how other H.M.-typed languages behave:
Haskell (hugs):

Haskell 98 mode: Restart with command line option -98 to enable extensions

Type :? for help
Hugs.Base> ((17,23),[8,9,10]) < ((12,21),[8,9])
False
Hugs.Base>

...just as about everybody would expect.

SML, by the way, does not seem to extend ">" to container types.

I think it would be a *very* good idea to provide
compare_lexicographically in addition to compare as a pre-defined built-in,
as this is (1) what many people want to do, (2) it cannot be implemented
without resorting to either C or black magic, and (3) it would not change
the behaviour of already existing code that uses "compare".

-- 
best regards,
Thomas Fischbacher
t.fischbacher@soton.ac.uk

Re: [Caml-list] Annoying behaviour of OCaml

[Jean-Christophe Filliâtre]

Thomas Fischbacher wrote:
> 
> Haskell 98 mode: Restart with command line option -98 to enable extensions
> 
> Type :? for help
> Hugs.Base> ((17,23),[8,9,10]) < ((12,21),[8,9])
> False
> Hugs.Base>

and with ocaml:

        Objective Caml version 3.10.1+rc1

# ((17,23),[8;9;10]) < ((12,21),[8;9]);;
- : bool = false

So where's the difference?

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/

Re: [Caml-list] Annoying behaviour of OCaml

[Berke Durak]

Thomas Fischbacher a écrit :
> 
> Yesterday, we were bitten quite badly by a rude surprise where OCaml
> behaved in a rather different way from what we would have expected:

Surprising.  I didn't notice before that arrays are compared 
hierarchically and not lexicographically.

> I think it would be a *very* good idea to provide
> compare_lexicographically in addition to compare as a pre-defined built-in,
> as this is (1) what many people want to do, (2) it cannot be implemented
> without resorting to either C or black magic, and (3) it would not change
> the behaviour of already existing code that uses "compare".

Lexicographic order is quite natural for recursive sum types such as lists.

As for arrays, I guess the intent was to accelerate cases where the
array lengths are different.  Assume you are sorting a random array of
arrays of random lengths, but whose contents have large common prefixes. 
  You'll have to do more work to sort these with lexicographical ordering.

OTOH this reasoning would also apply to strings which are compared 
lexicographically...  Ocaml's ways are mysterious!

However I don't think it's worth cluttering the standard library with
compare_lexicographically as it can be easily implemented.
--
Berke DURAK

Re: [Caml-list] Annoying behaviour of OCaml

[Eric Cooper]

On Thu, Jan 10, 2008 at 02:52:26PM +0000, Thomas Fischbacher wrote:
> compare [|1;2;3|] [|4;5|];; (* ...but actially is not: this gives 1,
> 			       supposedly because the second list is
> 			       shorter than the first.
> 			    *)

This is indeed unexpected behavior:
    # compare "123" "45";;
    - : int = -1
    # compare [1;2;3] [4;5];;    
    - : int = -1
    # compare [|1;2;3|] [|4;5|];;
    - : int = 1

-- 
Eric Cooper             e c c @ c m u . e d u

Re: [Caml-list] Annoying behaviour of OCaml

[Brian Hurt]

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

Eric Cooper wrote:

>On Thu, Jan 10, 2008 at 02:52:26PM +0000, Thomas Fischbacher wrote:
>  
>
>>compare [|1;2;3|] [|4;5|];; (* ...but actially is not: this gives 1,
>>			       supposedly because the second list is
>>			       shorter than the first.
>>			    *)
>>    
>>
>
>This is indeed unexpected behavior:
>    # compare "123" "45";;
>    - : int = -1
>    # compare [1;2;3] [4;5];;    
>    - : int = -1
>    # compare [|1;2;3|] [|4;5|];;
>    - : int = 1
>
>  
>
It it?  I mean, all I ever read into compare was that it returned a 
*consistent* ordering- for example, if a < b and b < c, then a < c.  
Note that a *specific* ordering was ever gaurenteed- and if I wanted a 
specific ordering, I should implement it myself.  It certainly wasn't 
ever gaurenteed that the ordering would be consistent with some other 
(or any other) language.

Ordering arrays based on length is an obvious performance advantage- 
it's an O(1) comparison, independent of the length of the arrays (or the 
cost of comparing two elements of the arrays).

Brian


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

Re: [Caml-list] Annoying behaviour of OCaml

[Thomas Fischbacher]

Brian Hurt wrote:

>>This is indeed unexpected behavior:
>>    # compare "123" "45";;
>>    - : int = -1
>>    # compare [1;2;3] [4;5];;    
>>    - : int = -1
>>    # compare [|1;2;3|] [|4;5|];;
>>    - : int = 1
>>
> It it?  I mean, all I ever read into compare was that it returned a 
> *consistent* ordering- for example, if a < b and b < c, then a < c.  

Well, yes, this is what the manual says and guarantees. However,
everybody does expect lexicographical ordering here. In particular,
it would be natural to have

compare (Array.of_list x) (Array.of_list y) = compare x y

As this does not hold (see above), this is an unexpected pitfall.

> Note that a *specific* ordering was ever gaurenteed- and if I wanted a 
> specific ordering, I should implement it myself.

Well... if we take e.g.:

# [|1;2;3|] < [|4;5|];;
- : bool = false

...how would you implement (non-polymorphic!) general lexicographic
order in OCaml without resorting to C?

-- 
best regards,
Thomas Fischbacher
t.fischbacher@soton.ac.uk

Re: [Caml-list] Annoying behaviour of OCaml

[Christophe Raffalli]

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


> 
> Well, yes, this is what the manual says and guarantees. However,
> everybody does expect lexicographical ordering here. In particular,
> it would be natural to have
> 

No, I expect as fast as possible ordering to speed up Sets and Maps
as much as possible.

It is easy to write in C or in Caml (with Obj) polymorphic lexicographic comparison
if you need it. You could even start with the original compare of OCaml in compare.c if I remember well.

Now remains the question of having both a "fast_compare" (comparing size first for both string and
arrays which is not the case now) and "lex_compare" in the library ... But it does not bother me too
much.

> compare (Array.of_list x) (Array.of_list y) = compare x y

This would become true if the hd of the list was at the rigth of the tl like in

type 'a mylist =
  Nil
| Cons of 'a mylist * 'a

let rec mylist_to_list = function
  Nil -> []
| Cons(l,x) -> x::mylist_to_list l

let my_list_to_array l = Array.of_list (mylist_to_list l)

let l1 = Cons(Nil,1)
let l2 = Cons(Cons(Nil,2),1)
let b = compare (my_list_to_array l1) (my_list_to_array l2) = compare l1 l2

So this property is not really that natural.

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von Thomas Fischbacher <tf@functionality.de>:

> Brian Hurt wrote:
>
> >>This is indeed unexpected behavior:
> >>    # compare "123" "45";;
> >>    - : int = -1
> >>    # compare [1;2;3] [4;5];;
> >>    - : int = -1
> >>    # compare [|1;2;3|] [|4;5|];;
> >>    - : int = 1
> >>
> > It it?  I mean, all I ever read into compare was that it returned a
> > *consistent* ordering- for example, if a < b and b < c, then a < c.
>
> Well, yes, this is what the manual says and guarantees. However,
> everybody

Can you prove "everybody"?

Even if this would be the case, not what we expect
is of importance, but what the documentation says.
If there's a difference between documentation and bahaviour,
then there is a bug (in the documentation, or in the
implementation, or both).


> does expect lexicographical ordering here. In particular,
> it would be natural to have
>
> compare (Array.of_list x) (Array.of_list y) = compare x y

Well, this is one way one could expect it.
But there might be reasons not to do so.
This is mixig two paradigms, and so this might be
used differently.
The same is when using strings: OCaml's strings aren't functional.
You can change them in-place.
This is not following purely functional style, but that's not what
OCaml is prtends to provide.

I normally write my comparison functions by myself, to extract the
elements of a datastructure that should be comapred, but then
use comapre on it (even if other functions might be faster).
If I would compare more complex data structures, I would look into the
documentation. I also was surprised on that language-comparison, but now
slightly remember, this was mentioned on this list before.

Look here,

  compare [|1;2;3;5|] [|1;2;3;4|];;
- : int = 1
# compare [|1;2;3;4|] [|1;2;3;5|];;
- : int = -1
#


Nice. If the size is equal, it compares "as expected". :-)
Isn't that enough? ;-)
 Now it's clear, how to write your own function ;-)


>
> As this does not hold (see above), this is an unexpected pitfall.

That's your opinion.
There might be other opinions on it.

I would say, it's a design-decision.
And apparantly different then you would do it.

Ciao,
   Oliver

Re: [Caml-list] Annoying behaviour of OCaml

[David Thomas]

--- Oliver Bandel <oliver@first.in-berlin.de> wrote:
> Even if this would be the case, not what we expect
> is of importance, but what the documentation says.
> If there's a difference between documentation and
> bahaviour, then there is a bug (in the
documentation,
> or in the implementation, or both).

I disagree that expectations are of no importance. 
Principle of least surprise and all that...  Violation
of expectations is a bug not in documentation or
implementation, but design.  That said, there may very
well be overriding concerns that force us to introduce
behavior contrary to expectations in certain instances
- it's one guideline of many.


      ____________________________________________________________________________________
Looking for last minute shopping deals?  
Find them fast with Yahoo! Search.  http://tools.search.yahoo.com/newsearch/category.php?category=shopping

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von David Thomas <david_hd@yahoo.com>:

>
> --- Oliver Bandel <oliver@first.in-berlin.de> wrote:
> > Even if this would be the case, not what we expect
> > is of importance, but what the documentation says.
> > If there's a difference between documentation and
> > bahaviour, then there is a bug (in the
> documentation,
> > or in the implementation, or both).
>
> I disagree that expectations are of no importance.
> Principle of least surprise and all that...
[...]

Principle of least surprise is fine.
But it depends on the view of the one
who is surprised or not.

When I start to use Blender for example,
with the principle of least surprise,
I will be very surprised not to have
the typical Windows-GUI (and KDE and such stuff)
when using it.
I could blame the developers for using completely
different ways of GUI-design, writing hate-mails to them,
why they didn't used the menues that every person expects,
when using a GUI-based application, ...
...or I could try to learn how to use and see, that
it's the best GUI (IMHO), that was ever invented.

Or there are expectations to three mouse-buttons and
for a long time the expectation was, that only the
left button has to be used; since a while the right one
also became popular, and later then the middle button.

But some years ago I wanted to provide a GUI as frontend to
sendfile; I used left button for "add file", right
for "remove file" (or other way around, don't know).
The sendmail developer than said, this is against
the expectations, so he would not encourage it.

To go that way every time IMHO is nonsesne...
...expectations can (and WILL) be changed by the
programs that people use. Habituating to them
means changing the expectations.

Expectations are based on habits.
And habits can change (even if sometimes slowly).



OK, this is not OCaml-discussion, but you started an abstract
discussion, so I can use the arguments on other software too.


> Violation
> of expectations is a bug not in documentation or
> implementation, but design.  That said, there may very
> well be overriding concerns that force us to introduce
> behavior contrary to expectations in certain instances
> - it's one guideline of many.

So, OK, then these "overridings" are at work here. ;-)

When one knows them, this is OK, IMHO.
The perfect world can possibly be found at http://www.haskell.org/

I'm now very habituated to OCaml. And it's "imperfection"
(compared to Haskell) is a plus for me, because I like the
multi-paradigm way.

I also have moaned about non-functional strings
years ago (when starting with OCaml), but now my expectations have
been ocamlized ;-) and today it's ok for me. There are good reasons for
them and I could go to the Haskell-universe if I don't want them.
And I didn't had problems with the imparative strings so far,
so my experiences confirmed the design of OCaml.
This might be different for other people, depending on needs and
expectations ;-) (needs might also be habituated).

And if compare does not fit the needs, one can write special
compare-functions. I'm sure, in OCaml, this can be done with
a hand of lines of Code.

Ciao,
   Oliver

Re: [Caml-list] Annoying behaviour of OCaml

[David Thomas]

--- Oliver Bandel <oliver@first.in-berlin.de> wrote:

> So, OK, then these "overridings" are at work here.
> ;-)

I never meant to imply that they weren't.  I was
simply voicing opposition to the rejection of
expectation as immaterial.


      ____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von David Thomas <david_hd@yahoo.com>:

>
> --- Oliver Bandel <oliver@first.in-berlin.de> wrote:
>
> > So, OK, then these "overridings" are at work here.
> > ;-)
>
> I never meant to imply that they weren't.  I was
> simply voicing opposition to the rejection of
> expectation as immaterial.
[...]

Expectations are immaterial, but nevertheless of influence ;-)


Ciao,
   Oliver

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von David Thomas <david_hd@yahoo.com>:

[...]
> I disagree that expectations are of no importance.
> Principle of least surprise and all that...
[...]


Imagine a purely-imperative programmer,
coming to use FPLs....

...many expectations that will not work then...


Ciao,
   Oliver

Re: [Caml-list] Annoying behaviour of OCaml

[Thomas Fischbacher]

Eric Cooper wrote:

>>compare [|1;2;3|] [|4;5|];; (* ...but actially is not: this gives 1,
>>			       supposedly because the second list is
>>			       shorter than the first.
>>			    *)
> 
> This is indeed unexpected behavior:
>     # compare "123" "45";;
>     - : int = -1
>     # compare [1;2;3] [4;5];;    
>     - : int = -1
>     # compare [|1;2;3|] [|4;5|];;
>     - : int = 1

Ah, yes, many thanks. I mixed up some things in my bugreport - but this
shows the issue fairly well.

-- 
best regards,
Thomas Fischbacher
t.fischbacher@soton.ac.uk

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von Eric Cooper <ecc@cmu.edu>:

> On Thu, Jan 10, 2008 at 02:52:26PM +0000, Thomas Fischbacher wrote:
> > compare [|1;2;3|] [|4;5|];; (* ...but actially is not: this gives
> 1,
> >                                supposedly because the second list is
> >                                shorter than the first.
> >                             *)
>
> This is indeed unexpected behavior:
>     # compare "123" "45";;
>     - : int = -1

This is what I would expect.
It's the way I know.
check each char on equality.
The first comparision gives you, that "1" < "5",
and the comparison is done.



>     # compare [1;2;3] [4;5];;
>     - : int = -1
>     # compare [|1;2;3|] [|4;5|];;
>     - : int = 1

ooops?!

That's a point, where I would look into the the
documentation now ;-) because it's also unexpected for me.
Does comapre use different properties to comapare
arrays and lists?

Lists: compare element by element;
Array: comapre length?!

Ciao,
   Oliver

Re: [Caml-list] Annoying behaviour of OCaml

[Oliver Bandel]

Zitat von Thomas Fischbacher <tf@functionality.de>:
[...]
>
> compare ((17,23),[|8;9;10|]) ((12,21),[|8;9|]);;

17 > 12

This must give back 1.



>
> (* This situation is quite similar to the one where encountered
>     the problem. We tried to use Array.sort in conjunction with
>     "compare" to sort some abstract specifications of contributions
>     to a sparse matrix of the form ((row,column),array_of_factors)
>     by row, assuming that "compare" would do the job through
>     lexicographical order, but actually, it does not. In this case,
>     the result is +1 rather than -1!
> *)
>
> compare ((17,23),[8;9;10]) ((12,21),[8;9]);;

17 > 12

This must give back 1.


>
> Let us see for comparison how other H.M.-typed languages behave:
> Haskell (hugs):
>
> Haskell 98 mode: Restart with command line option -98 to enable
> extensions
>
> Type :? for help
> Hugs.Base> ((17,23),[8,9,10]) < ((12,21),[8,9])
> False
> Hugs.Base>


# compare 1 2;;
- : int = -1

Is -1 to be interpreted as false or as true?

OCaml:

# ((17,23),[8;9;10]) <  ((12,21),[8;9]);;
- : bool = false


So it's the same as in Haskell.
So it should be what you expected.

Ciao,
   Oliver