ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Proposed addition to DynArray

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

On Thu, 29 May 2003, Brian Hurt wrote:

> I don't have a problem with a pre-expand, but adding elements out of order
> doesn't work (at least the way I think they work).  If the dynarray has n
> elements, the elements are numbers 0..n-1 inclusive.
>
> The solution is to use a 'a option Dynarray.t.  You're null element then
> becomes None.  I dislike exposing the null elements as "valid entries"- to
> my mind, they're just filler.  This is especially important if you
> consider an int Dynarray.t - is that 0 a real, important 0, or a null
> element?  So I would would fake up a enum that returns n Nones and append
> it to the dynarray to increase the size.  Dynarray.set can then change the
> Nones to Some x.

Yeah, exposing phony nulls was one of the philisophical issues I was
wrestling with as I added my expansion hack.  At the time I decided that
the ability to do this outweighed the potential to do something silly (and
I promised myself to always look out for null values (the null I'm using
in this case would never be a valid value, so I can ignore them when I run
across them).

And you're right, expanding the array the way I described it won't work
like I wanted, you have to do something along the lines of:

let null = "";;
let j = DynArray.make 2 null;;
DynArray.add j "blah";;
DynArray.add j "flah";;

(* Now I want to add something to slot 9 *)

ignore (Dynarray.append j (DynArray.init 8 8 null (fun x -> null)));;
DynArray.set j 9 "flee";;

Where the length field is artificially pushed out to the end of the array,
so stuff can be added out of order.  But this does expose all those
not-really-null nulls in spots 2 - 8.  Now that I think about it this
might be best left out.  However, if it is added, it should be called
unsafe_expand or something similar so people realize that they're
willfully doing something "incorrect".

Sigh...why does doing things the right way always interfere with doing
what I think I want...

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

Re: [Ocaml-lib-devel] Proposed addition to DynArray

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

On Thu, 29 May 2003, William D. Neumann wrote:

> I have a situation  where I need to expand the
> size of the array to fit the data I will be adding, but I might be adding
> the elements out of order, so I can't just call DynArray.add

I don't have a problem with a pre-expand, but adding elements out of order 
doesn't work (at least the way I think they work).  If the dynarray has n 
elements, the elements are numbers 0..n-1 inclusive.

The solution is to use a 'a option Dynarray.t.  You're null element then
becomes None.  I dislike exposing the null elements as "valid entries"- to
my mind, they're just filler.  This is especially important if you
consider an int Dynarray.t - is that 0 a real, important 0, or a null
element?  So I would would fake up a enum that returns n Nones and append
it to the dynarray to increase the size.  Dynarray.set can then change the
Nones to Some x.

We might want to consider adding a function in Enum to create an enum that 
returns so many of a given value, to make this easier.

Brian

[Ocaml-lib-devel] Proposed addition to DynArray

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

I currently need some of the DynArrays that I'm working with to have the
ability to expand to a given size without adding a series of elements
onto the end of the array (I have a situation  where I need to expand the
size of the array to fit the data I will be adding, but I might be adding
the elements out of order, so I can't just call DynArray.add).

Now, I can easily do this externally with a call to make and then blit
(or append if the DynArray is a non-mutable record field or class
member), or I could add it to my local copy of the DynArray module itself
via something like:

let expand darr new_length =
  if new_length > darr.length then
    changelength darr (new_length - darr.length)

and adding the appropriate blurb to the interface.

I'm just wondering if anyone else thinks this would be useful enough to
add to the DynArray module proper... Discuss.

William D. Neumann

---

"Well I could be a genius, if I just put my mind to it.
And I...I could do anything, if only I could get 'round to it.
Oh we were brought up on the space-race, now they expect you to clean toilets.
When you've seen how big the world is, how can you make do with this?
If you want me, I'll be sleeping in - sleeping in throughout these glory days."

	-- Jarvis Cocker

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

> Enum.fold has to set up an exception stack every time it calls next.  It
> only catches an exception once- but it has to set up the stack frame every
> single time.  And that costs.

You're benchmark is just comparing one try...catch with one None/Some
matching. When you are doing some O(1) functional operations you have to do
1 try...catch and 'N' None/Some matching. But according to your results I
modified the implementation of fold in order not to setup a stack frame
every time :

let fold f init t =
 let acc = ref init in
 let rec loop() =
  acc := f (t.next()) !acc;
  loop()
 in
 try
  loop()
 with
  No_more_elements -> !acc

It should now be very efficient.

> In either case, interface harmonization is a more important issue IMHO.
> The exported definition of next should not be any more complicated than:
>     let next t = t.next ()

I already told several times about this : if we let escape the
No_more_elements exception outside of the API, then maybe one iter upper in
the call stack will catch it and break iteration , so if the user fail to
catch it properly when calling next() it can cause very error prone
behaviors since he won't be noticed about the exception being raised.

exemple  :

let e1 = List.enum [1;2;3]
let e2 = List.enum []

let combine x =
    (x  , Enum.next e2)

let l = Enum.of_list (Enum.map combine e1)

=> []

So we have to keep the current next implementation.

Nicolas Cannasse

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

On Wed, 28 May 2003, Nicolas Cannasse wrote:

> > > I don't agree here :
> > > - BUT the internal next is most of the time "concatening" the next
> functions
> > > in a purely functional way, so for example after two Enum.maps and doing
> an
> > > Enum.iter, you'll have to check the None/Some three times !
> >
> > For Enum.iter this is correct.  However, for doing just about anything
> > else you need to try/catch the exception the same number of times you need
> > to check for None/Some.  And I would expect map and fold to be at least as
> > important as iter.
> 
> I don't think so... here's current Enum.map implementation :

Oh.  You're right- I forgot Enum.map was O(1).  I was mainly thinking of 
fold, and tossed map in as well without thinking about it.

> In this sequence, there is only 1 catch for the exception if you're using
> Enum.iter or 2 if you're using Enum.fold , and it does not depends of the
> number of maps / filters you have done ! Here will be a map with next
> returning 'a option :

Enum.fold has to set up an exception stack every time it calls next.  It 
only catches an exception once- but it has to set up the stack frame every 
single time.  And that costs.

> Exceptions are really cheap in ocaml, better than pattern matching since the
> caml stay unwinding is very efficient.

Attached are a pair of simple benchmarks I whipped up.  Basically, they 
compare the relative costs of raising an exception vr.s returing 
None/Some.  I checked the output, and compiling with "ocamlopt -o test 
test1.ml" (or 2, as the case may be) doesn't "overoptimize" the test.

The file called test1.ml uses exceptions, and runs in 2.18 seconds on my 
system.  The file called test2.ml uses Some/None, and runs in 1.3 seconds.  
Exceptions are fast.  Just not as fast as allocating a word of memory and 
taking a branch.  Playing around with the code a little bit leads me to 
beleive that 0.7 seconds are program overhead, so as an approximation, 
catching an exception is 2.5x as expensive as Some/None.  Rough 
approximation here.  But it's actually a lot closer than I would have 
guessed.

In either case, interface harmonization is a more important issue IMHO.  
The exported definition of next should not be any more complicated than:
    let next t = t.next ()

Brian

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

> > I don't agree here :
> > - BUT the internal next is most of the time "concatening" the next
functions
> > in a purely functional way, so for example after two Enum.maps and doing
an
> > Enum.iter, you'll have to check the None/Some three times !
>
> For Enum.iter this is correct.  However, for doing just about anything
> else you need to try/catch the exception the same number of times you need
> to check for None/Some.  And I would expect map and fold to be at least as
> important as iter.

I don't think so... here's current Enum.map implementation :

let map f t =
 {
  count = t.count;
  next = (fun () -> f (t.next()));
 }

Every time we're catching only the exception one at the very end, since the
map doesn't check for it, and the fold is only used to "finalize" an d Enum.
Common usage of enums is the following :

let e = DataStructure.enum d in
let e = Enum.map f e in
... several maps / filter ....
let d = DataStructure.of_enum d  (* this one will call Enum.fold or
Enum.iter *)

In this sequence, there is only 1 catch for the exception if you're using
Enum.iter or 2 if you're using Enum.fold , and it does not depends of the
number of maps / filters you have done ! Here will be a map with next
returning 'a option :

let map f t =
    {
        count = t.count;
        next = (fun () -> match t.next() with None -> None | Some e -> Some
(f e));
    }
and thus matching and allocating blocks all around...
Exceptions are really cheap in ocaml, better than pattern matching since the
caml stay unwinding is very efficient.

Nicolas Cannasse

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

On Tue, 27 May 2003, Nicolas Cannasse wrote:

> > Now consider rewritting this to take an Enum instead of a list.  You have
> > to force the algorithm into fold somehow- which means managing a
> > handrolled stack (the above code is double non-tail recursive).
> 
> Since you're building a tree you don't need to be tail rec ( the stack will
> grow in O(log n) ! )

Yeah.  Building a stack isn't the problem- in fact, I have to do that for 
tree_to_enum.  It's the complexity of the stack.  

> 
> > For sheer code clarity, I think 'a option is a cleaner response than
> > throwing an exception.
> 
> I don't agree here :
> - BUT the internal next is most of the time "concatening" the next functions
> in a purely functional way, so for example after two Enum.maps and doing an
> Enum.iter, you'll have to check the None/Some three times ! 

For Enum.iter this is correct.  However, for doing just about anything 
else you need to try/catch the exception the same number of times you need 
to check for None/Some.  And I would expect map and fold to be at least as 
important as iter.

In both cases the expected case is for it not to be the end of the 
enumeration- for the exception not to be thrown, or for Some x to be 
returned.  I don't know how expensive setting up a try/catch block is, but 
since the branch between None/Some is a highly predictable branch, the 
cost of the branch is 1 clock cycle *or less*.  Add another clock cycle 
for the memory load (from L1 cache- the word was just allocated and 
filled).  Below the level that would be measurable in any real-world case, 
would be my guess.  In either case, I think this is a premature 
optimization.

Plus there is the problem of having the exported next behaving differently 
from the imported next- a likely source of confusion.

Brian

Re: [Ocaml-lib-devel] Enum.iter2

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

On Tue, 27 May 2003, Nicolas Cannasse wrote:

> > Is there a reason why Enum.iter2 does index stuff?
> 
> Certainly a too fast copy/fast from Enum.iter2i  , not mine but it's been
> properly fixed.

Mine, I think.

Brian

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

> You have two types (Enum and Stream) and a clear way to distinguish
> them (whether count always makes sense). If you merge them, you push
> the distinguishing feature to runtime.
>
> Also, it's not clear what the semantics of count on Stream are. Consider
> Stream.of_list; does it do one traversal on creation to take the count?
> Does it do it on the first call to count?  What if it's on a List with
> setcdr?  Should count be treated as an expensive or an inexpensive op?
>
> I think it makes sense to create a stream from an enum, but the opposite
> is not true.  I think we are lucky count is there to remind us.  If you
> agree with this, then the two types should not be unified.

I totally agree with you here.
The only thing that should be mentionned, is that you can always use Enum
instead of Stream, because it's better :
- if the user doesn't need count, then it's better because he still can use
all functionnal ops in Enum , as well as of_enum implementations in several
data structures
- if the user does need count, then Enum is providing the best way of doing
it (that is : actually really "counting" elements, one by one) in an
efficient way (see Enum.force) since only the first call to count will be
costly.

Nicolas Cannasse

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

> > Even if I like Streams I think that enums are somehow much powerful and
less
> > error prone (since you can't do next() ).
>
> The more I think about this, the more I disagree.  Case in point: consider
> taking a list of items and turning it into a balanced tree.  Using the
> standard list operations, this is not too horribly ugly:
>
>
> type 'a tree_t = Void
>                | Node of 'a tree_t * 'a * 'a tree_t

Errr...
I didn't think about recursive structures. It's true that having Enum.next()
would be here very better.
So ok let's add :
    val next : 'a Enum.t -> 'a option

(updated CVS)

> Now consider rewritting this to take an Enum instead of a list.  You have
> to force the algorithm into fold somehow- which means managing a
> handrolled stack (the above code is double non-tail recursive).

Since you're building a tree you don't need to be tail rec ( the stack will
grow in O(log n) ! )

> For sheer code clarity, I think 'a option is a cleaner response than
> throwing an exception.

I don't agree here :
- the new "exported" next is returning 'a option and that's a good thing (
no need to catch exception, code is more clear )
- BUT the internal next is most of the time "concatening" the next functions
in a purely functional way, so for example after two Enum.maps and doing an
Enum.iter, you'll have to check the None/Some three times ! Raising an
exception which propagate to the upper level is really a better choice.
- this choice is only making the code a little harder for the Enum modules,
other modules will never have to catch No_more_elements.

I think this is a good compromise.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Enum.iter2

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

> Is there a reason why Enum.iter2 does index stuff?

Certainly a too fast copy/fast from Enum.iter2i  , not mine but it's been
properly fixed.

Thanks again for the report,
Nicolas Cannasse

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

[Manos R. <er...@cs...>]

On Mon, May 26, 2003 at 06:49:15PM -0500, Brian Hurt wrote:
> 
> Replying to myself...
> 
> On Mon, 26 May 2003, Brian Hurt wrote:
> 
> > But you're right, count needs to be an optional thing.
> > 
> 
> val count: ExtStream.t -> int option
> 
> where a return value of Some x means the stream has x elements, and a 
> return value of None means that count is not implemented.  This has the 
> advantage of roping the type checker in to make sure everyone checks for 
> the non-implemented version.

You have two types (Enum and Stream) and a clear way to distinguish 
them (whether count always makes sense). If you merge them, you push 
the distinguishing feature to runtime. 

Also, it's not clear what the semantics of count on Stream are. Consider
Stream.of_list; does it do one traversal on creation to take the count?
Does it do it on the first call to count?  What if it's on a List with
setcdr?  Should count be treated as an expensive or an inexpensive op?

I think it makes sense to create a stream from an enum, but the opposite
is not true.  I think we are lucky count is there to remind us.  If you
agree with this, then the two types should not be unified. 

-- Manos

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

Replying to myself...

On Mon, 26 May 2003, Brian Hurt wrote:

> But you're right, count needs to be an optional thing.
> 

val count: ExtStream.t -> int option

where a return value of Some x means the stream has x elements, and a 
return value of None means that count is not implemented.  This has the 
advantage of roping the type checker in to make sure everyone checks for 
the non-implemented version.

Now, two possibilities for doing a destructive count (i.e. one that clones 
the ExtStream and then reads ahead to see how many items are left).  The 
first one is:

val destructive_count : ExtStream.t -> int

let destructive_count enum =
    match enum.count () with
        Some x -> x
        | None ->
            let e = ExtStream.clone enum in
            let rec loop count =
                match e.next() with
                    None -> count
                    | Some _ -> loop (count + 1)
            in
            loop 0

i.e. we clone and loop everytime destructive_count is called.

The other one is:

val destructive_count: ExtStream.t -> ExtStream.t

let destructive_count enum =
    let e = ExtStream.clone enum in
    let rec loop count =
        match e.next () in
            None -> count
            | Some _ -> loop (count + 1)
    in
    let countref = ref (loop 0) in
    let next () =
        match enum.next () with
            None -> None
            | Some x -> decr countref; Some x
    and count () = !countref in
    ExtStream.make next count

In this case, we run through the enumeration only once- and create a new 
enumeration which decrements a reference every call to next.

There are advantages and disadvantages to each.

Brian

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

On Mon, 26 May 2003, Manos Renieris wrote:

> On Mon, May 26, 2003 at 05:51:36PM -0500, Brian Hurt wrote:
> > 
> > The more I think about, the more I think the solution is to merge Stream 
> > and Enum, and create a best-of-breed interface (probably called 
> > ExtStream).  IMHO, this api would:
> > 	- have an exported next, like Stream
> > 	- have an exported count, like Enum
> 
> On streams generated from list's or files, count is not a sensible
> operation, or am I mistaken? 
> 

From lists, it's an O(N) operation but easy enough (List.length).  For any 
datastructure where traversing the elements is not destructive, count is 
also easily doable.

But for files, "traversing the elements" is destructive- you read the 
file.  And if the file really is the console and the user typing stuff in, 
you can't just rewind and reread the file either.  At which point you need 
to create the interim list of objects.

But you're right, count needs to be an optional thing.

Brian

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

[Manos R. <er...@cs...>]

On Mon, May 26, 2003 at 05:51:36PM -0500, Brian Hurt wrote:
> 
> The more I think about, the more I think the solution is to merge Stream 
> and Enum, and create a best-of-breed interface (probably called 
> ExtStream).  IMHO, this api would:
> 	- have an exported next, like Stream
> 	- have an exported count, like Enum

On streams generated from list's or files, count is not a sensible
operation, or am I mistaken? 

-- Manos

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

On Mon, 26 May 2003, Nicolas Cannasse wrote:

> > Also todo: to_enum, of_enum, to_stream, and of_stream should be added.
> > The to_* should be both by priority and by key.
> 
> Even if I like Streams I think that enums are somehow much powerful and less
> error prone (since you can't do next() ). 

The more I think about this, the more I disagree.  Case in point: consider 
taking a list of items and turning it into a balanced tree.  Using the 
standard list operations, this is not too horribly ugly:


type 'a tree_t = Void
               | Node of 'a tree_t * 'a * 'a tree_t

let tree_from_lst lst =
    let rec subtree lst len =
        if (len > 1) then
            let pivot = len/2 in
            let left, lst' = subtree lst pivot in
            match lst' with
                h :: t -> 
                    let right, t' = subtree t (len - pivot - 1) in
                    Node(left, h, right), t'
                | _ -> assert false
        else if (len > 0) then
            match lst with
                h :: t -> Node(Void, h, Void), t
                | _ -> assert false
        else
            Void, lst
    in
    let len = List.length lst in
    if (len > 0) then
        let tree, _ = subtree lst (List.length lst) in
        tree
    else
        Void

Now consider rewritting this to take an Enum instead of a list.  You have 
to force the algorithm into fold somehow- which means managing a 
handrolled stack (the above code is double non-tail recursive).  
Signifigantly uglier.

On the other hand, using a stream is almost as bad, as you need a way to 
find out the number of elements in the stream before starting (above done 
with a call to String.length).

The above code, or rather code much like it, showed up in some exploratory 
code I was doing to implement a interval map (see the thread in the main 
list).  The idea being that a tree would make inserts and removals O(log 
N), while I could do (for example) unions by first converting both trees 
to a list, unioning the lists, and recreating the tree from the unioned 
list, list:

let union a b =
    let rec loop alst blst accum =
        match alst, blst with
           (amin, amax):: atail, (bmin, bmax)::btail ->
               if (amax < bmin) then
                   loop atail blst ((amin, amax) :: accum)
               else if (bmax < amin) then
                   loop alst btail ((bmin, bmax) :: accum)
               else
                   loop atail btail (((min amin bmin), (max amax bmax))
                                      :: accum)
            | _, [] -> List.rev_append accum alst
            | [], _ -> List.rev_append accum blst
            | [], [] -> List.rev accum
    in
    let alist = list_from_tree a
    and blist = list_from_tree b
    in
    tree_from_list (loop alist blist)
;;

But this requires me to instantiate both lists completely- requiring O(N) 
memory overhead to complete.  If I could "virtualize" the construction of 
the lists as an enumeration or stream, I could reduce the memory 
requirements to O(log N).  It's not hard to force list_from_tree into an 
enumeration.  I need to fake a stack, but in this case it's cleaner- all I 
need for a stack is the list of nodes I need to go down the left hand 
side of.  But forcing tree_from_list into Enum.map is neither simpler
than the above code, nor less error prone.  Signifigantly more complicated 
and error prone, I would think.

> Adding Stream support to psqueue
> would imply adding it for other data structures as well ( since we went to
> make things consistent ).
> I would prefer an  Enum.stream / Enum.of_stream and keep only "enum" usage
> into data structures.

The more I think about, the more I think the solution is to merge Stream 
and Enum, and create a best-of-breed interface (probably called 
ExtStream).  IMHO, this api would:
	- have an exported next, like Stream
	- have an exported count, like Enum
	- have the usual gang of suspects- map, iter, fold, etc.
	- next returns 'a option, with None meaning no more elements,
	  like Stream, instead of returning 'a and throwing an exception
	  on no more elements.

For the last one, fold (for example) currently looks like:
let fold f init t =
        let ret = ref init in
        let rec loop accu =
                loop (f (try t.next() with No_more_elements as e -> ret := 
accu; raise e) accu)
        in
        try
                loop init
        with
                No_more_elements -> !ret

If next returns 'a option instead of 'a, we could rewrite it like:

let fold f init t =
    let rec loop accu =
        match t.next() with
            None -> accu
            | Some x -> loop (f x accu)
    in
    loop init

For sheer code clarity, I think 'a option is a cleaner response than 
throwing an exception.

Brian

Re: [Ocaml-lib-devel] De-functor-ized Psqueue

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

> Also todo: to_enum, of_enum, to_stream, and of_stream should be added.
> The to_* should be both by priority and by key.

Even if I like Streams I think that enums are somehow much powerful and less
error prone (since you can't do next() ). Adding Stream support to psqueue
would imply adding it for other data structures as well ( since we went to
make things consistent ).
I would prefer an  Enum.stream / Enum.of_stream and keep only "enum" usage
into data structures.

Nicolas Cannasse

[Ocaml-lib-devel] Re: some proposals

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

In article <slr...@re...>, 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 just realized that perl map is simply:

  let merge_map f e = Enum.concat (Enum.map List.enum (Enum.map f e))

[Ocaml-lib-devel] Enum.iter2

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

Is there a reason why Enum.iter2 does index stuff?  Currently the
implementation is:

let iter2 f t u =
        let rec loop idx =
                f (t.next()) (u.next());
                loop (idx + 1)
        in
        try
                loop 0
        with
                No_more_elements -> ()


Why not:

let iter2 f t u =
        let rec loop () =
                f (t.next()) (u.next());
                loop ()
        in
        try
                loop ()
        with
                No_more_elements -> ()

[Ocaml-lib-devel] De-functor-ized Psqueue

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

Added a create function in place of the old empty.  Fixed queue_to_string 
while I was in there to use a string buffer instead of just endlessly 
concating strings.  This should be more efficient.  Note that priorities 
are still implicitly part of the data.  Not that I'm opposed to making 
priorities just ints, but one major change at a time.

Also todo: to_enum, of_enum, to_stream, and of_stream should be added.  
The to_* should be both by priority and by key.

Brian

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

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

Brian Hurt wrote:

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

Use interscript!

http://interscript.sourceforge.net

Here is some code:

------
@set_title('Extlib Performance')
@head(1,'Operation costs')
Here is a performance table for
various data structures
@p()
@begin_table('oper','list','array''hash')
@table_row('append','O(1)','O(N)','N/A')
@table_row('prepend','O(1)','O(N)','N/A')
@table_row('magicr','O(1)','O(N)','O(1)')
@end_table()
@p()
--------------

This input can be used to simultaneously
generate HTML (in two formats), LaTeX, Lout,
and plain text (and even nroff if someone
would care to write an nroff weaver).

BTW: the stuff after the @ sign is not
magical interscript stuff. No,
it is any Python code you want to write
(the functions such as 'begin_table' are just part of the
standard library).

This implies you can generate documentation easily
with Python script. Indeed, you can generate
code too (since its actually a literate programming
tool).

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

Re: [Ocaml-lib-devel] some proposals

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

On Fri, 23 May 2003, Nicolas Cannasse wrote:

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

You're right.  Need a typecast:

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



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

Actually, handling the corner cases is a good argument, IMHO, *FOR* adding 
class Int.  This strikes me as being a common error.

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

Allocating the option blocks doesn't worry me much.  I assumed that we 
wanted to a) avoid allocating an unnecessary interim list, and b) wanted 
to construct the list forwards, as opposed to doing a List.rev.  If either 
of these are relaxed, then yes, the function can be fairly easily 
implemented given existing functions.

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

I forgot about this trick.  This is a better implementation.

Brian

Re: [Ocaml-lib-devel] Re: ExtList / Enum updates

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

> > Enum - added :
> >     val filter_map : ('a -> 'b option) -> 'a t -> 'b t
> >     val clone : 'a t -> 'a t
> 
> Is there a reason why Enum.filter is not implemented using Enum.from?
> 
> As in:
> 
> let filter f t =
>     let rec next () =
>         let x = t.next() in
>         if f x then x else next()
>     in
>     from next

Historical reasons. filter was defined before from.
I will update the sources, thanks for the report.

Nicolas Cannasse

[Ocaml-lib-devel] Re: ExtList / Enum updates

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

In article <014501c320d5$657a69b0$2713f9ca@WARP>, Nicolas Cannasse wrote:
> 
> Enum - added :
>     val filter_map : ('a -> 'b option) -> 'a t -> 'b t
>     val clone : 'a t -> 'a t

Is there a reason why Enum.filter is not implemented using Enum.from?

As in:

let filter f t =
    let rec next () =
        let x = t.next() in
        if f x then x else next()
    in
    from next

Re: [Ocaml-lib-devel] some proposals

[<Ala...@en...>]

On Thu, 22 May 2003, Brian Hurt wrote:

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

No for the current OCaml release, yes for the next one... Xavier
implemented strength reduction for Pervasives.compare (which means it will
be specialized for all integers types, floats, strings).

See:
http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/ocaml/bytecomp/translcore.ml.diff?r1=1.87&r2=1.88&f=h
http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/ocaml/byterun/ints.c.diff?r1=1.38&r2=1.39&f=h


        Objective Caml version 3.06+34 (2003-05-21)

# let f (x:int) y = compare x y;;
        closure L1, 0
        push
        acc 0
        push
        const "f"
        push
        getglobal Toploop!
        getfield 1
        appterm 2, 4
        restart
L1:     grab 1
        acc 1
        push
        acc 1
        ccall int_compare, 2
        return 2




-- Alain