ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

On Thu, Nov 24, 2005 at 04:08:51PM +0000, Peter Jolly wrote:
> Incidentally, I notice that DynArray lacks most of these functions too,
> including sort.  Would it be worth adding them there, to give all the
> common linear containers equivalent interfaces?

Having a common set of interface functions is definitely a goal to go
for.

It's a bit of a shame that Extlib has fiddled with some of the
standard library interfaces, particularly changing List.sort and
adding its own non-standard exceptions.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

On 11/24/05, Richard W. M. Jones <ri...@me...> wrote:

> > Actually, I agree it makes complete sense for partition.  As I think
> about
> > it, I think filter and find_all should be different.  find_all should
> return
> > a list, and filter should return an array.  And possibly, filter should
> be
> > defined in terms of find_all.
>
> Perhaps you can share your thinking on this :-)
>

Sorry!

I think the principle of least surprise is going to be that
> Array.filter should return an array - this is surely what users would
> expect.


I agree: filter implies you're given a container,  then you "filter" away
some elements, still left with the same type of container.

Find_all suggests you're just looking for all matching elements.  It doesn'=
t
suggest any particular data structure.  So, a list is as good as anything.

The problem will be in the implementation which may require
> two passes -- it could be solved better if there was a truncation
> primitive for arrays.


As I suggested above, one way to implement filter is just:

let filter x y =3D of_list (find_all x y)

There are a number of other implementations, it might make sense to write a
benchmark to decide which is faster.  One worry with a two-pass approach,
though, is it might be incompatible with find/inclusion functions that
contain state (i.e. the state might get confused on the 2nd call).

-Amit

Re: [Ocaml-lib-devel] ExtArray?

[Peter J. <pe...@jo...>]

Richard Jones wrote:
>Amit Dubey wrote:
>> Array.find
>>
>> Will this return the element or an index?
> 
> I'm not sure which is better?  I think probably having Array.find be
> exactly like List.find, ie. returning an element, and having an
> additional Array.find_index to return the index would be the best
> idea.  What do people think?

The principle of least surprise suggests that identically-named
functions should have identical behaviours, so I agree with this.

>> Array.filter
>> Array.find_all
>> Array.partition
>>
>> Would these return lists or arrays?
> 
> I think it's better to return arrays, but what do people think about
> that?

Again, since List.filter returns a list and Enum.filter returns an enum,
it seems logical that Array.filter should return an array.  The other
behaviour can be derived trivially, and hopefully not too inefficiently,
by doing the filtering on an intermediate enum:

 let filter_to_list f a = List.of_enum (Enum.filter f (Array.enum a))

Incidentally, I notice that DynArray lacks most of these functions too,
including sort.  Would it be worth adding them there, to give all the
common linear containers equivalent interfaces?

Re: [Ocaml-lib-devel] ExtArray?

[Richard W. M. J. <ri...@me...>]

On Thu, Nov 24, 2005 at 03:56:20PM +0000, Amit Dubey wrote:
> > Array.filter
> > > Array.find_all
> > > Array.partition
> > >
> > > Would these return lists or arrays?
> >
> > I think it's better to return arrays, but what do people think about
> > that?
> 
> Actually, I agree it makes complete sense for partition.  As I think about
> it, I think filter and find_all should be different.  find_all should return
> a list, and filter should return an array.  And possibly, filter should be
> defined in terms of find_all.

Perhaps you can share your thinking on this :-)

I think the principle of least surprise is going to be that
Array.filter should return an array - this is surely what users would
expect.  The problem will be in the implementation which may require
two passes -- it could be solved better if there was a truncation
primitive for arrays.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtArray?

[William N. <wne...@cs...>]

On Nov 24, 2005, at 8:57 AM, Amit Dubey wrote:

> William writes:

Thanks.  I am apparently still confused by the mysteries of "Reply to  
all".

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Fwd: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

William writes:

---------- Forwarded message ----------
From: William Neumann <wne...@cs...>
Date: Nov 24, 2005 2:58 PM
Subject: Re: [Ocaml-lib-devel] ExtArray?
To: Amit Dubey <ami...@gm...>


On Nov 24, 2005, at 7:16 AM, Amit Dubey wrote:

> Array.find
>
> Will this return the element or an index?

If I were writing it (and I'm sure I have at some point) I'd have
Array.find
return the element, but I'd also have an Array.findi that returned
the element and it's index (and just define Array.find  as snd
(Array.findi ...) ).

> Array.filter
> Array.find_all
> Array.partition
>
> Would these return lists or arrays?

I'd have them return arrays, myself.  Less efficient, perhaps, but
certainly more consistent.  And if I wanted lists back, I'd just use
List.XXX (Array.to_list arr).

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

          --Superstar Billy Graham

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

On 11/24/05, Richard Jones <ri...@an...> wrote:

> > Array.find
> >
> > Will this return the element or an index?
>
> I'm not sure which is better?  I think probably having Array.find be
> exactly like List.find, ie. returning an element, and having an
> additional Array.find_index to return the index would be the best
> idea.  What do people think?


I agree that returning the element is similar to what List does, but arrays
are not lists ;)  I would argue that something like find_index is all that'=
s
necessary, and you can do a lookup if you need the element.

> Array.filter
> > Array.find_all
> > Array.partition
> >
> > Would these return lists or arrays?
>
> I think it's better to return arrays, but what do people think about
> that?


Actually, I agree it makes complete sense for partition.  As I think about
it, I think filter and find_all should be different.  find_all should retur=
n
a list, and filter should return an array.  And possibly, filter should be
defined in terms of find_all.

-Amit

Re: [Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

Well, it seems like people are generally for this proposal, so I have
added a skeletal ExtArray module to CVS.  At present it is simply a
straightforward include of Array.

> Array.for_all
> Array.exists
> Array.mem
> Array.memq
> Array.assoc etc.
> 
> These seem like nice additions.

I'll add these and make them look like the List versions.

> Array.sort
> 
> This already exists.
> 
> Array.find
> 
> Will this return the element or an index?

I'm not sure which is better?  I think probably having Array.find be
exactly like List.find, ie. returning an element, and having an
additional Array.find_index to return the index would be the best
idea.  What do people think?

> Array.filter
> Array.find_all
> Array.partition
> 
> Would these return lists or arrays?

I think it's better to return arrays, but what do people think about
that?

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Ocaml-lib-devel] ExtArray?

[Janne H. <jjh...@gm...>]

Hi,

> Does anyone have any opinions on whether we should have ExtArray,
> analogous to ExtList and ExtString?
>
> Particular functions which are missing from standard Array but which
> would be useful are:
> ...

I would personally find these very useful.

Best regards,
Janne

Re: [Ocaml-lib-devel] ExtArray?

[Amit D. <ami...@gm...>]

Hi,

Array.for_all
Array.exists
Array.mem
Array.memq
Array.assoc etc.

These seem like nice additions.

Array.sort

This already exists.

Array.find

Will this return the element or an index?

Array.filter
Array.find_all
Array.partition

Would these return lists or arrays?

-Amit



On 11/24/05, Richard Jones <ri...@an...> wrote:
>
>
> Does anyone have any opinions on whether we should have ExtArray,
> analogous to ExtList and ExtString?
>
> Particular functions which are missing from standard Array but which
> would be useful are:
>
> Now you can argue that I'm using the wrong data structure and I should
> be using a list, but I have my reasons for using an array and having
> to convert it to a list just to do a quick "for_all" seems a bit
> silly.
>
> Rich.
>
> --
> Richard Jones, CTO Merjis Ltd.
> Merjis - web marketing and technology - http://merjis.com
> Team Notepad - intranets and extranets for business -
> http://team-notepad.com
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=3D7637&alloc_id=3D16865&op=3Dclick
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

Re: [Ocaml-lib-devel] ExtArray?

[Peter J. <pe...@jo...>]

Richard Jones wrote:
> Does anyone have any opinions on whether we should have ExtArray,
> analogous to ExtList and ExtString?

As an ExtLib user I would find such a module very convenient.

While I generally use DynArray when I have the liberty to choose my own
data structure, existing libraries - including parts of the OCaml
standard library - force the use of the built-in arrays in many cases.
I'm sure I can't be the only person who's got quick-and-dirty
implementations of Array.mem, Array.filter, Array.find, and Array.enum
embedded in various projects.

[Ocaml-lib-devel] ExtArray?

[Richard J. <ri...@an...>]

Does anyone have any opinions on whether we should have ExtArray,
analogous to ExtList and ExtString?

Particular functions which are missing from standard Array but which
would be useful are:

Array.for_all
Array.exists
Array.mem
Array.memq
Array.find
Array.filter
Array.find_all
Array.partition
Array.assoc etc.
Array.sort

Now you can argue that I'm using the wrong data structure and I should
be using a list, but I have my reasons for using an array and having
to convert it to a list just to do a quick "for_all" seems a bit
silly.

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

[Ocaml-lib-devel] Re: ExtString.String.slice bug

[Bardur A. <sp...@sc...>]

Bardur Arantsson wrote:
> Brian Brunswick wrote:
> 
>> Hi, thanks for extlib!
>>
>> ExtString.String.slice doesn't live up to its documentation of never
>> raising an exception. It fails to check if ~last is out of range, and
>> crashes in String.sub.
>>
>> Is it best to report bugs here, or in the tracker?
>>
>> -- 
> 
> 
> I notice there's been no commit to the CVS with a fix for this even 
> though the bug was reported quite a long time ago, so I'm going to 
> commit this cleaned up and corrected version later today/tomorrow if 
> there are no objections:
> 
>     let clip _min _max x =
>       max _min (min _max x)
>     ;;
> 
>     let slice ?(first=0) ?(last=Sys.max_string_length) s =
>       let i =
>         clip 0 (length s)
>           (if (first<0) then
>              (length s) + first
>            else
>              first)
>       and j =
>         clip 0 (length s)
>           (if (last<0) then
>              (length s) + last
>            else
>              last)
>       in
>         if i>=j || i=length s then
>           create 0
>         else
>           sub s i (j-i)
> 
> 
> Btw, John Skaller is correct in that the behavior was intended to be 
> exactly like Python's slice operator.
> 

I've committed the above version; with slightly less "spacy" syntax.

-- 
Bardur Arantsson
<bar...@TH...>
<bar...@TH...>

- Me? The 13th Duke of Wimbourne? In a student nurse's hall of
residence at three in the morning? With my reputation? ... Bingo!
                       The 13th Duke of Wimbourne, 'The Fast Show'

[Ocaml-lib-devel] Re: ExtString.String.slice bug

[Bardur A. <sp...@sc...>]

Brian Brunswick wrote:
> Hi, thanks for extlib!
> 
> ExtString.String.slice doesn't live up to its documentation of never
> raising an exception. It fails to check if ~last is out of range, and
> crashes in String.sub.
> 
> Is it best to report bugs here, or in the tracker?
> 
> --

I notice there's been no commit to the CVS with a fix for this even 
though the bug was reported quite a long time ago, so I'm going to 
commit this cleaned up and corrected version later today/tomorrow if 
there are no objections:

     let clip _min _max x =
       max _min (min _max x)
     ;;

     let slice ?(first=0) ?(last=Sys.max_string_length) s =
       let i =
         clip 0 (length s)
           (if (first<0) then
              (length s) + first
            else
              first)
       and j =
         clip 0 (length s)
           (if (last<0) then
              (length s) + last
            else
              last)
       in
         if i>=j || i=length s then
           create 0
         else
           sub s i (j-i)


Btw, John Skaller is correct in that the behavior was intended to be 
exactly like Python's slice operator.

-- 
Bardur Arantsson
<ba...@im...>
<ba...@sc...>

- And the best part? I didn't learn a thing.

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Brian H. <bh...@sp...>]

On Tue, 25 Oct 2005, Brian Brunswick wrote:

> I'll continue inflicting my opinion on the list:-)

Ditto :-)

>
> I would say no, it shouldn't wrap again. I think its useful behaviour
> to have endpoints that silently truncate, and not useful to have ones
> that wrap around.

Wrapping also brings up the possibility of the substring operation 
returning a string that is *longer* than the original string.  Consider 
the case where I ask for the substring going from index -2 to 
(String.length s) - 1 inclusive.  How long of a string should this return? 
One possible returns a string of length 2 (containing characters -2 and -1 
inclusive), and another says it should return a string of length 
(String.length s) + 2, with characters -2 and -1 duplicated twice, once at 
the begining of the string and once at the end.  Now, what happens when I 
ask for the string going from -(String.length s) - 2 to 2*(String.length 
s)?  And so on.


Brian

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[skaller <sk...@us...>]

On Tue, 2005-10-25 at 13:07 +0100, Amit Dubey wrote:
> On 10/25/05, Brian Brunswick <bri...@gm...> wrote:
>         On 25/10/05, Amit Dubey <ami...@gm...> wrote:
>         > I see the problem.  I think there may be another problem if
>         first < -(length
>         > s).  Is it best to fix these bugs, or change the
>         documentation? 
>         >
>         
>         My opinion would be fix the problem, since we already have
>         String.sub
>         to throw exceptions.
> 
> 
> OK, but this raises two questions:
> (1) what would be the behaviour when (length s) <= i  < 2 * (length
> s).  Similar to when 0 > i > -1 * (length s) (i.e. substact length s)?
> (2) what about when i < -2 * (length s) or i >= 2 * (length s)?
> (Where i = first/last)
> 

What Python does. See the Python reference manual.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Brian B. <bri...@gm...>]

On 25/10/05, Amit Dubey <ami...@gm...> wrote:
> On 10/25/05, Brian Brunswick <bri...@gm...> wrote:
> > On 25/10/05, Amit Dubey <ami...@gm...> wrote:
> > > I see the problem.  I think there may be another problem if first <
> -(length
> > > s).  Is it best to fix these bugs, or change the documentation?
> > >
> >
> > My opinion would be fix the problem, since we already have String.sub
> > to throw exceptions.
>
>
>  OK, but this raises two questions:
>  (1) what would be the behaviour when (length s) <=3D i  < 2 * (length s)=
.
> Similar to when 0 > i > -1 * (length s) (i.e. substact length s)?
>  (2) what about when i < -2 * (length s) or i >=3D 2 * (length s)?
>  (Where i =3D first/last)
>
>

I'll continue inflicting my opinion on the list:-)

I would say no, it shouldn't wrap again. I think its useful behaviour
to have endpoints that silently truncate, and not useful to have ones
that wrap around.

The wrapping at zero is useful because it gives a reference relative
to the end of the string,
and not because it wraps. I'll wager that people practically never
have code that generates
some positive and some negative offsets by arithmetic for the same argument=
.

So we do: let i =3D if i>=3D0 then min i len else max 0 (len - i)
for both first and last, and then if last<first "" else ....

>  What about meeting halfway and adding a function like truncate pair:
>
>  let truncate_pair xl yl =3D
>    let rec aux accu_x accu_y xl yl =3D match xl,yl with
>    | x::xs, y::ys -> aux (x::accu_x) (y::accu_y) xs ys
>    | _, _ -> (rev accu_x, rev accu_y)
>    in
>      aux [] [] xl yl
>
>  -Amit
>

Yes, we want that as well. I'd still be tempted to add most of the
Haskell list ones too, simply on the basis that people might be
familiar with them.

--
Bri...@it...____Wit____Disclaimer____!Shortsig_rules!

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Brian B. <bri...@gm...>]

On 25/10/05, Brian Brunswick <bri...@gm...> wrote:
> So we do: let i =3D if i>=3D0 then min i len else max 0 (len - i)
> for both first and last, and then if last<first "" else ....

Spot the deliberate mistake :-) above....

--
Bri...@it...____Wit____Disclaimer____!Shortsig_rules!

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Amit D. <ami...@gm...>]

On 10/25/05, Brian Brunswick <bri...@gm...> wrote:
>
> On 25/10/05, Amit Dubey <ami...@gm...> wrote:
> > I see the problem. I think there may be another problem if first <
> -(length
> > s). Is it best to fix these bugs, or change the documentation?
> >
>
> My opinion would be fix the problem, since we already have String.sub
> to throw exceptions.



OK, but this raises two questions:
(1) what would be the behaviour when (length s) <=3D i < 2 * (length s).
Similar to when 0 > i > -1 * (length s) (i.e. substact length s)?
(2) what about when i < -2 * (length s) or i >=3D 2 * (length s)?
(Where i =3D first/last)


Eg on the project I used String.slice in, I wanted a version of
> List.combine, but with the spec of Haskell zip, ie just discarding
> extra length. It might be reasonable to add that family too.


What about meeting halfway and adding a function like truncate pair:

let truncate_pair xl yl =3D
let rec aux accu_x accu_y xl yl =3D match xl,yl with
| x::xs, y::ys -> aux (x::accu_x) (y::accu_y) xs ys
| _, _ -> (rev accu_x, rev accu_y)
in
aux [] [] xl yl

-Amit

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Brian B. <bri...@gm...>]

On 25/10/05, Amit Dubey <ami...@gm...> wrote:
> I see the problem.  I think there may be another problem if first < -(len=
gth
> s).  Is it best to fix these bugs, or change the documentation?
>

My opinion would be fix the problem, since we already have String.sub
to throw exceptions.

Generally, I reckon its nice to have both exception and non-exception
versions of things.

Eg on the project I used String.slice in, I wanted a version of
List.combine, but with the spec of Haskell zip, ie just discarding
extra length. It might be reasonable to add that family too.

--
Bri...@it...____Wit____Disclaimer____!Shortsig_rules!

Re: [Ocaml-lib-devel] ExtString.String.slice bug

[Amit D. <ami...@gm...>]

I see the problem. I think there may be another problem if first < -(length
s). Is it best to fix these bugs, or change the documentation?

-Amit

On 10/25/05, Brian Brunswick <bri...@gm...> wrote:
>
> Hi, thanks for extlib!
>
> ExtString.String.slice doesn't live up to its documentation of never
> raising an exception. It fails to check if ~last is out of range, and
> crashes in String.sub.
>
> Is it best to report bugs here, or in the tracker?
>
> --
> Bri...@it...
> ____Wit____Disclaimer____!Shortsig_rules!
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by the JBoss Inc.
> Get Certified Today * Register for a JBoss Training Course
> Free Certification Exam for All Training Attendees Through End of 2005
> Visit http://www.jboss.com/services/certification for more information
> _______________________________________________
> ocaml-lib-devel mailing list
> oca...@li...
> https://lists.sourceforge.net/lists/listinfo/ocaml-lib-devel
>

[Ocaml-lib-devel] ExtString.String.slice bug

[Brian B. <bri...@gm...>]

Hi, thanks for extlib!

ExtString.String.slice doesn't live up to its documentation of never
raising an exception. It fails to check if ~last is out of range, and
crashes in String.sub.

Is it best to report bugs here, or in the tracker?

--
Bri...@it...____Wit____Disclaimer____!Shortsig_rules!

Re: [Ocaml-lib-devel] Extlib.list.unique

[Amit D. <ami...@gm...>]

On 10/22/05, sejourne_kevin <sej...@ya...> wrote:

> When ordering isn't need I use this one :


I think you misunderstood me: I'm talking about cases where you can't do th=
e
*first* sort, not the second. Although Pervasives.compare defines a total
order over the *physical* representation of a datastructure, in some cases =
(
e.g. if you're writing a math application), there may be instances when you
don't want an ordering over the *semantic* representation of the elements
elements: you only want equality. In these cases, you'd be better off with
the O(n^2) version.

But then maybe I'm being anal... (but then as Brian pointed out, if you hav=
e
a meaningful ordering over elements, why not just use a set?)

-Amit

Re: [Ocaml-lib-devel] Extlib.list.unique

[Brian H. <bh...@sp...>]

On Fri, 21 Oct 2005, sejourne_kevin wrote:

> Hello evrybody.
>
> Thanks for that lib I use evryday.
>
> But, I notice that ExtList.unique is in O(n^2) this is a problem for me,
> I often use list over 100000 elements(and some time over million).
> So I wrote a replacement function that is faster O(n+n*log(n)).
> It use about 5X the space of the parameter list. On my computer (512 Mo)
> the limit before the stak overflow is just over a million.

I think this is actually a sign that you don't want to be using lists at 
all, but sets and/or maps.

Brian

Re: [Ocaml-lib-devel] Extlib.list.unique

[sejourne_kevin <sej...@ya...>]

Amit Dubey a écrit :
> In principle, I like the idea. I don't know if I like the implementation,
> though. It seems a bit too complex, and the variable names are difficult to
> decipher (e.g. "ac" means "accu/accumulator", but it isn't clear what tcn
> means; if you want to use short names, might as well use "x", "y", etc.)
> Maybe this is going too far, but could you overload the O(n^2)
> implementation with the faster one, for cases where you don't have an
> ordering over elements? i.e. something like this:
When ordering isn't need I use this one :
let delete_double ?(cmp=Pervasives.compare) l =
  let rec delete accu = function
      [] -> accu
    | [x] -> x :: accu
    | x::y::reste->
	delete (if (cmp x y) == 0 then accu else x::accu) (y::reste)
  in delete [] (List.sort cmp l)
;;
Witch


William Neumann proposed another implementation (with ordering)
without the problem of the array:


let uniq ?(last=false) ?(cmp=Pervasives.compare) l =
  let map = if last then List.rev_map else (fun f l -> List.rev
(List.rev_map f l)) in
  let cnt = let c = ref 0 in fun () -> incr c; !c in
  let rec drop_extras acc = function
    | h1::h2::t ->
        if fst h1 = fst h2
	then drop_extras acc (h1::t)
        else drop_extras (h1::acc) (h2::t)
    | [h] -> h::acc
    | [] -> acc
  in
    List.rev_map fst
      (* Reverse the list created by mapping fst over... *)
      (List.sort (fun (_,a) (_,b) -> b - a)
	 (* The list of pairs made by sorting in descending order by  the
second (int) element... *)
	 (drop_extras
            (* The list created by dropping all the duplicates from... *)
            []
            (* The list made by (stable) sorting by the first element... *)
            (List.sort (fun (a,_) (b,_) -> cmp a b)
               (* The list made by pairing each element with its
position  in the original list
		  (and possibly reversing the result if last = true) *)
               (map (fun x -> x,cnt ()) l))))
;;


I also have the same version of the function I post but without list :

let delete_double_unsort_list ?(last=false) ?(cmp=Pervasives.compare) l =
  let rec add_num ac n = function
      [] -> List.rev ac | h :: t -> add_num ((h,n)::ac) (succ n) t
  in
  let compare x y = cmp (fst x) (fst y) in
  let nl = add_num [] 0 l in
  let snl = List.sort compare nl in
  let rec get_dbl ac = function
      [] | [_] -> ac
    | (h1,nh1) :: (((h2,nh2) :: _) as l) ->
	if (cmp h1 h2) == 0
	then get_dbl ((if last then nh1 else nh2)::ac) l
	else get_dbl ac l
  in
  let dbl = get_dbl [] snl in
  let sdbl = List.stable_sort Pervasives.compare dbl in

  let rec delete ac a b = match a , b with
      _ , [] -> List.rev ((List.rev_map fst a) @ ac)
    | (_,na)::ta,nb::tb when na == nb -> delete ac ta tb
    | (e,_)::ta,gb -> delete (e::ac) ta gb
    | [],_ -> assert false
  in  delete [] nl sdbl
;;



It seems that William Neumann's version is the fastest on G4 / G5. On
the computers which I have at my arrangement (p4 1.6GZ) and (Barton 2500
+) I observed that it is my version the fastest.
As proposed by William I will write a "array version" with all functions
tails recursives that switch on list when max_array_size is reached.



	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com