ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] Advancements

[Nicolas C. <war...@fr...>]

Hi,

I'm quite disapointed about the current silence on this list... After a
short period of time where everyone really wanted to contribute, there seems
to be no more will to do so (excepted Brian modules post), but perhaps most
of people there only wanted to give advices about how to name such module
and not really develop and implement the ExtLib :))
For people who are still interested, I'll keep on gathering modules, and
since we have a 3-days WeekEnd here in Japan starting tomorrow, I'll try to
come on monday with a first ExtLib version implementing all suggestions
being made, so we can put it on some CVS.

Nicolas Cannasse

Re: [Ocaml-lib-devel] New Library 1: XList

[Brian H. <bri...@ql...>]

On Sat, 15 Mar 2003, Nicolas Cannasse wrote:

> > OK, The first of three libraries I'm submitting for comments:  XList.
> >
> > XList is a reimplementation of the Ocaml standard List library, except all
> > non-tail recursion has been removed, and instead I use Olivier Andrieu's
> > setcdr function.  This should be as fast as recursion for short lists, but
> > work correctly (shouldn't blow stack) for long lists.
> 
> Ok, thanks alot, few remarks :
> - the setcdr should of course be hidden in the ExtList.mli

Heck yeah! :-)

> - I switched you "length" implementation to the INRIA one ( using a non
> local "aux" function, since they must have had a good reason - performances
> perhaps -  to do so ) -- in general, I did make all local auxiliary
> functions being "global", if anyone could test the speed and tell if it is
> better this way...

Hmm.  If I had to guess, I'd guess that making them global slows things 
down, if it changes anything at all.  By making them internal, I'm 
encouraging the compiler to inline them.  And limiting their namespace.  I 
don't want to think about how many internal 'loop' functions I wrote :-).

> - replaced "failwith" & "invalid_argument" calls by corresponding ExtLib
> exceptions raise ( btw, I switched the name of the exception from
> No_such_element - quite obscure - to Empty_list : fully descriptive )

The code that does this is usually where I'm emulating the standard 
library.

> - about the programming style, removed all the ";;" (useless) and the
> indentation after a match .. with ( and added missings | for
> first-case-matching : this make the code more readable )

I'm not 100% sure of this, but don't care enough to argue.

> - used the let ... = function when it was possible

I'm still getting comfortable with the let ... = function format.  :-).  
In poking around in the produce assembly language, I can't see that it 
makes a difference.

> - while talking about performance, could someone do some test program for it
> ? I would like to test for example the improvement of inlining the setcdr
> calls in duplicate, append, etc.

Performance I'm less concerned with.  Having a test suite would be nice.  
Up until now, I've mainly been cutting&pasting into top-level ocaml, and 
throwing random data at it.  A more standard testing program would be 
nice.

> - for the fold tail recursive calls, I propose the naming of  tail_fold_left
> / right for tail recursives one ( since most of the time, you don't really
> need tail recursives calls )

Correctness counts for more with me than performance.  The thing I like 
about tail recursion is that it works no matter how huge the lists are.  
Failing on long lists is most likely to happen in production, in hard to 
replicate cases.  So I'd rather make the tail recursive versions default- 
and provide non-tail-recursive versions if needed.

The experimenting I did with setcdr and append indicated that setcdr was 
as fast, and maybe even faster, than the non-tail-recursive versions, 
while list reversing was about 30% slower.  So if I could replace a 
non-tail-recursive version with a setcdr version, I didn't see a need to 
supply an old form.

> - corrected a bug since fold_right' was recursively calling... fold_right :)
> - same : memq calling mem  , assq calling assoc , mem_assq calling mem_assoc
> ( too fast copy-past, Brian :=)

Typos R' us.

> - removed useless  begin...end blocks, corrected indentation at some points,
> remove useless parenthesis in multi pattern matching ( should cause the
> allocation of tuples - but I don't really know since the ocaml stdlib is
> using this style sometimes )

Commas cause tuples, parens only affect grouping.  In ocaml:
# 1,2;;
- : int * int = (1, 2)
# (1,2);;
- : int * int = (1, 2)

On grouping, by which I mean both parens and begin/end: I've been bitten 
once too often by incorrect associations.  One of my favorite obfuscated C 
tricks is:

#define TRUE (1 & 3 == 1)
#define FALSE (!TRUE)

If there's one bitch I have with Ocaml, it's all the shift/reduce
conflicts, which show up in the language as uncertain associations.  So I 
liberally add parens and begin/end blocks.  Because it doesn't slow 
anything down, and makes it easier to modify the code later.

> - added the "exception Different_list_size of string" ( to replace
> invalid_argument in iter2, map2, etc... )

This changes behavior of the standard library.  Which is "correct" is a 
different argument- this is no longer a silent change.

> - about your sort function, I would like to see what are the speed
> differences on sorting ~1000 items lists and ~1M items lists ( compared to
> the List.sort of the ocaml stdlib ) + switched the "cmp" argument to
> optional - default = compare ( consistent with the current ExtList )

Haven't done any timings here.

> - will somehow generate the mli and write the documentation ? I dislike the
> mathematical explainations of the ocaml stdlib documentation, I think a
> short description, with perhaps one sample for each function would be better
> for beginners, and then the specification can come ( order preserved,
> complexity, tail-rec, etc. )

I'll take a swing at these.

Brian

Re: [Ocaml-lib-devel] Third Library: Bitset

[Brian H. <bri...@ql...>]

This library is undergoing some severe redesign.  Once I stopped looking 
at it as a 'set of small integers' and started looking at it as an 'array 
of bits', the requirements of the library shifted in my mind.  For 
example, it should be possible to use the Bitvector library to implement 
elliptic curve cryptography (maybe not in the most efficient manner, but 
still).  So routines like sub (returning a subsection of the array) and 
rotates and shifts also need to be added.  Also, to implement EC crypto, 
you need a precise bitlength- no more rounding up to the next whole int.

I was hopping to have something to distribute today, but it didn't happen.

On Sun, 16 Mar 2003, Nicolas Cannasse wrote:

> - the functions and types are all started with  bitset_ ( C like notation,
> without namespace )
>    instead of doing :
>             open BitSet;;
>             let b = bitset_empty 10 in
>             bitset_add b 1;
>     it's better to use the module system :
>             let b = BitSet.empty 10 in
>             BitSet.add b 1;
>     this is more like 'ocaml style'

OK.  Your first example is why I named things the way I did (well, that 
and old, bad, C habits).

> - the functions add_list and remove_list are useless, since :
>             bitset_add_list b l  == List.iter (bitset_add b) l
>             ( perhaps it's convenient for you to have it available, but we
> can't add a  "_list version of all functions for all the modules we're
> writting :)

Point.  There isn't even a performance advantage :-)


> - about the design itself, it looks good, but perhaps it would be good to
> create an empty bitset with a default size (that's what you're doing), and
> then having it growing automaticly when needed ( right now you're relying on
> array bounds check, you need to do checks by hand - if the user turn them
> off - and raise a BitSet specific exception )

I'm actually moving in the other direction, towards have specific bit 
sizes.  Bitarray might be a better name.  The reason for having specific 
sizes (in bits) is to have defined behavior on shifts.  Does doing a shift 
left expand the bit array?

I'll add an expand function, tho.

> - I don't agree with your compare and equals implementations, since I would
> say the bitsets [0] and [0 ; 0; 0 ] are equals !

Comparing bit arrays with different lengths is a tricky thing to define.

> - wouldn't it better to replace bitset_first_member + bitset_next_member +
> bitset_to_list by two functions BitSet.map and BitSet.iter that are more in
> the functionnal way of doing things ?

Probably.  Consider it done.

> - a new function toggle for bit toogle ( 0 -> 1  || 1 -> 0 )

Already done.  Although I'm calling it negate.  So the three fundemental 
opertations are set, clear, and negate.  I'm going to drop the lists, but 
add set/clear/negate range functions (because these can be signifigantly 
speed up over calling the fundamental functions).

I'll get a new .mli together and (hopefully) post it tomorrow.

Brian

Re: [Ocaml-lib-devel] New Library 1: XList

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

On Mon, 17 Mar 2003, fva wrote:

>  Rather than using ExtList which gives the impression of an extension of 
> the signature (maybe there is, I haven't looked into the code, really) 

The only extension to the list signature I made was that I added a
fold_right'.  The only way I could think of to implement fold_right in a
tail-recursive manner was to first reverse the list, and then traverse it.  
My experiments with append show that reversing the list is about 30%
slower than simply doing a non-tail recursion.  So I provided two
functions- fold_right which reverse the list (works correctly for all
lists, slower), and fold_right' which does non-tail-recursion (faster,
doesn't work for all lists).

Brian

Re: [Ocaml-lib-devel] New Library 1: XList

[Nicolas C. <war...@fr...>]

> OK so my proposition is:
> - Extensions to modules implying an implicit extension on signatures get 
> prefixed, like ExtList
> - reimplementations/laternate versions get postfixed like List2 or 
> List++ or whatever...

I hope my proposal about module hierarchy is fulfilling theses goals.

Nicolas Cannasse

Re: [Ocaml-lib-devel] New Library 1: XList

[fva <fv...@ts...>]

Hi List (XList, ExtList, List+, I'm beginning to confuse my lists!!)


Brian Hurt wrote:

>On Thu, 13 Mar 2003, Blair Zajac wrote:
>
>  
>
>>Brian Hurt wrote:
>>    
>>
>>>OK, The first of three libraries I'm submitting for comments:  XList.
>>>      
>>>
>>Not another single letter abbreviation :)
>>    
>>
>
>In the 20 milliseconds I spend thinking of a name, that's what I cam up 
>with.  :-) I'm not married to it. 
>
>  
>
>>Maybe we should come up with a standard abbreviation for modules that
>>supersede or reimplement Ocaml standard libraries.
>>
>>Maybe Ext as was mentioned for ExtLib???
>>    
>>
>
>Works for me.  ExtList.
>
>  
>
>>The only thing is that Ext could mean any of
>>
>>External (not ok)
>>    
>>
>
>But not bad.  Or at least, not screamingly incorrect.
>
>Brian
>  
>
IMHO this is a case we had not yet encountered: not an extension of a 
module, but a reimplementation of (hopefully) the same signature 
implicitely defined by List.

 Rather than using ExtList which gives the impression of an extension of 
the signature (maybe there is, I haven't looked into the code, really) 
we could *postfix* a number (like "List2" for "2nd implementation of 
List") or List+ as suggested... Only I don't think the Ocaml team would 
care for such a comparison... Hey, what about ListAlt (we're getting 
into murkiers waters here, I know ;) )?

OK so my proposition is:
- Extensions to modules implying an implicit extension on signatures get 
prefixed, like ExtList
- reimplementations/laternate versions get postfixed like List2 or 
List++ or whatever...

(I think this makes sense as well from a linguistic point of view... but 
I'll defer to native speakers here).

Regards,

       Fran Valverde

[Ocaml-lib-devel] Module Structure

[Nicolas C. <war...@fr...>]

Hi list,

I have been thinking for some time on the module structure for ExtLib
issues, and I think I found a quite reasonable comprise.
Ok, first of all, we we talk there only about modules which are extending
the StdLib ones, other "new" modules doesn't cause any problems.
But for the Stdlib one - let's take the example of ExtList - there is some
problems :

- some people would like to use ExtList as a replacement of List

For this first category of people, we can do the following :

-- file extList.mli ---
module List : sig ... end
--- eof ---

Like this theses people will only have to add an extra "open ExtList" in the
beginning of their files and then they can use the List standard functions
as well as the List extended ones within the same short and readable
namespace : List.

But !
- this we're modifying the specification of some functions, people with
existing running code would like to use only ExtList as an additionnal
library of functions, without overriding the current Stdlib ones.

Here's the answer :
--- file extLib.mli ---
module ExtList = ExtList.List
--- eof ---

So they only have to do an "open ExtLib" and then they can use extended
functions under the ExtList namespace.

Nicolas Cannasse

Re: [Ocaml-lib-devel] New Library 1: XList

[Doug B. <dou...@ba...>]

"Nicolas Cannasse" <war...@fr...> writes:
> Thanks Doug, do you volunteer for further timing contests ? :-)

Unfortunately, no. I might try to help on occasion, if that is even
possible, but I am sorry to say I would be an unreliable collaborator
at this point, due to other commitments of my time.

Bonne Chance,
Doug
-- 
http://www.bagley.org/~doug/contact.shtml

Re: [Ocaml-lib-devel] New Library 1: XList

[Nicolas C. <war...@fr...>]

> > - while talking about performance, could someone do some test program
for it
> > ? I would like to test for example the improvement of inlining the
setcdr
>
> I have a "beta" implementation of something like the Perl Benchmark
> module:
>
>  http://www.bagley.org/~doug/ocaml/benchmark/
>
> It can help to answer such questions as: "is it faster to do it this
> way or that way?"
>
> I've attached an example below, which indicates, as one might expect,
> that inlining helps with byte code, but not so much with optimized
> code.

Thanks Doug, do you volunteer for further timing contests ? :-)

Thanks that's what I wanted to hear. I think then we should inline such
calls ( I myself like the bytecode, and you can't always easily switch to
native when you're using some features like Dynlink ). Definition proposal
for inlined calls : we should inline calls that does not require more than 1
or 2 easy lines of code, and are called many times.

BTW, I was also wondering about the local-loop definitions against a
separate-function, but since the loop is only called once, that shouldn't
make even a small difference.

What about the Brian's sort performances ?

Nicolas Cannasse

Re: [Ocaml-lib-devel] New Library 1: XList

[Doug B. <dou...@ba...>]

"Nicolas Cannasse" <war...@fr...> writes:
> - while talking about performance, could someone do some test program for it
> ? I would like to test for example the improvement of inlining the setcdr

I have a "beta" implementation of something like the Perl Benchmark
module:

 http://www.bagley.org/~doug/ocaml/benchmark/

It can help to answer such questions as: "is it faster to do it this
way or that way?"

I've attached an example below, which indicates, as one might expect,
that inlining helps with byte code, but not so much with optimized
code.

The example also has an alternative for your "init" function which
seems a little faster.

Cheers,
Doug
-- 

(* foo.ml ...

COMPILE:
 ocamlc -I +site-lib/benchmark unix.cma benchmark.cma -o foo foo.ml
 ocamlopt -I +site-lib/benchmark unix.cmxa benchmark.cmxa -o foo.opt foo.ml

RESULTS:
> ./foo
Throughputs for init1, init2 ...
     init1: 21 WALL (20.97 usr +  0.02 sys = 20.99 CPU) @ 156.93/s (n=3294)
     init2: 21 WALL (20.91 usr +  0.02 sys = 20.93 CPU) @ 71.91/s (n=1505)

        Rate init2 init1
init2 71.9/s    --  -54%
init1  157/s  118%    --

Throughputs for duplicate/ext, duplicate/inl ...
duplicate/ext: 21 WALL (20.82 usr +  0.02 sys = 20.84 CPU) @ 81.33/s (n=1695)
duplicate/inl: 21 WALL (20.95 usr +  0.01 sys = 20.96 CPU) @ 102.96/s (n=2158)

                Rate duplicate/ext duplicate/inl
duplicate/ext 81.3/s            --          -21%
duplicate/inl  103/s           27%            --

> ./foo.opt
Throughputs for init1, init2 ...
     init1: 22 WALL (20.92 usr +  0.02 sys = 20.94 CPU) @ 299.52/s (n=6272)
     init2: 22 WALL (21.57 usr +  0.01 sys = 21.58 CPU) @ 146.15/s (n=3154)

       Rate init2 init1
init2 146/s    --  -51%
init1 300/s  105%    --

Throughputs for duplicate/ext, duplicate/inl ...
duplicate/ext: 21 WALL (21.17 usr +  0.01 sys = 21.18 CPU) @ 126.25/s (n=2674)
duplicate/inl: 21 WALL (21.16 usr +  0.01 sys = 21.17 CPU) @ 128.72/s (n=2725)

               Rate duplicate/ext duplicate/inl
duplicate/ext 126/s            --           -2%
duplicate/inl 129/s            2%            --

 *)

open Printf
open Benchmark

let setcdr : 'a list -> 'a list -> unit = fun c v -> 
    Obj.set_field (Obj.repr c) 1 (Obj.repr v)


let rec duplicate_aux dst = function
    | [] -> dst
    | h :: t -> 
        let r = [ h ] in
        setcdr dst r;
        duplicate_aux r t


let duplicate = function
    | [] -> assert false
    | h :: t ->
        let r = [ h ] in
        r, (duplicate_aux r t)


let rec duplicate_aux_i dst = function
    | [] -> dst
    | h :: t -> 
        let r = [ h ] in
	Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
        duplicate_aux_i r t


let duplicate_i = function
    | [] -> assert false
    | h :: t ->
        let r = [ h ] in
        r, (duplicate_aux_i r t)



let init1 n f =
   let rec loop seq m =
     if m < 0 then seq else loop ((f m) :: seq) (pred m) in
   loop [] (pred n)


let rec init2 size f =
	let rec loop dst n =
		if n < size then
			let h = [ f n ] in
			setcdr dst h;
			loop h (n+1)
	in
	if size = 0 then [] 
	else if size < 0 then invalid_arg "ExtList.init"
	else
		let h = [ f 0 ] in
		loop h 1;
		h


let _ =
  let test_init1 x = init1 x (fun x -> x)
  and test_init2 x = init2 x (fun x -> x) in

  let res = throughputN 20
	      [("init1", test_init1, 10000);
               ("init2", test_init2, 10000)] in
  print_newline ();
  tabulate res;
  print_newline ();

  let l1 = init1 10000 (fun x -> x) in
  let res = throughputN 20
	      [("duplicate/ext", duplicate, l1);
               ("duplicate/inl", duplicate_i, l1)] in
  print_newline ();
  tabulate res

Re: [Ocaml-lib-devel] New Library 1: XList

[Nicolas C. <war...@fr...>]

> OK, The first of three libraries I'm submitting for comments:  XList.
>
> XList is a reimplementation of the Ocaml standard List library, except all
> non-tail recursion has been removed, and instead I use Olivier Andrieu's
> setcdr function.  This should be as fast as recursion for short lists, but
> work correctly (shouldn't blow stack) for long lists.

Ok, thanks alot, few remarks :
- the setcdr should of course be hidden in the ExtList.mli
- I switched you "length" implementation to the INRIA one ( using a non
local "aux" function, since they must have had a good reason - performances
perhaps -  to do so ) -- in general, I did make all local auxiliary
functions being "global", if anyone could test the speed and tell if it is
better this way...
- replaced "failwith" & "invalid_argument" calls by corresponding ExtLib
exceptions raise ( btw, I switched the name of the exception from
No_such_element - quite obscure - to Empty_list : fully descriptive )
- modified the implementation of "nth" in order to be able to raise
Invalid_index in each error case ( more consistent ), and do only one time
the test n < 0 ( better perfs I think )
- about the programming style, removed all the ";;" (useless) and the
indentation after a match .. with ( and added missings | for
first-case-matching : this make the code more readable )
- the remark for setcdr goes as well with duplicate
- used the let ... = function when it was possible
- while talking about performance, could someone do some test program for it
? I would like to test for example the improvement of inlining the setcdr
calls in duplicate, append, etc.
- for the fold tail recursive calls, I propose the naming of  tail_fold_left
/ right for tail recursives one ( since most of the time, you don't really
need tail recursives calls )
- corrected a bug since fold_right' was recursively calling... fold_right :)
- same : memq calling mem  , assq calling assoc , mem_assq calling mem_assoc
( too fast copy-past, Brian :=)
- removed useless  begin...end blocks, corrected indentation at some points,
remove useless parenthesis in multi pattern matching ( should cause the
allocation of tuples - but I don't really know since the ocaml stdlib is
using this style sometimes )
- added the "exception Different_list_size of string" ( to replace
invalid_argument in iter2, map2, etc... )
- about your sort function, I would like to see what are the speed
differences on sorting ~1000 items lists and ~1M items lists ( compared to
the List.sort of the ocaml stdlib ) + switched the "cmp" argument to
optional - default = compare ( consistent with the current ExtList )
- added the implementation for the following :

 val init : int -> (int -> 'a) -> 'a list
 val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list
 val iteri : (int -> 'a -> 'b) -> 'a list -> unit
 val split_nth : int -> 'a list -> 'a list * 'a list
 val first : 'a list -> 'a
 val last : 'a list -> 'a
 val find_exc : ('a -> bool) -> exn -> 'a list -> 'a (* raise the given exn
instead of Not_found *)

- added signature for some additonnal function proposals

## Joined modified file ##

- will somehow generate the mli and write the documentation ? I dislike the
mathematical explainations of the ocaml stdlib documentation, I think a
short description, with perhaps one sample for each function would be better
for beginners, and then the specification can come ( order preserved,
complexity, tail-rec, etc. )

Nicolas Cannasse

Re: [Ocaml-lib-devel] Third Library: Bitset

[Nicolas C. <war...@fr...>]

> Third and last library being submitted for comment: Bitset.
>
> This library implements sets of small non-negative integers as a bitset.
> The big advantage of this implementation is O(1) adding, removing, or
> testing for membership.

Few remarks :
- (same remarks about the code look as for ExtList )
- the functions and types are all started with  bitset_ ( C like notation,
without namespace )
   instead of doing :
            open BitSet;;
            let b = bitset_empty 10 in
            bitset_add b 1;
    it's better to use the module system :
            let b = BitSet.empty 10 in
            BitSet.add b 1;
    this is more like 'ocaml style'
- the functions add_list and remove_list are useless, since :
            bitset_add_list b l  == List.iter (bitset_add b) l
            ( perhaps it's convenient for you to have it available, but we
can't add a  "_list version of all functions for all the modules we're
writting :)
- about the design itself, it looks good, but perhaps it would be good to
create an empty bitset with a default size (that's what you're doing), and
then having it growing automaticly when needed ( right now you're relying on
array bounds check, you need to do checks by hand - if the user turn them
off - and raise a BitSet specific exception )
- I don't agree with your compare and equals implementations, since I would
say the bitsets [0] and [0 ; 0; 0 ] are equals !
- wouldn't it better to replace bitset_first_member + bitset_next_member +
bitset_to_list by two functions BitSet.map and BitSet.iter that are more in
the functionnal way of doing things ?
- a new function toggle for bit toogle ( 0 -> 1  || 1 -> 0 )

My proposal interface

----bitVector.mli ( V maj for BitVector module )

type t

(** theses two are only needed if you're not resizing the array dynamicaly
**)
exception Invalid_bit_index of int
val size : t -> int

val empty : int -> t
val is_empty : t -> bool
val clone : t -> t
val add : t -> int -> unit (* raise Invalid_bit_index *)
val remove : t -> int -> unit (* raise Invalid_bit_index *)
val toggle : t -> int -> unit (* raise Invalid_bit_index *)
val contains : t -> int -> bool
val compare : t -> t -> int
val equals : t -> t -> bool
val iter : (int -> unit) -> t -> unit
val map : (int -> 'a) -> t -> 'a list

Nicolas Cannasse

Re: [Ocaml-lib-devel] New Library 1: XList

[Nicolas C. <war...@fr...>]

> OK, The first of three libraries I'm submitting for comments:  XList.
[...]


Brian,
I will have a look at your librairies this WeekEnd, don't take my silence
for a bad omen, it's just too much work right now :)

Yours,
Nicolas Cannasse

Re: [Ocaml-lib-devel] Third Library: Bitset

[Brian H. <bri...@ql...>]

On Thu, 13 Mar 2003, Blair Zajac wrote:

> Because this module is O(1), maybe BitVector would be a better name,
> as suggested by another poster on this list when we discussed the
> MutableList?
> 

I don't have a problem with this name either.  Again, I didn't spend much 
time thinking about names.

Brian

Re: [Ocaml-lib-devel] New Library 1: XList

[Brian H. <bri...@ql...>]

On Thu, 13 Mar 2003, Blair Zajac wrote:

> Brian Hurt wrote:
> > 
> > OK, The first of three libraries I'm submitting for comments:  XList.
> 
> Not another single letter abbreviation :)

In the 20 milliseconds I spend thinking of a name, that's what I cam up 
with.  :-) I'm not married to it. 

> 
> Maybe we should come up with a standard abbreviation for modules that
> supersede or reimplement Ocaml standard libraries.
> 
> Maybe Ext as was mentioned for ExtLib???

Works for me.  ExtList.

> 
> The only thing is that Ext could mean any of
> 
> External (not ok)

But not bad.  Or at least, not screamingly incorrect.

Brian

Re: [Ocaml-lib-devel] New Library 1: XList

[Eric C. C. <ec...@cm...>]

On Thu, Mar 13, 2003 at 10:09:07AM -0800, Blair Zajac wrote:
> Maybe we should come up with a standard abbreviation for modules that
> supersede or reimplement Ocaml standard libraries.
> ...
> Maybe Ext as was mentioned for ExtLib???
> ... 
> Anybody else have any ideas here?

ListPlus, StringPlus, etc.?

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

Re: [Ocaml-lib-devel] Third Library: Bitset

[Blair Z. <bl...@or...>]

Brian Hurt wrote:
> 
> Third and last library being submitted for comment: Bitset.
> 
> This library implements sets of small non-negative integers as a bitset.
> The big advantage of this implementation is O(1) adding, removing, or
> testing for membership.

Brian,

Because this module is O(1), maybe BitVector would be a better name,
as suggested by another poster on this list when we discussed the
MutableList?

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/

Re: [Ocaml-lib-devel] New Library 1: XList

[Blair Z. <bl...@or...>]

Brian Hurt wrote:
> 
> OK, The first of three libraries I'm submitting for comments:  XList.

Not another single letter abbreviation :)

Maybe we should come up with a standard abbreviation for modules that
supersede or reimplement Ocaml standard libraries.

Maybe Ext as was mentioned for ExtLib???

The only thing is that Ext could mean any of

Extended (ok)
Extension (ok)
External (not ok)
Extra (not ok)

and many more.

Anybody else have any ideas here?

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/

[Ocaml-lib-devel] New library 2: Psqueue (try #2)

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

Original message bounced because it was too large.

Second of three libraries I am submitting for comments: Psqueue.

This library implements a Priority Search Queue, based up Ralf Hinze's 
paper, see:
http://citeseer.nj.nec.com/hinze01simple.html

Priority search queues provide the best behavior of both search trees
(O(log n) insert, delete, and find based upon a key-data mapping) and
priority queues (O(1) to find the highest priority element, O(log n) to
change the priority of any element).

This implementation is based around Red-Black trees.

Brian

[Ocaml-lib-devel] Third Library: Bitset

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

Third and last library being submitted for comment: Bitset.

This library implements sets of small non-negative integers as a bitset.  
The big advantage of this implementation is O(1) adding, removing, or 
testing for membership.

Brian

[Ocaml-lib-devel] New library 2: Psqueue

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

Second of three libraries I am submitting for comments: Psqueue.

This library implements a Priority Search Queue, based up Ralf Hinze's 
paper, see:
http://citeseer.nj.nec.com/hinze01simple.html

Priority search queues provide the best behavior of both search trees
(O(log n) insert, delete, and find based upon a key-data mapping) and
priority queues (O(1) to find the highest priority element, O(log n) to
change the priority of any element).

This implementation is based around Red-Black trees.

Brian

[Ocaml-lib-devel] New Library 1: XList

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

OK, The first of three libraries I'm submitting for comments:  XList.  

XList is a reimplementation of the Ocaml standard List library, except all
non-tail recursion has been removed, and instead I use Olivier Andrieu's
setcdr function.  This should be as fast as recursion for short lists, but 
work correctly (shouldn't blow stack) for long lists.

Well, for everything except two functions:  fold_right and fold_right2.  
For these two functions I did the reverse-the-list-first trick.  As this 
is slower than recursion for short lists, I also added fold_right' and 
fold_right2' which use non-tail recursion if it's important.

Brian

Re: [Ocaml-lib-devel] ExtLib v0.2

[Blair Z. <bl...@or...>]

Nicolas Cannasse wrote:
> 
> Okay, so perhaps somethink like :
> 
> let val_of = function
>     | None -> failwith "val_of"
>     | Some x -> x
> 
> is what you need ?
> But since I think some people will still want to catch the exception and use
> try...with instead of an easier pattern matching ( perhaps catching the
> exception to an upper level can be useful sometimes ), I would prefer :
> 
> exception ValNone
> 
> let val_of = function
>     | None -> raise ValNone
>     | Some x -> x

Sounds good to me.  So this way if you see a ValNone exception, you
know that you're not handling something that should be handled.

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/

Re: [Ocaml-lib-devel] ExtLib v0.2

[Nicolas C. <war...@fr...>]

> >     I disagree: val_of has two reasonable uses.  First, it can be
> > used with throwaway prototype programs, where simplicity and speed
> > matter more than correctness.  Second, it can be used where the
semantics
> > of the program dictate that the option has "Some" value.  If you don't
> > have a "Some" value in these cases, there often is nothing to do
> > except bail out in the "with" clause, so you might as well catch
> > the exception somewhere else higher up.
>
> Agreed.  I use Some values for my command line options which I verify
> before I use them, so I'd like to use them easily.

Okay, so perhaps somethink like :

let val_of = function
    | None -> failwith "val_of"
    | Some x -> x

is what you need ?
But since I think some people will still want to catch the exception and use
try...with instead of an easier pattern matching ( perhaps catching the
exception to an upper level can be useful sometimes ), I would prefer :

exception ValNone

let val_of = function
    | None -> raise ValNone
    | Some x -> x

Nicolas Cannasse

Re: [Ocaml-lib-devel] ExtLib v0.2

[Blair Z. <bl...@or...>]

Amit Dubey wrote:
> 
> 
>     I disagree: val_of has two reasonable uses.  First, it can be
> used with throwaway prototype programs, where simplicity and speed
> matter more than correctness.  Second, it can be used where the semantics
> of the program dictate that the option has "Some" value.  If you don't
> have a "Some" value in these cases, there often is nothing to do
> except bail out in the "with" clause, so you might as well catch
> the exception somewhere else higher up.

Agreed.  I use Some values for my command line options which I verify
before I use them, so I'd like to use them easily.

Best,
Blair

-- 
Blair Zajac <bl...@or...>
Plots of your system's performance - http://www.orcaware.com/orca/