ocaml-lib-devel — Developer's mailing list

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

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

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

Yeah yeah, replying to myself is bad.  Anyways, I wanted to send out an 
example of HTML for people to look at and critique.

Having played with this, I definately want to write a HTML generator for 
this page.  In Ocaml, natch.  Otherwise maintainance will be nigh unto 
impossible.

Brian

[Ocaml-lib-devel] Data structures table

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

Nicolas Cannasse came up with the idea of making a table of all data 
structures, all operations on those data structures, and the big-O cost of 
performing that operation.  What I'm thinking of is something like:

               Data Structure
               |     |     |      |  D  |
               |     |     |  H   |  y  |
               |     |     |  a   |  n  |
               |     |  A  |  s   |  a  |
               |  L  |  r  |  h   |  r  |
               |  i  |  r  |  t   |  r  |
               |  s  |  a  |  b   |  a  |
Operation      |  t  |  y  |  l   |  y  |
---------------+-----+-----+------+-----+
Find first elem|  1  |  1  | N/A  |  1  |
---------------+-----+-----+------+-----+
Find last elem |  N  |  1  | N/A  |  1  |
---------------+-----+-----+------+-----+
Find any elem  |  N  |  N  | lg N |  N  |
---------------+-----+-----+------+-----+
Prepend elem   |  1  |  N  | N/A  |  N  |
---------------+-----+-----+------+-----+
Append elem    |  N  |  N  | N/A  |  1  |
---------------+-----+-----+------+-----+
Insert elem    |  N  |  N  | lg N |  N  |
---------------+-----+-----+------+-----+

Obviously, using HTML and tables would be a better idea.  How you read 
this is if you're interested in a given operation- say Append (add an 
element at the end of the structure), then doing that with a list is O(N) 
(you have to duplicate the list), doing that with an array is O(N) (you 
have to allocate a new array and copy the data over), the operation is not 
meaningful with a hash table (where conceptually the data is unordered), 
and doing that with a Dynarray is O(1).

Hmm.  Actually, to prevent loads of N/As we probably want to break 
operations up into (at least) four different categories:

- Basic operations all data structures support, for example searching for
an element the fullfills a given criteria.

- Operations that depend upon ordered data- for example finding the first 
or last element.  Examples of data structures which are ordered include 
lists, arrays, and dynarrays.

- Operations that depend upon having keys associated with the data- for 
example, searching for the element that has is associated with a given 
key.  Examples of data structures which have keys are hash tables and 
priority search queues.

- Operations that depend upon having a priority relationship among 
elements, for example finding the highest priority element.  Examples of 
data structures which have priorities are queues, priority queues, and (of 
course) priority search queues.

Only data structures which "naturally" support those operations would be 
listed.  Alternatively, we could provide reasonable estimates on how 
expensive that operation would be to implement with the given data 
structure, and mark it somehow as needing to be implemented (different 
color?).

Thoughts?  Comments?

Brian

Re: [Ocaml-lib-devel] Data Structures

[Amit D. <ad...@Co...>]

> 
> Hi list,
> 
> When reading the PSQueue module, I was wondering if this one has to be in
> the ExtLib. Can an priority-search-queue can be considered "massively used"
> by ocaml developpers ?

    I hope this is not a rhetorical question, because I think the answer
is.... YES!!! :)

> More generally, it would be nice if we could be able
> to create a list of data structures that should be included in the ExtLib.
> The differents data-structures should be differents enough in terms of usage
> and/or complexity so the user can easily pick the one he needs when he have
> to write a program.
> 
> Right now we have :
> * non mutable
>     - caml list
>     - caml set
> * mutable
>     - caml stack
>     - caml arrays (not resizable)
>     - caml hashtables
>     - ref list
>     - resizable arrays
> 
> What should be added ? I think I have a mutable binary tree ( equiv of Set )
> somewhere that should be useful.

    My opinion - the more the merrier ;)  Right now in the extlib in the
Ocaml CDK, there is an implementation for "big" hashtables (conflicts stored
in a balanced tree rather than a linked list) and splay trees.  An
implementation of perfect hashtable would be nice (I have a simple one
lying around... it would be nice if there was a 'C' alternative to the
current hash function to use with perfect hashing, though).  I also have
an implementation of a heap using a resizable array, but I guess PSQueue would
supercede this.

    Some of us actually do use these esoteric data structures!!! ;)


    -Amit

Re: [Ocaml-lib-devel] Data Structures

[John M. S. <sk...@oz...>]

Nicolas Cannasse wrote:

 
>>Personally, I'm in favor of the Java-style library, the kitchen sink
>>concept.  I think that a couple of megabytes of "unnecessary" and unused
>>libraries isn't that big of problem 


The issue here I think is to keep the library 

comprehensible.


I personally never use 'java style' libraries.
Its easier to write the code myself than bother
learning someone elses interface, especial
one aimed at programmers that can't actually
program.

But then, Java probably is such a totally BAD language,
it probably needs the kitchen sink. I'm not sure,
I refuse to program in it.

-- 
John Max Skaller, mailto:sk...@oz...
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850

[Ocaml-lib-devel] Enum + Std update

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

I added the new primitive :
    Enum.from : ('a -> unit) -> 'a t
which is similar to Stream.from.

( The only difference is that the "count" function is calling "Enum.force",
which is creating a list of the values and then modifying the enum to
enumerate on the list with a count reference )

typical usages are for I/O where you can't provide a count function at
creation time :

let input_char_enum ch =
    Enum.from (fun () -> try input_char ch with End_of_file -> raise
Enum.No_more_elements)

(added to Std , with and implementation of input_all )

Nicolas Cannasse

Re: [Ocaml-lib-devel] Xarray update

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

> > I understand you, but it add to be in many functions if you want to do
so.
> > Perhaps only for XArray.make would be enough ?
>
> How about this.  We leave the resizer function off all the extant
> functions, but add three functions:
>
> val set_resizer : resizer_t -> t -> unit
> val get_resizer : t -> resizer_t
> val default_resizer : resizer_t

I added that to the CVS , renamed Xarray to DynArray , updated all the
documentation, added a Makefile and a README , and tested/corrected the
documentation generation with ocamldoc .

Nicolas Cannasse