[Caml-list] Lexicographic sort

[Caml-list] Lexicographic sort

[Francois Pottier]

Hi,

I just found a nice way of writing lexicographic sort in O'Caml
using Luc Maranget's recent extension of pattern syntax, which
allows a single identifier to be bound in several alternatives.

For instance, here is code that sorts integer triples:

  let compare (major1, middle1, minor1) (major2, middle2, minor2) =
    match major1 - major2, middle1 - middle2, minor1 - minor2 with
    | 0, 0, d
    | 0, d, _
    | d, _, _ ->
	d

Quite beautiful. Perhaps this is obvious to many, but I thought
I'd post it.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: Lexicographic sort

[Francois Pottier]

On Thu, Jan 30, 2003 at 11:00:49AM +0100, Francois Pottier wrote:
> 
> For instance, here is code that sorts integer triples:
> 
>   let compare (major1, middle1, minor1) (major2, middle2, minor2) =
>     match major1 - major2, middle1 - middle2, minor1 - minor2 with
>     | 0, 0, d
>     | 0, d, _
>     | d, _, _ ->
> 	d

Of course, I should have said: here is code that *compares*
integer triples.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lexicographic sort

[Laurent Vibert]

On Thu, 30 Jan 2003, Francois Pottier wrote:

> 
> Hi,
> 
> I just found a nice way of writing lexicographic sort in O'Caml
> using Luc Maranget's recent extension of pattern syntax, which
> allows a single identifier to be bound in several alternatives.
> 
> For instance, here is code that sorts integer triples:
> 
>   let compare (major1, middle1, minor1) (major2, middle2, minor2) =
>     match major1 - major2, middle1 - middle2, minor1 - minor2 with
>     | 0, 0, d
>     | 0, d, _
>     | d, _, _ ->
> 	d
> 
> Quite beautiful. Perhaps this is obvious to many, but I thought
> I'd post it.
> 

Warning, from the Caml manual,
http://pauillac.inria.fr/ocaml/htmlman/manual014.html
``Or'' patterns :
If both matchings succeed, it is undefined which set of bindings is 
selected

eg. if (0,0,d) and (d,_,_) succeed, you don't hnow the result...
yes in this case, it works, but in some other, it doesn't :
let f = function (_::l) | l -> l
in f [1;2] 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Lexicographic sort

[Luc Maranget]

> 
> On Thu, 30 Jan 2003, Francois Pottier wrote:
> 
> > 
> > Hi,
> > 
> > I just found a nice way of writing lexicographic sort in O'Caml
> > using Luc Maranget's recent extension of pattern syntax, which
> > allows a single identifier to be bound in several alternatives.
> > 
> > For instance, here is code that sorts integer triples:
> > 
> >   let compare (major1, middle1, minor1) (major2, middle2, minor2) =
> >     match major1 - major2, middle1 - middle2, minor1 - minor2 with
> >     | 0, 0, d
> >     | 0, d, _
> >     | d, _, _ ->
> > 	d
> > 
> > Quite beautiful. Perhaps this is obvious to many, but I thought
> > I'd post it.
> > 
> 
> Warning, from the Caml manual,
> http://pauillac.inria.fr/ocaml/htmlman/manual014.html
> ``Or'' patterns :
> If both matchings succeed, it is undefined which set of bindings is 
> selected
> 
> eg. if (0,0,d) and (d,_,_) succeed, you don't hnow the result...
> yes in this case, it works, but in some other, it doesn't :
> let f = function (_::l) | l -> l
> in f [1;2] 
> 


Well, Francois's example is a good incentive to suppress this
undefined matching order.

In fact, matching is left-to-right, except when one of the
alternatives is a variable (or an underscore).  I have a loose agenda
to enforce left-to-right matching order, and Francois's code won't be
broken by future versions.


Again this undefined matching order in or-patterns is a mistake of mine
and it should be corrected.


--Luc



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners