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

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

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

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

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

- added signature for some additonnal function proposals

## Joined modified file ##

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

Nicolas Cannasse