ocaml-lib-devel — Developer's mailing list

[Ocaml-lib-devel] ExtList / Enum updates

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

ExtList - added :
    val filter_map : ('a -> 'b option) -> 'a list -> 'b list
    val unique : ?cmp:('a -> 'a -> bool) -> 'a list -> 'a list

Enum - added :
    val filter_map : ('a -> 'b option) -> 'a t -> 'b t
    val clone : 'a t -> 'a t

Enum.clone will enable you to enumerate several times over the same enum ,
the implementation is quite efficient.

Nicolas Cannasse

Re: [Ocaml-lib-devel] some proposals

[Remi V. <van...@la...>]

"Nicolas Cannasse" <war...@fr...> writes:

>> Which means we're probably stuck with something like:
>>
>> let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0
>
> Uh !
> This time Brian you're using up to TWO times polymorphic comparison
> !

well, If it is rewrite as :

let compare (x : int) (y:int) = if (x < y) then -1 else if (x > y) then 1 else 0

then there is no use of the polymorphic comparison function

[...]


-- 
Rémi Vanicat
va...@la...
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: [Ocaml-lib-devel] Re: some proposals

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

 > I considered implementing this as an enum.  But here's the problem: count
> requires you to know in advance how many elements you have.  The only way
> I can see doing this would be to create a list of pre-converted elements
> that didn't return None.  A stream might be a better choice.

Please remember I just added Enum.from !

--- Enum module -----

let filter_map f e =
    let rec next () =
        match f e.next with
        | None -> next()
        | Some x -> x
    in
    from next

-------------------

Nicolas Cannasse

Re: [Ocaml-lib-devel] some proposals

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

> Which means we're probably stuck with something like:
>
> let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0

Uh !
This time Brian you're using up to TWO times polymorphic comparison !
I think the most easy solution is really to use the substraction, but that
will cause the problems you showed with max_int / min_int , and doing some
previous boundary tests before return x - y will increase the cost of it. So
my conclusion is this is an user-specific problem (some might need max_int
while some might not ) which should be addressed by not adding the module
Int to the ExtLib, although it was a good idea.

About the partial_map, this can be done using a fold_left, which is more
appropriate since you don't allocate None/Some blocks . But I think perhaps
fold_left/right are not so easy to use in the first place, so maybe having a
partial_map would be nice , but I would rename it to filter_map since this
can be done using one map + one filter.

BTW, I would prefer a more simple version of the Brian one, which does not
need two loops :

let filter_map f l =
    let rec loop dst = function
        | [] -> ()
        | h :: t ->
            match f t with
            | None -> loop dst t
            | Some x ->
                    let r = [ x ] in
                    Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
                    loop r t
    in
    let dummy = [ Obj.magic () ] in
    loop dummy l;
    List.tl dummy

Nicolas Cannasse

Re: [Ocaml-lib-devel] Re: some proposals

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

On Thu, 22 May 2003, Alan Post wrote:

> The perl map function allows the number of outgoing items to be
> other than 1, for instance:
> 
>   my @l2 = map { if ( filter( $_ ) { $_ } else {()}} @l1;
> 
> or:
> 
>   my %h = map { $_, f( $_ )} @l;
> 
> I imagine it would be a bit tricky to implement an Enum function like
> that ("merge_map"?), but it would generalize the partial map function
> above.
> 
> 
> A more general question:  how many map/iterate functions will be a
> part of the data structures, as opposed to having users stick to the
> Enum versions?  For instance,
> 
>   List.map f l 
> 
>     vs
> 
>   List.of_enum (Enum.map f (List.enum l))
> 
> Will each datastructure have its own map function, to make things
> convenient for users?
> 

I considered implementing this as an enum.  But here's the problem: count 
requires you to know in advance how many elements you have.  The only way 
I can see doing this would be to create a list of pre-converted elements 
that didn't return None.  A stream might be a better choice.  

let stream_partial_map f src =
    let rec next curr_ref x =
        match !curr_ref with
          [] -> None
          | h :: t -> 
              curr_ref := t;
              match f h with
                  None -> next curr_ref x
                  | Some t -> Some t
    in
    Stream.from (next (ref src))
;;


But I hate having two different almost-identical-but-subtly-different
ways of doing things.  I think that instead of Enum module, we should 
consider an ExtStream module, with Enum functionality.

Brian

[Ocaml-lib-devel] Re: some proposals

[Alan P. <ap...@re...>]

In article <200...@ro...eak>, Michal Moskal wrote:
> 
> 1) For extList:
> 
> val partial_map : ('a -> 'b option) -> 'a list -> 'b list
> 
> let rec partial_map f = function
>  | x :: xs ->
>     begin
>       match f x with
>       | Some y -> y :: list_partial_map f xs
>       | None -> list_partial_map f xs
>     end
>  | [] -> []

The perl map function allows the number of outgoing items to be
other than 1, for instance:

  my @l2 = map { if ( filter( $_ ) { $_ } else {()}} @l1;

or:

  my %h = map { $_, f( $_ )} @l;

I imagine it would be a bit tricky to implement an Enum function like
that ("merge_map"?), but it would generalize the partial map function
above.


A more general question:  how many map/iterate functions will be a
part of the data structures, as opposed to having users stick to the
Enum versions?  For instance,

  List.map f l 

    vs

  List.of_enum (Enum.map f (List.enum l))

Will each datastructure have its own map function, to make things
convenient for users?

Re: [Ocaml-lib-devel] some proposals

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

On Thu, 22 May 2003, Brian Hurt wrote:

> Optimization question for the list at large: would doing:
> 
> let Int.compare (x : int) (y : int) : int = Pervasives.compare x y
> 
> be enough to allow the optimizer to do it's thing?
> 

Answering my own question: looks like no.

Which means we're probably stuck with something like:

let Int.compare x y = if (x < y) then -1 else if (x > y) then 1 else 0

Brian

Re: [Ocaml-lib-devel] some proposals

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

On Thu, 22 May 2003, Michal Moskal wrote:

> 
> 1) For extList:
> 
> val partial_map : ('a -> 'b option) -> 'a list -> 'b list
> 
> let rec partial_map f = function
>   | x :: xs ->
>     begin
>       match f x with
>       | Some y -> y :: list_partial_map f xs
>       | None -> list_partial_map f xs
>     end
>   | [] -> []
> 
> modulo tail-recursion tricks.

First cut:


let partial_map f src =
    let rec loop dst lst =
        match lst with
            [] -> ()
            | h :: t ->
                match f h with
                    None -> loop dst t
                    | Some b -> 
                        let r = [ b ] in
                        Obj.set_field (Obj.repr dst) 1 (Obj.repr r);
                        loop r t
    in
    let rec find_head lst =
         match lst with
             [] -> []
             | h :: t ->
                 match f h with
                     None -> find_head t
                     | Some b ->
                         let r = [ b ] in
                         loop r t;
                         r
    in
    find_head src


> 
> 2) Int module like:
> 
> module Int =
>   struct
>       type t = int
>       let compare x y = x - y
>   end

Compare needs to be a little bit more intelligent to handle carry.  
Consider that compare min_int max_int = 1, i.e. min_int > max_int.  While 
Pervasive.compare min_int max_int = -1 (which is correct).

Optimization question for the list at large: would doing:

let Int.compare (x : int) (y : int) : int = Pervasives.compare x y

be enough to allow the optimizer to do it's thing?

Brian

Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 01:19:21PM -0500, Brian Hurt wrote:
> On Thu, 22 May 2003, Remi Vanicat wrote:
> 
> > well, in the original code, one have :
> > 
> > let kmp p =
> >   let next = init_next p
> >   and m = String.length p in
> >   function s ->
> > 
> > So Partial application of the first argument already compute the next
> > table. and so you can call the computed function on several different
> > string. 
> 
> Check.  I'd missed that.  On the other hand, you compute the length of p 
> twice- once in kmp and once in init_next.  Which is what I was trying to 
> eliminate.  Maybe I was being stupid- how expensive is a String.length?  I 
> was assuming it was O(n), linear with the length of the string.

String.length is O(1) (with very small ,,1'' :-)

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

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

On Thu, 22 May 2003, Michal Moskal wrote:

> String.length is O(1) (with very small ,,1'' :-)

You learn something new everyday.  In this case, my optimizations to not 
call String.length are false optimizations and should be removed.  
Especially as they open the door for "ill-defined behavior" (aka bugs).

Brian

[Ocaml-lib-devel] some proposals

[Michal M. <mal...@pl...>]

1) For extList:

val partial_map : ('a -> 'b option) -> 'a list -> 'b list

let rec partial_map f = function
  | x :: xs ->
    begin
      match f x with
      | Some y -> y :: list_partial_map f xs
      | None -> list_partial_map f xs
    end
  | [] -> []

modulo tail-recursion tricks.

2) Int module like:

module Int =
  struct
      type t = int
      let compare x y = x - y
  end

To be used as input for Map.Make/Set.Make.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

[Hideo B. <ba...@im...>]

Hello,

A minor comment.

At Thu, 22 May 2003 10:51:25 -0500 (CDT),
Brian Hurt wrote:
> Sanity check this code, if you will:
>
> let kmp p =
(snip)

The algorithm looks to me like "Morris-Pratt" (MP),
and not "Knuth-Morris-Pratt" (KMP). KMP tries to exploit
a bit more information in the pattern in the preprocessing
stage to reduce redundant comparisons during the matching.

This may be a different issue but, I have heard (and read)
that Boyer-Moore style algorithms are much faster in practice,
often having a sub linear runtime (but I have never done any
benchmarks myself).

There are so many zillions of different algorithms!
e.g.:
  http://www-igm.univ-mlv.fr/~lecroq/string/index.html

but I guess almost everyone will only need one reasonable
implementation. Just something to think about.

--
Hideo Bannai <ba...@im...>
Human Genome Center, Institute of Medical Science, University of Tokyo
4-6-1 Shirokanedai, Minato-ku, Tokyo 108-8639, Japan.
Phone: +81-3-5449-5615 Fax  : +81-3-5449-5442

Re: [Ocaml-lib-devel] ExtString module updated

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

On Thu, 22 May 2003, Remi Vanicat wrote:

> well, in the original code, one have :
> 
> let kmp p =
>   let next = init_next p
>   and m = String.length p in
>   function s ->
> 
> So Partial application of the first argument already compute the next
> table. and so you can call the computed function on several different
> string. 

Check.  I'd missed that.  On the other hand, you compute the length of p 
twice- once in kmp and once in init_next.  Which is what I was trying to 
eliminate.  Maybe I was being stupid- how expensive is a String.length?  I 
was assuming it was O(n), linear with the length of the string.

Could we still preserve this, and only do a single string match, with code 
something like:

let find p =
    let m = String.length p in
    let next = String.KMP.compile' p m in
    fun s -> String.KMP.match' next m s

Where compile' and match' are versions of compile and match that take 
pre-computed string lengths-

let compile p = compile' p (String.length p)
and match pat s = match' pat (Array.length pat) s

?

Brian

Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 06:57:01PM +0200, Remi Vanicat wrote:
> well, in the original code, one have :
> 
> let kmp p =
>   let next = init_next p
>   and m = String.length p in
>   function s ->
> 
> So Partial application of the first argument already compute the next
> table. and so you can call the computed function on several different
> string. 

With the minor performance hit of additional closure allocation.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 01:12:02PM -0500, Brian Hurt wrote:
> > I think better as submodule:
> 
> Yes.  Can we do modules in modules?  

Sure.


-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

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

On Thu, 22 May 2003, Michal Moskal wrote:

> > Sanity check this code, if you will:
> > 
> >             if i >= (m - 1) then next
>                       ^^^^^^^
> 
> I'm not quite sure how good is ocamlc wrt moving constants out of loop,
> but probably moving this substraction out of the loop would be The Right
> Thing.

For a simple decrement I wouldn't worry too much about strength reduction.  
At worst it's a single clock cycle cost- i.e. too low to notice generally.

> > And it gets rid of all the references- 
> > which probably means a speed up (haven't tested it yet though).  
> 
> Maybe refs are optimized away by the compiler? But I don't know.

I don't know either.

> 
> > Although 
> > one thing we might want to consider: actually exporting the kmp_init 
> > function and kmp function seperately.  This way if I wanted to find the 
> > same substring in a lot of different strings, I don't have to constantly 
> > recreate the next table.  Maybe something like:
> [snip]
> 
> I think better as submodule:

Yes.  Can we do modules in modules?  I.e.: String.KMP.compile and 
String.KMP.match, like:

    let pat = String.KMP.compile p in
    String.find_all (fun s -> try let _ = String.KMP.match pat s in true
                              with Not_found -> false) strlist

Brian

Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 10:51:25AM -0500, Brian Hurt wrote:
> On Thu, 22 May 2003, Michal Moskal wrote:
> 
> > On Thu, May 22, 2003 at 06:51:04PM +0900, Nicolas Cannasse wrote:
> > > > > val find : string -> string -> int  (* find a substring *)
> > > >
> > > > Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
> > > > n are lengths of strings respectively? or O(log m * n + m))
> > > 
> > > Right now only a naive O(m*n) technique. Please check the CVS, and submit me
> > > some code if you have a better implementation.
> > 
> > You can have a look at http://caml.inria.fr/Examples/oc/basics/kmp.ml
> > 
> > I tried rewrite of while loop to tail recursion, but it looks ugly.
> > 
> > 
> 
> Sanity check this code, if you will:
> 
> let kmp p =
>     let m = String.length p in
>     let init_next p = 
>         let next = Array.create m 0 in
>         let rec loop i j =
>             if i >= (m - 1) then next
                      ^^^^^^^

I'm not quite sure how good is ocamlc wrt moving constants out of loop,
but probably moving this substraction out of the loop would be The Right
Thing.

> I don't think it's that ugly.  

Matter of taste I believe.

> And it gets rid of all the references- 
> which probably means a speed up (haven't tested it yet though).  

Maybe refs are optimized away by the compiler? But I don't know.

> Although 
> one thing we might want to consider: actually exporting the kmp_init 
> function and kmp function seperately.  This way if I wanted to find the 
> same substring in a lot of different strings, I don't have to constantly 
> recreate the next table.  Maybe something like:
[snip]

I think better as submodule:

extString.mli (or whatever):

module KMP = 
  sig
    type pattern
    val compile : string -> pattern
    val match : pattern -> string -> int
  end

val find : string -> string -> int

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

[Remi V. <van...@la...>]

Brian Hurt <bri...@ql...> writes:

> On Thu, 22 May 2003, Michal Moskal wrote:
>
>> On Thu, May 22, 2003 at 06:51:04PM +0900, Nicolas Cannasse wrote:
>> > > > val find : string -> string -> int  (* find a substring *)
>> > >
>> > > Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
>> > > n are lengths of strings respectively? or O(log m * n + m))
>> > 
>> > Right now only a naive O(m*n) technique. Please check the CVS, and submit me
>> > some code if you have a better implementation.
>> 
>> You can have a look at http://caml.inria.fr/Examples/oc/basics/kmp.ml
>> 
>> I tried rewrite of while loop to tail recursion, but it looks ugly.
>> 
>> 
>
> Sanity check this code, if you will:
>
> let kmp p =
>     let m = String.length p in
>     let init_next p = 
>         let next = Array.create m 0 in
>         let rec loop i j =
>             if i >= (m - 1) then next
>             else if p.(i) = p.(j) then
>                 begin
>                     next.(i+1) <- j+1;
>                     loop (i+1) (j+1)
>                 end
>             else if j = 0 then
>                 begin
>                     next.(i+1) <- 0;
>                     loop (i+1) j
>                 end
>             else
>                 loop i next.(j)
>         in
>         loop 1 0
>     in
>     let next = init_next p in
>     let n = String.length s in
>     let rec loop2 i j =
>         if (j >= m) || (i >= n) then
>             if j >= m then i - m
>             else raise Not_found
>         else if s.(i) = p.(j) then
>             loop2 (i+1) (j+1)
>         else if j = 0 then
>             loop2 (i+1) j
>         else
>             loop2 i next.(j)
>     in
>     loop2 0 0
> ;;
>
> I don't think it's that ugly.  And it gets rid of all the references- 
> which probably means a speed up (haven't tested it yet though).  Although 
> one thing we might want to consider: actually exporting the kmp_init 
> function and kmp function seperately.  This way if I wanted to find the 
> same substring in a lot of different strings, I don't have to constantly 
> recreate the next table.  Maybe something like:

well, in the original code, one have :

let kmp p =
  let next = init_next p
  and m = String.length p in
  function s ->

So Partial application of the first argument already compute the next
table. and so you can call the computed function on several different
string. 



[...]




-- 
Rémi Vanicat
va...@la...
http://dept-info.labri.u-bordeaux.fr/~vanicat

Re: [Ocaml-lib-devel] ExtString module updated

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

On Thu, 22 May 2003, Michal Moskal wrote:

> On Thu, May 22, 2003 at 06:51:04PM +0900, Nicolas Cannasse wrote:
> > > > val find : string -> string -> int  (* find a substring *)
> > >
> > > Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
> > > n are lengths of strings respectively? or O(log m * n + m))
> > 
> > Right now only a naive O(m*n) technique. Please check the CVS, and submit me
> > some code if you have a better implementation.
> 
> You can have a look at http://caml.inria.fr/Examples/oc/basics/kmp.ml
> 
> I tried rewrite of while loop to tail recursion, but it looks ugly.
> 
> 

Sanity check this code, if you will:

let kmp p =
    let m = String.length p in
    let init_next p = 
        let next = Array.create m 0 in
        let rec loop i j =
            if i >= (m - 1) then next
            else if p.(i) = p.(j) then
                begin
                    next.(i+1) <- j+1;
                    loop (i+1) (j+1)
                end
            else if j = 0 then
                begin
                    next.(i+1) <- 0;
                    loop (i+1) j
                end
            else
                loop i next.(j)
        in
        loop 1 0
    in
    let next = init_next p in
    let n = String.length s in
    let rec loop2 i j =
        if (j >= m) || (i >= n) then
            if j >= m then i - m
            else raise Not_found
        else if s.(i) = p.(j) then
            loop2 (i+1) (j+1)
        else if j = 0 then
            loop2 (i+1) j
        else
            loop2 i next.(j)
    in
    loop2 0 0
;;

I don't think it's that ugly.  And it gets rid of all the references- 
which probably means a speed up (haven't tested it yet though).  Although 
one thing we might want to consider: actually exporting the kmp_init 
function and kmp function seperately.  This way if I wanted to find the 
same substring in a lot of different strings, I don't have to constantly 
recreate the next table.  Maybe something like:

let _kmp_init_next p m =
    let next = Array.create m 0 in
    let rec loop i j =
        if i >= (m - 1) then next
        else if p.(i) = p.(j) then
            begin
                next.(i+1) <- j+1;
                loop (i+1) (j+1)
            end
        else if j = 0 then
            begin
                next.(i+1) <- 0;
                loop (i+1) j
            end
        else
            loop i next.(j)
    in
    loop 1 0

let kmp_init_next p = _kmp_init_next p (String.length p)

let _kmp next p s m =
    let n = String.length s in
    let rec loop2 i j =
        if (j >= m) || (i >= n) then
            if j >= m then i - m
            else raise Not_found
        else if s.(i) = p.(j) then
            loop2 (i+1) (j+1)
        else if j = 0 then
            loop2 (i+1) j
        else
            loop2 i next.(j)
    in
    loop2 0 0

let kmp next p s = _kmp next p s (String.length p)

let find p s =
    let m = String.length p in
    let next = _kmp_init_next p m in
    _kmp next p s m


Where kmp_init_next and kmp would be exported in the .mli file.  You could 
then write code like:

let find_all_substring substr strlist =
    let next = kmp_init_next substr in
    List.find_all (fun s -> try let _ = kmp next substr s in true
                   with Not_found -> false) strlist
;;

Brian

Re: [Ocaml-lib-devel] ExtString module updated

[Michal M. <mal...@pl...>]

On Thu, May 22, 2003 at 06:51:04PM +0900, Nicolas Cannasse wrote:
> > > val find : string -> string -> int  (* find a substring *)
> >
> > Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
> > n are lengths of strings respectively? or O(log m * n + m))
> 
> Right now only a naive O(m*n) technique. Please check the CVS, and submit me
> some code if you have a better implementation.

You can have a look at http://caml.inria.fr/Examples/oc/basics/kmp.ml

I tried rewrite of while loop to tail recursion, but it looks ugly.

-- 
: Michal Moskal :: http://www.kernel.pl/~malekith : GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::::: Wroclaw University, CS Dept : {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] ExtString module updated

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

> > val find : string -> string -> int  (* find a substring *)
>
> Using KMP or some other technique? (i.e. if it takes O(m * n), where m and
> n are lengths of strings respectively? or O(log m * n + m))

Right now only a naive O(m*n) technique. Please check the CVS, and submit me
some code if you have a better implementation.

Nicolas Cannasse

[Ocaml-lib-devel] ExtString module updated

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

Added :

val ends_with : string -> string -> bool

val find : string -> string -> int  (* find a substring *)

and implemented all ExtString functions.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Data structures table- trial HTML

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

On Mon, 19 May 2003, Nicolas Cannasse wrote:

> But few comments here :
> - reading verticaly the names of the data structures in a pain :)

Yeah.  There is a tradeoff there, when I start putting real data into it- 
horizontal structure names mean wide, irregular width, columns, and a much 
wider table.  Vertical structure names make for regular width columns, and 
a much thinner table.  But you're right, it's harder to read.

> - I think we need more primitives, for example it's not specified that the
> "index" access on arrays is O(1) , and actually prepend/append/insert/remove
> are not valid operations on arrays since it is not resizable.

Sorry.  The data is not necessarily even *correct*- it's just a test file 
I'm running through my program.  After the programm is more or less 
finished, we start filling in the data.  I was just wondering if the HTML 
I was producing worked.

> - we need more explanations than that.

Version 2.0 is going to have comments.  And classes- so we're not trying 
to compare linked lists with hash tables.  And probably other bells and 
whistles.

> 
> Here's how I see the thing :
> 
> There is no direct comparison between the differents data structures, but
> even a beginner can have a quick read at the list to understand about the
> main differences between data structures.
> 

I like the idea of table.  Used properly, they allow the programmer to 
"these are the operations I'm most concerned with- what data structures 
are best to use?"

I'll post the code here when it's in viewable form.

Brian

Re: [Ocaml-lib-devel] Data structures table- trial HTML

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

> Could someone with IE on Windows take a quick peek at the included HTML
> file and see if it looks sane or not?  It's validated HTML 3.2 Final- but
> it should work just fine one most any browser.  People with Opera and
> other browsers please test as well.  I've looked at it under Netscape and
> Konqueror on Linux, and all looks well.

Thanks Brian , it works.
But few comments here :
- reading verticaly the names of the data structures in a pain :)
- I think we need more primitives, for example it's not specified that the
"index" access on arrays is O(1) , and actually prepend/append/insert/remove
are not valid operations on arrays since it is not resizable.
- we need more explanations than that.

Here's how I see the thing :

List : Ocaml list are immutable, you cannot then modify their contents, but
since they're implemented as linked list, you can easily append elements at
the beginning. List in Ocaml are efficient enough for most of the usages. If
you need a list were contents can be changed, see the RefList module.
    <followed by sample samples on basic list operations with complexity>

 Array : Ocaml arrays are not resizable, but provide constant-time indexed
access. If you need resizable arrays, use DynArray
 < and so on... >

There is no direct comparison between the differents data structures, but
even a beginner can have a quick read at the list to understand about the
main differences between data structures.

Nicolas Cannasse

[Ocaml-lib-devel] Data structures table- trial HTML

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

Could someone with IE on Windows take a quick peek at the included HTML
file and see if it looks sane or not?  It's validated HTML 3.2 Final- but
it should work just fine one most any browser.  People with Opera and
other browsers please test as well.  I've looked at it under Netscape and
Konqueror on Linux, and all looks well.

Many thanks.

Brian