ocaml-lib-devel — Developer's mailing list

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

Re: [Ocaml-lib-devel] Data Structures

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

On Wed, 14 May 2003, Nicolas Cannasse wrote:

> > 2) Ext-Lib should include data structures which are a) non-trivial to
> > implement, and b) widely (if not massively) usefull- by which I mean
> > many moderately complex programs can use one or more of them profitably.
> > Call this the "Java Standard Library" concept.  Note that this could
> > involve more than just data structures- things like XML-Light could be
> > included as well.
> 
> In the beginning of this list, I think we already talked about this point,
> and concluded that ExtLib should include "modules" that are either
> non-trivial to implement and widely used , or "modules" that are perhaps
> very easy to implement but massively used ( the second point is important,
> the goal here is to standardize a lttle more programming habits while each
> user have today his own implementation )

Widely used, or widely usable?  PSQueue gets a big check in the "complex 
to implement" column.  The paper I was working from:
http://citeseer.nj.nec.com/hinze01simple.html
was only published in 2001.  This isn't enough time for the structure to 
become popular yet.  On the other hand, I think it's a widely usefull 
structure- any time you need a priority queue that allows you to cheaply 
change priorities in the queue other than the top priority element it's 
usefull.

> 
> > 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 compared to the bloats and memory
> > leaks of your average C++ program.
> 
> I personnally don't like the Java Stdlib : too much classes ! Too much is
> becoming bad when you can't tell anymore when you need some library if it is
> included in the Stdlib or not : sometimes it takes less time to write a
> class from scratch than finding+learning how to use it from the Java Stdlib
> :-)

Give me a d20- I want to roll to disbeleive.  And yes, I've worked with 
Java.  And I'll even admit to getting caught out on not knowing the Ocaml 
standard libraries as well as I should either.  But I think that's a fault 
with me and my knowledge, not on the library.

And you run into this problem no matter how large or small the library is.  
I see people reimplementing strcat all the time in C.  The smaller and 
lighterweight the library is, the easier it is to reimplement.

> 
> > 2) It increases program efficiency by encouraging using complex data
> > structure where appropriate.  Part of the reason that lists, arrays, and
> > unbalanced trees are so popular is because they are trivial to
> > reimplement.  Part of the reason that priority search queues are not
> > popular is that they are non-trivial to implement.  This is why quicksort
> > is more popular than heapsort, and bubblesort is more popular than either
> > of them.
> 
> Perhaps true , but the user have to understand it ( see point 3 )

They have to understand the *interface*.

> 
> > 3) It increases awareness of the more complex data structures.  Another
> > part of the reason priority search queues aren't more widely used is that
> > they aren't known or understood.  Note this goes beyond just implementing
> > the data structures- I have a mostly-completed "gentle introduction to
> > priority search queues" kicking around at home.
> 
> I think that when you provide such a library, you have to provide a (short)
> introduction for each module . Especially concerning data structures, the
> user should be easily aware of what are the usage of each data structure
> provided by the library. IMHO, the best would be to have a comparative list
> of available data structures, with some examples of using them and
> complexity notations. If that compative list cannot show the user the main
> differences between 2 data structures, then one of them is useless :)

I agree.  Actually, I like the idea of having that table.  It's a 2D 
table- one dimension is the data structures, the other is the various 
operations.  The element i,j is the computational complexity (norm/max) of 
doing that operation on that data structure.  Data structures for which a 
given operation isn't supported are marked N/A.

If two columns of that table are identical, then either a) one of the data 
structures is redundant, or b) not all operations are listed.

I'll continue this is in seperate thread.

> 
> > Bit sets/arrays- although I'm begining to think this really should be an
> > adjunct to arbitrary precision integers.
> 
> Perhaps two differents modules would be good, even if they share the same
> internal representation , since you're not using the same way a Bitset and a
> big_int. Converting from and to a Num.num should be enough. ( that reminds
> me that "Big_int" and "Num" functions naming is quite "old styled" ending
> all with _big_int or _num, perhaps herited from ages ago, before the module
> system )
> 
> I forgot the following :
> - mutable data structures:
>     * Queue ( FIFO )

Speaking of not knowing your stdlib :-).  Check out the Queue module.

Brian

Re: [Ocaml-lib-devel] Xarray update

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

On Wed, 14 May 2003, Nicolas Cannasse wrote:

> > I liked the ability to specify resizer functions at creation time.  
> > Different xarrays, used for different purposes, might need different 
> > reallocation routines.  If the signatures aren't the most legible, a doc 
> > comment should clear up the confusion.
> 
> 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
(* sets the resizer function for an xarray *)

val get_resizer : t -> resizer_t
(* gets the current resizer function for a given xarray *)

val default_resizer : resizer_t
(* the default resizer function the library is using- allowing the library
   to change default schemes later on, and making it a more memorable
   name. *)

Brian

Re: [Ocaml-lib-devel] Data Structures

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

> 2) Ext-Lib should include data structures which are a) non-trivial to
> implement, and b) widely (if not massively) usefull- by which I mean
> many moderately complex programs can use one or more of them profitably.
> Call this the "Java Standard Library" concept.  Note that this could
> involve more than just data structures- things like XML-Light could be
> included as well.

In the beginning of this list, I think we already talked about this point,
and concluded that ExtLib should include "modules" that are either
non-trivial to implement and widely used , or "modules" that are perhaps
very easy to implement but massively used ( the second point is important,
the goal here is to standardize a lttle more programming habits while each
user have today his own implementation )

> 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 compared to the bloats and memory
> leaks of your average C++ program.

I personnally don't like the Java Stdlib : too much classes ! Too much is
becoming bad when you can't tell anymore when you need some library if it is
included in the Stdlib or not : sometimes it takes less time to write a
class from scratch than finding+learning how to use it from the Java Stdlib
:-)

> 2) It increases program efficiency by encouraging using complex data
> structure where appropriate.  Part of the reason that lists, arrays, and
> unbalanced trees are so popular is because they are trivial to
> reimplement.  Part of the reason that priority search queues are not
> popular is that they are non-trivial to implement.  This is why quicksort
> is more popular than heapsort, and bubblesort is more popular than either
> of them.

Perhaps true , but the user have to understand it ( see point 3 )

> 3) It increases awareness of the more complex data structures.  Another
> part of the reason priority search queues aren't more widely used is that
> they aren't known or understood.  Note this goes beyond just implementing
> the data structures- I have a mostly-completed "gentle introduction to
> priority search queues" kicking around at home.

I think that when you provide such a library, you have to provide a (short)
introduction for each module . Especially concerning data structures, the
user should be easily aware of what are the usage of each data structure
provided by the library. IMHO, the best would be to have a comparative list
of available data structures, with some examples of using them and
complexity notations. If that compative list cannot show the user the main
differences between 2 data structures, then one of them is useless :)

> Bit sets/arrays- although I'm begining to think this really should be an
> adjunct to arbitrary precision integers.

Perhaps two differents modules would be good, even if they share the same
internal representation , since you're not using the same way a Bitset and a
big_int. Converting from and to a Num.num should be enough. ( that reminds
me that "Big_int" and "Num" functions naming is quite "old styled" ending
all with _big_int or _num, perhaps herited from ages ago, before the module
system )

I forgot the following :
- mutable data structures:
    * Queue ( FIFO )

Nicolas Cannasse

Re: [Ocaml-lib-devel] Xarray update

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

> I liked the ability to specify resizer functions at creation time.  
> Different xarrays, used for different purposes, might need different 
> reallocation routines.  If the signatures aren't the most legible, a doc 
> comment should clear up the confusion.

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 ?

Nicolas Cannasse

Re: [Ocaml-lib-devel] Data Structures

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

On Mon, 12 May 2003, Nicolas Cannasse wrote:

> 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? 

Compare to strings, arrays, and simple trees?  No, probably not.  But I
see enough uses for the data structure that I thought it widely, if not
massively, usefull.

There are two lines of thought I can see:

1) Ext-Lib should only include those data structures in which it is hard 
to write something at all complex without, and focus on being small and 
light.  This is especially the case if it's going to be a replacement for 
the standard library.  Call this the "C Standard Library" concept.

2) Ext-Lib should include data structures which are a) non-trivial to 
implement, and b) widely (if not massively) usefull- by which I mean 
many moderately complex programs can use one or more of them profitably.  
Call this the "Java Standard Library" concept.  Note that this could 
involve more than just data structures- things like XML-Light could be 
included as well.

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 compared to the bloats and memory
leaks of your average C++ program.

Heck, one advantage Ocaml has is that it doesn't need different
implementations of linked lists and resizeable arrays for ints vr.s floats
vr.s other structures, like C++'s STL needs.  In the space C++ needs to 
implement xarrays for three different data types, Ocaml could be providing 
three different data structures.

Including more complex, less often used, data structures in a standard 
library has four advantages that I can think of:

1) It increases the amount of code reuse, and makes code easier to rewrite 
because you don't have to reimplement complex data structures.  This came 
up on a newsgroup recently, as someone was wondering why the SML/NJ 
implementations of some benchmarks were so much longer than the Ocaml 
implementations- the answer being that SML/NJ implemented a complete hash 
table algorithm, while Ocaml simply used the one in the standard library:
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=b897qr%24gbl%241%40wolfberry.srv.cs.cmu.edu&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26group%3Dcomp.lang.ml

2) It increases program efficiency by encouraging using complex data 
structure where appropriate.  Part of the reason that lists, arrays, and 
unbalanced trees are so popular is because they are trivial to 
reimplement.  Part of the reason that priority search queues are not 
popular is that they are non-trivial to implement.  This is why quicksort 
is more popular than heapsort, and bubblesort is more popular than either 
of them.

3) It increases awareness of the more complex data structures.  Another 
part of the reason priority search queues aren't more widely used is that 
they aren't known or understood.  Note this goes beyond just implementing 
the data structures- I have a mostly-completed "gentle introduction to 
priority search queues" kicking around at home.

4) It allows for optimization of common data structures which are not
usefull for individual programs, but are worthwhile if the cost is spread
out over many programs.  Ext-Lib's reimplementation of the List module is
a good example of this.  Currently psqueue.ml is not tail recursive- I
didn't think it worthwhile for the initial version of the library
(especially considering that, unlike List, most of the routines are O(log
n) in stack usage, meaning that stack overflows are unlikely).  But should
the library start being widely used, such optimizations might be
worthwhile- and they'd benefit everyone using the datastructure.  This is
the BLAS effect.

> 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

Bit sets/arrays- although I'm begining to think this really should be an 
adjunct to arbitrary precision integers.

Mutable doubly linked lists, where insertion anywhere into the list is
O(1).

Generic balanced (red-black?) trees.

Brian

Re: [Ocaml-lib-devel] Xarray update

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

On Sun, 11 May 2003, Nicolas Cannasse wrote:

> Xarray modifications :
>     - added exception policy ( Invalid_arg of int * string * string )
>     - added :
>             val empty : 'a t -> bool
>     - removed useless parenthesis in "if"

All the above are cool.

>     - removed ?resizer in functions, and added :
>             val set_resizer : 'a t -> resizer_t -> unit
>        this makes the source code and the signatures more readable.

I liked the ability to specify resizer functions at creation time.  
Different xarrays, used for different purposes, might need different 
reallocation routines.  If the signatures aren't the most legible, a doc 
comment should clear up the confusion.

Brian

[Ocaml-lib-devel] Data Structures

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

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 ? 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.

Nicolas Cannasse

[Ocaml-lib-devel] Xarray update

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

Xarray modifications :
    - added exception policy ( Invalid_arg of int * string * string )
    - added :
            val empty : 'a t -> bool
    - removed useless parenthesis in "if"
    - removed ?resizer in functions, and added :
            val set_resizer : 'a t -> resizer_t -> unit
       this makes the source code and the signatures more readable.

(should be commited when you read this mail)

Nicolas Cannasse

[Ocaml-lib-devel] XmlLight 2 Release

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

Hi list !

I'm please to announce the release of the version 2 of Xml-Light :
Xml Light is a small parser/printer for Xml documents, entirely written in
OCaml. It supports a subset of the Xml specification, which should be enough
for most of the usages, including DTD proving and PCDATA nodes. You can
download the distribution or watch the Ocamldoc HTML documentation on the
web page : http://tech.motion-twin.com/xmllight .

Any comments/remarks are of course more than welcome.

Nicolas Cannasse

[Ocaml-lib-devel] Need for XString?

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

I was wondering if there was any interest in an XString library, the basis 
of which I've attached (it needs to be cleaned up, documented, given a mli 
file, etc).  Basically, it's an unbalanced tree of strings.  This allows 
concatenation in strict O(1), and to_string in O(n) (n being the number of 
characters in the string).

On the other hand, a lot of it's functionality is taken up by the standard 
library Buffer (which I discovered after writting the above).

If there is interest, I'll clean it up and check it in.  If not, I'm going 
to delete it.

Brian

[Ocaml-lib-devel] Xml Light

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

Hi list !

Here's a pre release version of Xml-Light, fully working and documented. I'm
just waiting few more days for people comments before making a proper
release on the Caml-list. It will be then added to the ExtLib, with
additionnal functions such as Enum support. Any comments are welcome !

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

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

On Wed, 30 Apr 2003, Nicolas Cannasse wrote:

> > I'm playing (while waiting for compiles) at writting a circular, mutable,
> > doubly linked list data structure.  The advantage of this is that inserts
> > anywhere into the list are O(1), if you have a pointer into the list.
> >
> > Enum is almost a perfect vehicle for this- internal to the enum I'm
> > keeping a reference to the current element.  If I could just 'reach into'
> > the enum and snag this reference, all would be good with the world.  But I
> > can't figure out how to do that (this may be because it's friday afternoon
> > of a long, stressfull week and my brain is mush).
> 
> With circular lists, your next() function will of course never raise
> No_more_elements, and count() should also be something like :
> let rec infinite_count() = infinite_count()
> And doing an *.of_enum with a cicular list will of course run until you kill
> the process or run out of memory, same for Enum.iter... You could hack
> something like waiting for physical equality with the first element to break
> the loop, but if there is a map done before, you will never get it ! 

Sorry, I wasn't clear.  It's internal structure is circular so that I
don't have to define a NULL.  But externally it will be a finite list, and
have a most definate end and begining.  This circularness will be hidden 
internally.

Here's the basic idea I have so far and some example functions:

type 'a dllist_elem_t = { datum : 'a; mutable next : 'a dllist_elem_t;
                          mutable prev : 'a dllist_elem_t }

type 'a dllist_head_t = Empty | NotEmpty of 'a dllist_elem_t

type 'a dllist_t = 'a dllist_head_t ref

let head dllist =
    match !dllist with
        Empty -> assert false (* or something *)
        | NotEmpty head -> head.datum

let prepend dllist x =
    let rec newelem = { datum = x ; next = newelem ; prev = newelem } in
    match !dllist with
        Empty -> dllist := (NotEmpty newelem)
        | NotEmpty head ->
		newelem.next <- head;
                newelem.prev <- head.prev;
                head.prev <- newelem;
                newelem.prev.next <- newelem;
                dllist := NotEmpty(newelem)


let count dllist =
    match !dllist with
        Empty -> 0
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem cnt =
                if elem == tail then (cnt + 1) else
                loop (elem.next) (cnt + 1)
            in
            loop head 0


let iter f dllist =
    match !dllist with
        Empty -> ()
        | NotEmpty head ->
            let tail = head.prev in
            let rec loop elem =
                f elem;
                if (elem == tail) then () else loop elem.next
            in
            loop head



Notice in head- I don't return the dllist_elem_t, I return the element in 
it.  This is how I want it to work- dllist_elem_t never "leaks" out of the 
internal representation.  Also note that although I have a double 
dereference to get to the first element (the reference and the enumerated 
type) after that everything else is just 1 reference away.  

But this actually raises problems with doing a pointer type external from 
the linked list.  I suppose what I want is sort of an OO interface, with a 
"protected" inteface seen only inside the module, and a "public" interface 
I can put into the .mli and everyone can use.  But I'm not 100% sure how 
to do this.

Brian

Re: [Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

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

> I'm playing (while waiting for compiles) at writting a circular, mutable,
> doubly linked list data structure.  The advantage of this is that inserts
> anywhere into the list are O(1), if you have a pointer into the list.
>
> Enum is almost a perfect vehicle for this- internal to the enum I'm
> keeping a reference to the current element.  If I could just 'reach into'
> the enum and snag this reference, all would be good with the world.  But I
> can't figure out how to do that (this may be because it's friday afternoon
> of a long, stressfull week and my brain is mush).

With circular lists, your next() function will of course never raise
No_more_elements, and count() should also be something like :
let rec infinite_count() = infinite_count()
And doing an *.of_enum with a cicular list will of course run until you kill
the process or run out of memory, same for Enum.iter... You could hack
something like waiting for physical equality with the first element to break
the loop, but if there is a map done before, you will never get it ! Enums
are right know (and should remain) enumerations on finite set of elements, I
don't really see how you could use them with an infinite set... So once you
get your Enum from a circular list, how are you supposed to use it ? (
remember that next() is hidden ! ) I suggest then that you write a different
module, having an of_enum function that will create an list and make it
circular but no enum function since such Enum cannot be used later :-)

Nicolas Cannasse

Re: [Ocaml-lib-devel] email notices on cvs commits

[Maxence G. <max...@in...>]

On Tue, 22 Apr 2003 12:24:13 +0900
"Nicolas Cannasse" <war...@fr...> wrote:

> > > At work, our cvs is set up to email notices out to a mailing list when
> > > commits happen.  Any chance of setting up our cvs server to do that?
> >
> > I can do it, but I would prefer a "commitlog" file in /CVSROOT/commitlog
> > Since like this you can have a quick look at all modified files.
> 
> I have added the following to /CVSROOT/loginfo file, but it doesn't seems to
> work :
> 
> ALL (echo ""; id; echo %s; date; cat) >> $CVSROOT/CVSROOT/commit.log
> 
> 
> BTW, perhaps sourceforge CVS server is delaying some changes.
> If there is any CVS expert around...
> 
> Nicolas Cannasse
>

Have a look at the sourceforge site doc:

http://sourceforge.net/docman/display_doc.php?docid=772&group_id=1#scriptsyncmail

Hope this helps,

-- 
Maxence Guesdon

Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

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

Brian Hurt wrote:

> Especially in that I (the xarray module) don't know how large an 'a is.  
> Most likely it's just a reference off somewhere to some other type. 


Oh yeah .. my C/C++ experience lets me down here (many unboxed
data types of different sizes).

> Does anyone mind if I use named parameters for the resizer?  Use the type 
> (for example):
> resizer: numslots:int -> oldlength:int -> newlength:int -> int
> ?
> 
> Make it more obvious what the various arguments are.


I agree, this is a case where named parameters are 

a good idea: usage of strategy function is going
to be light (not much use), so the extra clutter
of naming is small but the benefit of seeing those
unfamiliar uses is correct is great.


BTW: with respect to boxing: we cannot support the
unboxed float array (etc) types the specialised Ocaml
arrays can. Or can we?

[Funny but once one gets down to optimisation,
the familiar problems of C/C++ turn up again:
smly, once one wants advanced name control,
again the same problems, and solutions, begin
to suggest themselves: C++ is messy because
users want things that are convenient and efficient,
which is not always the same thing as pure and clean..]

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

[Ocaml-lib-devel] Minor mods to xarray

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

Kicked off by my discussion with John Max Skaller in this list.

- made the type of resizer functions a named type (cleaning up a lot
of code and type definitions)
- added a third parameter to the resize functions- the old length of
the array (tells them if we're inserting or deleting)
- named the arguments to the resizer functions so I can fargin remember
what order they go in.
- Added a conservative resizer function to demonstrate why I added the
oldlength parameter.
- Cleaned up and (hopefully) improved several comment, especially
about resizer functions.
- Cleaned up exponential_resizer, so hopefully it's clearer what it's
doing.  And it doesn't need to be recursive anymore.
- Allowed 0 length arrays in a lot more places.
- changed name of newlength to changelength, to stop some name collisions

Brian

Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

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

On Sun, 27 Apr 2003, John Max Skaller wrote:

> Brian Hurt wrote:
> 
> > Certainly not difficult.  I just don't 
> > see what you get out of it.  
> 
> 
> Suppose you have a rule: when you're increasing the number
> of elements in the array, you can resize it, but never
> when you're decreasing them. That might be useful,
> but it cannot be implemented unless you know the number
> of elements in the array -- i don't mean slots of store
> but actual occupied slots.
> 
> For example: the number of slots is set to the number
> of elements on expansion. So for example adding 1 element
> at a time to 5 then subtracting, then adding again:
> 
> data slots
> 0     0
> 1     1
> 2     2
> 3     3
> 4     4
> 5     5
> 4     5
> 3     5
> 2     5
> 1     5
> 0     5
> 1     1
> 2     2
> 3     3
> 4     4
> 5     5

Ah!  Only reallocate when you start adding elements back in, but then 
shrink to a correct size.  You'd have to save state that you had shrunk, 
but that's not hard.

OK.  Yes, for that you need to know if you're adding or removing slots.

I was thinking you meant something like:
data	slots
0	0
1	1
2	2
3	3
2	3
1	3
0	0 <- shrink happened
1	1
2	2
...

etc.  You have the shrink happening on the first insert.

And that's actually not *that* strange of a resizing algorithm, especially 
if you know that deletes are "bursty".  It saves copying, and may even 
save short-term memory usage (if the GC wouldn't get around to collecting 
the old array soon enough).

> NOte that one could argue that passing
> in the size of a slot (in bytes) also makes
> sense, since a strategy may be based on tuning
> around memory amounts (Kbytes) due to the finiteness
> of this quantity, rather than the more abstract notion
> of a slot.

Especially in that I (the xarray module) don't know how large an 'a is.  
Most likely it's just a reference off somewhere to some other type.  Which 
is one of the reasons adding a user-defined resizer function is usefull.  
If you do know (or at least can guess) how big of data structures you're 
kicking around, write a specific resizer for it.  Or have a 
parameterizable resizing function, like I did with the step function.

Does anyone mind if I use named parameters for the resizer?  Use the type 
(for example):
resizer: numslots:int -> oldlength:int -> newlength:int -> int
?

Make it more obvious what the various arguments are.

Brian

Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

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

Brian Hurt wrote:

> On Fri, 25 Apr 2003, John Max Skaller wrote:
> 
>>-------------------------------------------------------- 
>>one thing I found: I needed 3 arguments not 2:
>>
>>current slots, current used slots, required size
>>
> 
> The inputs xarray has to give the resizer algorithm are:
> 
> - the current number of slots the array has
> 
> - the current number of slots the array needs
 
 
>>The extra argument is necessary for asymmetric growth/shrinkage
>>algorithms, so I recommend you add it: at present you cannot
>>take 'unused space' into account since it cannot be computed.
>>
>>
> 
> Hmm.  Consider the following case.  You have an array, using the doubling 
> algorithm, with a size of 16 and a length (number of used elements) of 10.  
> Now, you add an enumeration with 100 elements in it.
> 
> Currently, the resizer function is called with a currsize of 16 (the 
> current number of spaces in the array when it's called) and a length of 
> 110 (how many elements need to fit into the array).  Exponential_resizer 
> then keeps doubling 16 until it gets a long enough array size- 128 in this 
> case.  It returns 128.
> 
> If I understand you correctly, in this example you also want 10 (call it
> 'oldlength')  passed in as well.  


Yes.

> Certainly not difficult.  I just don't 
> see what you get out of it.  


Suppose you have a rule: when you're increasing the number
of elements in the array, you can resize it, but never
when you're decreasing them. That might be useful,
but it cannot be implemented unless you know the number
of elements in the array -- i don't mean slots of store
but actual occupied slots.

For example: the number of slots is set to the number
of elements on expansion. So for example adding 1 element
at a time to 5 then subtracting, then adding again:

data slots
0     0
1     1
2     2
3     3
4     4
5     5
4     5
3     5
2     5
1     5
0     5
1     1
2     2
3     3
4     4
5     5

The number of slots can shrink, but only
when the number of used slots increases.

Why would you want to do this? I have no idea.
But it is a viable algorithm and it cannot
be implemented without passing the number
of used slots in .. a general rule says
"pass the whole of the state in" and the
state is charactized by both the physical
slot count and the number of used slots.

NOte that one could argue that passing
in the size of a slot (in bytes) also makes
sense, since a strategy may be based on tuning
around memory amounts (Kbytes) due to the finiteness
of this quantity, rather than the more abstract notion
of a slot.

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

[Ocaml-lib-devel] Enum, doubly linked lists, and thoughts

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

I'm playing (while waiting for compiles) at writting a circular, mutable,
doubly linked list data structure.  The advantage of this is that inserts
anywhere into the list are O(1), if you have a pointer into the list.

Enum is almost a perfect vehicle for this- internal to the enum I'm 
keeping a reference to the current element.  If I could just 'reach into' 
the enum and snag this reference, all would be good with the world.  But I 
can't figure out how to do that (this may be because it's friday afternoon 
of a long, stressfull week and my brain is mush).

So this leaves me with three options, that I wanted to throw out to the 
listmind at large for input:

1) I can extend Enum to do what I want/need.  Nicolas is probably against 
this.  And here I think I actually agree with him- we don't want to extend 
Enum in ways that make it hard/inefficient/impossible to apply to native 
linked lists.

2) I can implement a whole new interface, call it Pointer for lack of a 
better name, and implement *that*.  One member of this interface being 
Pointer.enum_of, an O(1) creation of an enumeration given a pointer.

3) I can just add the pointer library, without any generalization (but
still with the enum_of function), to the Dllist library.

Thoughts?

Brian