ocaml-lib-devel — Developer's mailing list

Re: [Ocaml-lib-devel] Exceptions and Complexity

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

> I entirely agree with you... Yet my concern is that because the code we
> include in the ext-lib uses *a different* convention for the semantics
> attached to the use of extensions,  the OCaml team may have a harder
> time when deciding whether to include them or not in the stdlib. But
> then, maybe we can "suggest" them what a nice thing would be to start
> including more meaningful exceptions into the stdlib!

As said before, I doubt that the extlib will be one day integrated into the
OCaml Stdlib... so I would prefer to have the "le's create another StdLib
with more functions" as goal for the ExtLib.

> BTW, if I were an active OCaml implementor, I'd be "eavesdropping" into
> this list so see how things went around here... So although the list's
> recipients are "non-disclosed", and I don't remember any of them
> answering to the list, I guess they are in fact following the progress
> of this thing just in case... Can I "cry to the void" and ask if anybody
> from the implementor's list is around just to be aware of it?

There is, there is.
Maxence, although not a member of the "Great Ocaml Fathers", is working at
INRIA and as been writting several great tools, ocamldoc among all (
although I dislike the usage of classes :-P )

Nicolas Cannasse

Re: [Ocaml-lib-devel] candidate functions

[fva <fv...@ts...>]

Eric C. Cooper wrote:

>Here are the functions (primarily extensions to List and String) that
>I find myself re-using.  The set-theoretic and combinatoric ones are
>probably too simplistic for general use, but I'll throw them out there
>for discussion.
>  
>
How would you go about packaging these in the extlib so that they can be 
more or less seamlessly integrated with the stdlib. A single overarching 
file-module?

Regards,

        Fran Valverde

Re: [Ocaml-lib-devel] Exceptions and Complexity

[fva <fv...@ts...>]

Nicolas Cannasse wrote:

>Hi,
>
>I've read all the comments about MutableList modules, and several important
>points have been raised.
>Thanks to all people who have replied !
>
>- yes, MList was intended as a additionnal module
>- of course, for end users, a fully documented module will be released
>- in the documentation, we can put some note about implementation, saying
>that  MList.t = list ref ( this clarify most of the questions )
>
IMHO this is like an invitation to tinkering! X)

(This paragraph is rather like (*my*) "philosophy of using modules to 
implement ADTs", and *not* my view of how should things that go into the 
extlib be packaged). IMO, the whole purpose of making signatures 
evident, then characterising structures in terms of the complexity of 
the operations/functions, is to make the data abstract yet let users 
have a feeling about their performance... Telling the core of the 
implementation (the main data type for the ADT) is adding information 
that is *not needed* to use the type, and I would *vote against* it. (It 
is very handy, though if the user wants to improve the code... In which 
case he will probably go down to the source itself, however).

>- yes using labels for "copy" make sense
>- map_list : ('a -> 'b) -> 'a t -> 'b list  is approved
>- shuffle simply do shuffle the list in-place. ( that's a random sort, so it
>is O(n²) )
>
>About Complexity, I think this has of course be part of the documentation :
>- copy and copy-list are O(1)
>- length is O(n)
>- set and remove_at_index are O(n)
>
OK. About all the above.

>About Exceptions, let me disagree with the current standard library model.
>Of couse, for many functions not-so-much-used a Failure "msg" is a very good
>way of raising an exception. But when you're using data structures such as
>lists, catching an exception is a very common way of handling different
>cases, so exception cannot be seen anymore as an error message, but as a
>possible kind of return value, so has to have a named constructor.
>
>most of the time when using the stdlib I end up using pattern matching to
>catch only one kind of failure :
>
>try
>    let h = List.hd l in
>    < do something with it >
>with
>    Failure "hd" ->
>        < handle it >
>
>Imagine that List.find would raise Failure "find" instead of Not_found...
>That wouldn't be nice... Why ? because we catch Not_found many times, that's
>why a separate constructor has been created. I don't really interstand
>caml-team Failure usage in the stdlib because it's so "old-style" and
>"weakly-typed" ( you can for example make a syntax error in the error
>message... ). For me, Failure exceptions are the one which are designed to
>be raised up to the toplevel... and printed. When you have an exception
>which is worth catching, you have to define a constructor. And several
>constructors are making your code much easier to debug.
>
I entirely agree with you... Yet my concern is that because the code we 
include in the ext-lib uses *a different* convention for the semantics 
attached to the use of extensions,  the OCaml team may have a harder 
time when deciding whether to include them or not in the stdlib. But 
then, maybe we can "suggest" them what a nice thing would be to start 
including more meaningful exceptions into the stdlib!

BTW, if I were an active OCaml implementor, I'd be "eavesdropping" into 
this list so see how things went around here... So although the list's 
recipients are "non-disclosed", and I don't remember any of them 
answering to the list, I guess they are in fact following the progress 
of this thing just in case... Can I "cry to the void" and ask if anybody 
from the implementor's list is around just to be aware of it?

Regards,

        Fran Valverde

Re: [Ocaml-lib-devel] Exceptions and Complexity

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

On Thu, Feb 27, 2003 at 12:06:27PM +0900, Nicolas Cannasse wrote:
> Hi,
> 
> I've read all the comments about MutableList modules, and several important
> points have been raised.
> Thanks to all people who have replied !
> 
> - yes, MList was intended as a additionnal module
> - of course, for end users, a fully documented module will be released
> - in the documentation, we can put some note about implementation, saying
> that  MList.t = list ref ( this clarify most of the questions )

So maybe you could extend Stack module? New module with overlapping
functionality probably isn't going to be added to OCaml stdlib.

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

[Ocaml-lib-devel] Exceptions and Complexity

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

Hi,

I've read all the comments about MutableList modules, and several importa=
nt
points have been raised.
Thanks to all people who have replied !

- yes, MList was intended as a additionnal module
- of course, for end users, a fully documented module will be released
- in the documentation, we can put some note about implementation, saying
that  MList.t =3D list ref ( this clarify most of the questions )
- yes using labels for "copy" make sense
- map_list : ('a -> 'b) -> 'a t -> 'b list  is approved
- shuffle simply do shuffle the list in-place. ( that's a random sort, so=
 it
is O(n=B2) )

About Complexity, I think this has of course be part of the documentation=
 :
- copy and copy-list are O(1)
- length is O(n)
- set and remove_at_index are O(n)

About Exceptions, let me disagree with the current standard library model=
.
Of couse, for many functions not-so-much-used a Failure "msg" is a very g=
ood
way of raising an exception. But when you're using data structures such a=
s
lists, catching an exception is a very common way of handling different
cases, so exception cannot be seen anymore as an error message, but as a
possible kind of return value, so has to have a named constructor.

most of the time when using the stdlib I end up using pattern matching to
catch only one kind of failure :

try
    let h =3D List.hd l in
    < do something with it >
with
    Failure "hd" ->
        < handle it >

Imagine that List.find would raise Failure "find" instead of Not_found...
That wouldn't be nice... Why ? because we catch Not_found many times, tha=
t's
why a separate constructor has been created. I don't really interstand
caml-team Failure usage in the stdlib because it's so "old-style" and
"weakly-typed" ( you can for example make a syntax error in the error
message... ). For me, Failure exceptions are the one which are designed t=
o
be raised up to the toplevel... and printed. When you have an exception
which is worth catching, you have to define a constructor. And several
constructors are making your code much easier to debug.

Nicolas Cannasse

Re: [Ocaml-lib-devel] candidate functions

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

On Wed, Feb 26, 2003 at 11:38:47AM -0500, Eric C. Cooper wrote:
> (* Invoke (f ()) n times, for side effects. *)
> 
> val repeat : int -> (unit -> unit) -> unit
> 
> (* Apply f to 0 .. n-1, for side effects. *)
> 
> val dotimes : int -> (int -> unit) -> unit

I belive for loop is more readable:

  repeat 20 f == for i = 1 to 20 do f () done
  dotimes 20 f == for i = 0 to 19 do f i done

and gives more possiblities.

Don't have strong opinions about other stuff here.

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] Mutable List

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

On Wed, Feb 26, 2003 at 06:07:20PM +0100, fva wrote:
> 1) If your submission was intended as a candidate module, I guess that 
> it should come along with at least documentation for the signature 
> primitives... 

I guess this was the idea. In fact I figured out sementics of all
functions in a minute or two, I just wonder about complexities.


-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] candidate functions

[Luc M. <Luc...@cv...>]

Perhaps it's a dummy question but why List.create doesn't exist ?

module AdvancedList =
  struct
    let create n v =
      let rec create_aux l n v =
	match n with 
	  | 0 -> l
	  | _ -> (create_aux (v::l) (n-1) v)
      in create_aux [] n v;;

    let rec create_with_fun f n =
      match n with 
	| 0 -> []
	| _ -> f() :: (create_with_fun f (n - 1));;

  end

-- 
Luc...@cv...
	

Re: [Ocaml-lib-devel] Mutable List

[fva <fv...@ts...>]

Nicolas Cannasse wrote:

>Hi ext-list,
>
>Here's my mutable list interface.
>Implementation is available and mostly use the standard List library
>function.
>
So this is a candidate for a new module for the ext-lib, *not* an 
extension for a particular lib in StdLib?

>Mutable lists with in place modifications are very usable each time you were
>previously using "list ref"
>
>I'm not putting any documentation with the interface, since every not
>obvious function can be considered as to be removed or changed.
>It also provide a set of functions based on item index in the list ( i'm
>using this, but i'm not really sure it should be in the ExtLib MList... or
>perhaps in an inner module )
>
>I'm waiting for your comments.
>
I will try to be constructive and please do not be fooled by typed 
language... It is very difficult to convey constructive criticism:

1) If your submission was intended as a candidate module, I guess that 
it should come along with at least documentation for the signature 
primitives... This is the minimal documentation to show people how to 
use your module... (I know it's a pain in the neck... I'm only concerned 
that nobody would take the trouble of using it. Even though it's in the 
*super-magnificent* :) ext-lib.

2) If it was intended as an implementation for lists but with mutable 
characteristics...
    a) Why not make the connection more evident in the code?
    b) Why didn't you characterize the complexity of the functions (I 
guess this is what Moskal did with the
        questions he put to you)

If the answer to both question is "because it was just an example", may 
I suggest that we *encourage* people submitting either:

a) signatures: to state the purpose & conventions of the functions 
(preferrably in Ocamldoc, but *any* documentation would feel OK with me)

b) or implementations: to be articulate as to the running complexities 
expected of the implementations in either of two ways:
    a) this function runs in O(whatever)...
    b) I haven't worked our or tested the complexity...

Because I think this would improve *any* code's usability *enormously*.

This could be done incrementally and cooperatively with users & such 
afterwards, but the original author should submit as much information as 
he is able about the "creature".

Regards,

        Fran Valverde

PS: On the technical aspect, yes, I would also try to mimic Stdlib' s 
way of using exceptions (like very few and overloaded so as to ease 
their percolation to the main library). F.

>
>Nicolas Cannasse
>
>-------------------------------------------------------------------
>
>exception Invalid_index of int
>exception No_such_element
>
>module MList :
>  sig
> type 'a t
>
> val empty : unit -> 'a t
> val isempty : 'a t -> bool
>
> val copy : 'a t -> 'a t -> unit
> val copy_list : 'a t -> 'a list -> unit
> val from_list : 'a list -> 'a t
> val to_list : 'a t -> 'a list
>
> val add : 'a t -> 'a -> unit
> val push : 'a t -> 'a -> unit
> val pop : 'a t -> 'a (* raise No_such_element *)
> val last : 'a t -> 'a (* raise No_such_element *)
> val first : 'a t -> 'a (* raise No_such_element *)
> val npop : 'a t -> int -> 'a list (* raise No_such_element *)
> val clear : 'a t -> unit
> val length : 'a t -> int
> val add_sort : ('a -> 'a -> int) -> 'a t -> 'a -> unit
>
> val hd : 'a t -> 'a (* raise No_such_element *)
> val tl : 'a t -> 'a list (* raise No_such_element *)
> val iter : ('a -> unit) -> 'a t -> unit
> val find : ('a -> bool) -> 'a t -> 'a
> val find_ex : ('a -> bool) -> 'a t -> exn -> 'a
> val exists : ('a -> bool) -> 'a t -> bool
> val map : ('a -> 'b) -> 'a t -> 'b list
> val sort : ('a -> 'a -> int) -> 'a t -> unit
> val filter : ('a -> bool) -> 'a t -> unit
>
> val shuffle : 'a t -> unit
>
> val remove : 'a t -> 'a -> unit (* only one element removed, tested with
>( = ), raise Not_found *)
> val remove_if : ('a -> bool) -> 'a t -> unit
>
>(* indexes functions *)
>
> val index_of : 'a t -> 'a -> int (* raise Not_found *)
> val at_index : 'a t -> int -> 'a (* raise Invalid_index *)
> val index_of_with : ('a -> bool) -> 'a t -> int (* raise Not_found *)
>
> val set : 'a t -> int -> 'a -> unit (* raise Invalid_index *)
> val remove_at_index : 'a t -> int -> unit (* raise Invalid_index *)
>
>end
>  
>

[Ocaml-lib-devel] candidate functions

[Eric C. C. <ec...@cm...>]

Here are the functions (primarily extensions to List and String) that
I find myself re-using.  The set-theoretic and combinatoric ones are
probably too simplistic for general use, but I'll throw them out there
for discussion.

-- 
Eric C. Cooper          e c c @ c m u . e d u

----
(*
 * Additions to the List module.
 *)

(* Generate the range of integers [a; a+1; ...; b] *)

val range : int * int -> int list

(* List equivalent of Array.init *)

val listi : int -> (int -> 'a) -> 'a list

(* List equivalent of Array.mapi *)

val mapi : (int -> 'a -> 'b) -> 'a list -> 'b list

(* List equivalent of Array.iteri *)

val iteri : (int -> 'a -> unit) -> 'a list -> unit

(* Reverse assoc *)
(* can also add rassq, mem_rassoc/rassq, remove_rassoc/rassq if needed *)

val rassoc : 'b -> ('a * 'b) list -> 'a

(* Tail-recursively compute rev (map f list1) @ list2 *)

val rev_map_append : ('a -> 'b) -> 'a list -> 'b list -> 'b list

(* Split [x1; x2; ...; xN] into [x1; ...; x{n}] and [x{n+1}; ...; xN] *)

val split_nth : int -> 'a list -> 'a list * 'a list

(* Tail-recursively split [x1; x2; ...; xN] into
   [x{n}; ...; x1] and [x{n+1}; ...; xN] *)

val rev_split_nth : int -> 'a list -> 'a list * 'a list

(* Return the last element of a list. *)

val last : 'a list -> 'a

(* Insert x at position n in list.
   Position 0 places x at the front;
   position (length list) places x at the end. *)

val insert : 'a -> int -> 'a list -> 'a list

(* Remove first occurrence of x, if any, from list. *)

val remove_first : 'a -> 'a list -> 'a list

(* Remove all occurrences of x from list. *)

val remove : 'a -> 'a list -> 'a list

(* Remove a subset of elements from a list. *)

val remove_subset : 'a list -> 'a list -> 'a list

(* Rotate each element of a list to the left,
   so that the head becomes the last element. *)

val rotate_left : 'a list -> 'a list

(* Homogeneous version of List.fold_left.
   Uses the head of the list as the initial value. *)

val fold : ('a -> 'a -> 'a) -> 'a list -> 'a

(* Test whether the first list is a subset of the second. *)

val subset : 'a list -> 'a list -> bool

(* Return cartesian product of two lists. *)

val product : 'a list -> 'b list -> ('a * 'b) list

(* Return all sublists of a list. *)

val subsets : 'a list -> 'a list list

(* Return all n-element sublists of a list. *)

val choose : int -> 'a list -> 'a list list

(* Return all sublists with up to n elements. *)

val choose_up_to : int -> 'a list -> 'a list list

(* Remove duplicates from a sorted list,
   using a sort-style comparison function that returns 0 for equality. *)

val uniq : ('a -> 'a -> int) -> 'a list -> 'a list

(*
 * Additions to the String module.
 *)

(* String equivalents of Array.fold_left and Array.fold_right *)

val string_fold_left : ('a -> char -> 'a) -> 'a -> string -> 'a
val string_fold_right : (char -> 'a -> 'a) -> 'a -> string -> 'a

(* Convert between strings and lists of chars. *)

val explode : string -> char list
val implode : char list -> string

(* Convert between strings and lists of ints in the range 0 .. 255 *)

val explode_bytes : string -> int list
val implode_bytes : int list -> string

(* Like [index_from] but searches at most [len] chars. *)
(* can also add bounded_rindex if needed *)

val bounded_index : string -> pos:int -> len:int -> char -> int

(*
 * Miscellaneous control structures.
 *)

(* Compute f (g x) *)
(* It would be nice to have a standard infix operator for this. *)

val compose : ('b -> 'c) -> ('a -> 'b) -> 'a -> 'c

(* Compute f^n x *)

val iterate : ('a -> 'a) -> int -> 'a -> 'a

(* Invoke (f ()) n times, for side effects. *)

val repeat : int -> (unit -> unit) -> unit

(* Apply f to 0 .. n-1, for side effects. *)

val dotimes : int -> (int -> unit) -> unit

Re: [Ocaml-lib-devel] Mutable List

[Eric C. C. <ec...@cm...>]

On Wed, Feb 26, 2003 at 11:09:54AM +0100, Michal Moskal wrote:
> Ordering of arguments is copy dst src? I thought copy src dst, but...
> 
> >  val copy_list : 'a t -> 'a list -> unit
> 
> ...this made me think right.
> 
> Maybe assign instead of copy would be better? It suggests the right
> ordering of arguments. And I know each function here takes argument it
> operates as first argument, so this shouldn't be hard to remember.

This is a good case for
  copy ~src: x ~dst: y

(remembering strcpy, bcopy, memcpy, ... in C)

-- 
Eric C. Cooper          e c c @ c m u . e d u

Re: [Ocaml-lib-devel] Mutable List

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

On Wed, Feb 26, 2003 at 11:01:04AM +0900, Nicolas Cannasse wrote:
> exception Invalid_index of int
> exception No_such_element

Maybe Invalid_argument "..." or Failure "..." would be better for 
both? IMHO this is more in style of existing ocaml std library.

> module MList :
>   sig
>  type 'a t
> 
>  val empty : unit -> 'a t
>  val isempty : 'a t -> bool
> 
>  val copy : 'a t -> 'a t -> unit

Ordering of arguments is copy dst src? I thought copy src dst, but...

>  val copy_list : 'a t -> 'a list -> unit

...this made me think right.

Maybe assign instead of copy would be better? It suggests the right
ordering of arguments. And I know each function here takes argument it
operates as first argument, so this shouldn't be hard to remember.

And one more Q : is copy constant time operation?

>  val from_list : 'a list -> 'a t
>  val to_list : 'a t -> 'a list
> 
>  val add : 'a t -> 'a -> unit

At front or at end? I belive both versions should be available (i.e.
list should be cyclic), since it doesn't give much overhead and gives
more possiblities. If only pop/push are supported, why not use Stack
module from std library?

>  val push : 'a t -> 'a -> unit
>  val pop : 'a t -> 'a (* raise No_such_element *)

>  val last : 'a t -> 'a (* raise No_such_element *)
>  val first : 'a t -> 'a (* raise No_such_element *)
>  val npop : 'a t -> int -> 'a list (* raise No_such_element *)
>  val clear : 'a t -> unit
>  val length : 'a t -> int

Is this constant time operation?

>  val add_sort : ('a -> 'a -> int) -> 'a t -> 'a -> unit
> 
>  val hd : 'a t -> 'a (* raise No_such_element *)
>  val tl : 'a t -> 'a list (* raise No_such_element *)

If other internal representation then 'a list is used this will have to
be O(n) operation, so I doubt it's good idea to provide it.

>  val iter : ('a -> unit) -> 'a t -> unit
>  val find : ('a -> bool) -> 'a t -> 'a
>  val find_ex : ('a -> bool) -> 'a t -> exn -> 'a
>  val exists : ('a -> bool) -> 'a t -> bool
>  val map : ('a -> 'b) -> 'a t -> 'b list

val map : ('a -> 'b) -> 'a t -> 'b t
val map_list : ('a -> 'b) -> 'a t -> 'b list 

?

>  val sort : ('a -> 'a -> int) -> 'a t -> unit
>  val filter : ('a -> bool) -> 'a t -> unit
> 
>  val shuffle : 'a t -> unit

Hmm? What's that?

> 
>  val remove : 'a t -> 'a -> unit (* only one element removed, tested with
> ( = ), raise Not_found *)
>  val remove_if : ('a -> bool) -> 'a t -> unit
> 
> (* indexes functions *)
> 
>  val index_of : 'a t -> 'a -> int (* raise Not_found *)
>  val at_index : 'a t -> int -> 'a (* raise Invalid_index *)
>  val index_of_with : ('a -> bool) -> 'a t -> int (* raise Not_found *)
> 
>  val set : 'a t -> int -> 'a -> unit (* raise Invalid_index *)

set x n y takes O(n)?

>  val remove_at_index : 'a t -> int -> unit (* raise Invalid_index *)

Ditto?

-- 
: Michal Moskal ::::: malekith/at/pld-linux.org :  GCS {C,UL}++++$ a? !tv
: PLD Linux ::::::: Wroclaw University, CS Dept :  {E-,w}-- {b++,e}>+++ h

Re: [Ocaml-lib-devel] Ocaml indent?

[Stefano Z. <za...@bo...>]

On Tue, Feb 25, 2003 at 02:39:39PM -0500, Manos Renieris wrote:
> Now, for the level of the library, what I see for the first
> phase is (I think) very close to Stefano's:

If you like I can sent you on the list (to which I'm _not_ subscribed)
the set of functions I've collected that I would like to see in the
ocaml standard library.

Cheers.

-- 
Stefano Zacchiroli  -  Undergraduate Student of CS @ Uni. Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it}  -  http://www.bononia.it/zack/
"  I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!  " -- G.Romney

Re: [Ocaml-lib-devel] Ocaml indent?

[fva <fv...@ts...>]

John Max Skaller wrote:

>
>> My general philosophy on labels is that they should only be used when 
>> there is a real good reason to use them.  What a 'real good reason' 
>> is I'm still working on.
>
>
>
> Good reason (1) is obvious: there are a LOT of arguments.
>
> Good reason (2) might be: there are several arguments of the same
>
> type and no natural order the programmer might guess at, or,
> the chosen order differs from the C function it is wrapping.
>
> Good reason (3) is related to both: there are many arguments
> and some are optional (so labels are necessary to invoke
> the defaults).
>
> Another less good reason is: there are enough arguments
> and lack of natural ordering, and the client is
> likely to want to curry the function with subsets
> of the arguments, perhaps multiple times. 

All seem to me good enough reasons. Shall we push it as a recommendation 
for contributions?

But remember that some Standardlib functions come in two guises now: 
labelled and unlabelled.

Regards.

        Fran Valverde

Re: [Ocaml-lib-devel] Ocaml indent?

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

 
> My general philosophy on labels is that they should only be used when 
> there is a real good reason to use them.  What a 'real good reason' is I'm 
> still working on.


Good reason (1) is obvious: there are a LOT of arguments.

Good reason (2) might be: there are several arguments of the same

type and no natural order the programmer might guess at, or,
the chosen order differs from the C function it is wrapping.


An example might be:

Array.make count value

can be confused with

Array.make value count

without a type error if the array type is int array.

Good reason (3) is related to both: there are many arguments
and some are optional (so labels are necessary to invoke
the defaults).

Another less good reason is: there are enough arguments
and lack of natural ordering, and the client is
likely to want to curry the function with subsets
of the arguments, perhaps multiple times.


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

[Ocaml-lib-devel] Mutable List

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

Hi ext-list,

Here's my mutable list interface.
Implementation is available and mostly use the standard List library
function.
Mutable lists with in place modifications are very usable each time you were
previously using "list ref"

I'm not putting any documentation with the interface, since every not
obvious function can be considered as to be removed or changed.
It also provide a set of functions based on item index in the list ( i'm
using this, but i'm not really sure it should be in the ExtLib MList... or
perhaps in an inner module )

I'm waiting for your comments.

Nicolas Cannasse

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

exception Invalid_index of int
exception No_such_element

module MList :
  sig
 type 'a t

 val empty : unit -> 'a t
 val isempty : 'a t -> bool

 val copy : 'a t -> 'a t -> unit
 val copy_list : 'a t -> 'a list -> unit
 val from_list : 'a list -> 'a t
 val to_list : 'a t -> 'a list

 val add : 'a t -> 'a -> unit
 val push : 'a t -> 'a -> unit
 val pop : 'a t -> 'a (* raise No_such_element *)
 val last : 'a t -> 'a (* raise No_such_element *)
 val first : 'a t -> 'a (* raise No_such_element *)
 val npop : 'a t -> int -> 'a list (* raise No_such_element *)
 val clear : 'a t -> unit
 val length : 'a t -> int
 val add_sort : ('a -> 'a -> int) -> 'a t -> 'a -> unit

 val hd : 'a t -> 'a (* raise No_such_element *)
 val tl : 'a t -> 'a list (* raise No_such_element *)
 val iter : ('a -> unit) -> 'a t -> unit
 val find : ('a -> bool) -> 'a t -> 'a
 val find_ex : ('a -> bool) -> 'a t -> exn -> 'a
 val exists : ('a -> bool) -> 'a t -> bool
 val map : ('a -> 'b) -> 'a t -> 'b list
 val sort : ('a -> 'a -> int) -> 'a t -> unit
 val filter : ('a -> bool) -> 'a t -> unit

 val shuffle : 'a t -> unit

 val remove : 'a t -> 'a -> unit (* only one element removed, tested with
( = ), raise Not_found *)
 val remove_if : ('a -> bool) -> 'a t -> unit

(* indexes functions *)

 val index_of : 'a t -> 'a -> int (* raise Not_found *)
 val at_index : 'a t -> int -> 'a (* raise Invalid_index *)
 val index_of_with : ('a -> bool) -> 'a t -> int (* raise Not_found *)

 val set : 'a t -> int -> 'a -> unit (* raise Invalid_index *)
 val remove_at_index : 'a t -> int -> unit (* raise Invalid_index *)

end

[Ocaml-lib-devel] Compiling & Installing

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

Right now I see here some talks around about compilation and installation of
ExtLib.

I think that first we don't need to do such choice right now, and second
that there is no choice to be made !
We're here talking about ExtLib, that'll be perhaps in the beginning ten to
twenty files/modules with almost no inner depencies, all in the same
directory, all wriiten in Ocaml - with no C stubs. I think we can afford
making a source distribution with only a standard Makefile, and perhaps at
least a bytecode-binary version for the current version of Ocaml.

So please drop talks about Compiling and Installing tools. That discussion
is currently held about the COAN project on the official list and have
nothing to do with ExtLib.

Nicolas Cannasse

Re: [Ocaml-lib-devel] Ocaml indent?

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

> > The current goal is not to put every existing (although very used) ocaml
> > library into the ExtLib. For example PXP, which is a very good XML
parser -
> > and everybody is using XML in today applications - should remain a
separate
> > library. The ExtLib should remain somehow small :)
>
> Huge libraries- like GUI interface or 3D libraries- should be on their
> own.  But unless we're talking megabytes of library here, I'd perfer to
> download and install *one* library, not thirty.  And, IMHO, XML parsing is
> small enough and there are enough possible uses for it that I'd like it in
> the library.

Yes I agree,
It would be good to add ( later ) a very small Xml parser into the ExtLib.
But let's delay such choices a little bit more...

Nicolas Cannasse

Re: [Ocaml-lib-devel] Ocaml indent?

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

> >> For that, we already have a decomposition to follow, that of the
> >> standard library itself.  We need a name, a license, a compilation
> >> strategy, and an installation strategy.
> 
> I think we should be careful here. In my opinion Boost went entirely 
> off the rails by chosing a special make tool, and then modifying
> that so that to actually build boost became a total nightmare.
> 
> They failed to follow my recommendation:-)
> 
> I recommended Python script as the build tool, and they
> thought it was 'too heavy' which of course turned out
> to be a joke compared to having to download and build
> a custom tool -- which needed constant modification.
<snip>
> Well, we should probably use ocaml script instead :-)

That's Ocamake,
Thanks for your support John :)

Nicolas Cannasse

Re: [Ocaml-lib-devel] Ocaml indent?

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

> > What a pity when the type of a function (for example the order of
> > arguments) is *almost* what we need and we have to create a dummy
> > function, for example to change the order of the arguments...
> 
> How much of a problem is this?  I mean, to do:
> let foo x y = bar y x ;;
> strikes me as being seriously trivial.

Yes, but it really bothers me to define such functions in my code, because I must find a not conflicting and still meaningful name for these, or use
a function defined "on the fly".
Example :
I have a set module MySet (result of the Set.Make functor), containing the function
add :  elt -> t -> t

Now if I want to build a MySet.t from a list, I use fold_left like this :
  List.fold_left (fun set e -> MySet.add e set) MySet.empty my_list

I could have used 
  List.fold_right MySet.add my_list MySet.empty
but fold_right is not tail-recursive, so I think MySet.add should have the type
add : t -> elt -> t

In this case, I would not have to pollute my code with 
  (fun set e -> MySet.add e set)

You can say the workaround is trivial, but it happens quite often.

> A bigger problem for me is to make the arguments in a standard order.  One 
> thing that *always* annoys me in C is:
>     fprintf(stream, "string");
>     fputs("string", stream);
> 
> I'd much perfer to have a standard order for arguments, to make them 
> easier to remember.  For example, in data-structure oriented APIs, the 
> data structure to act upon/use should always be the first argument.  Etc.

I agree. 

> Having to look up the order of arguments every time you use the function 
> encourages programmers to not use the function.

I agree again.

-- 
Maxence Guesdon

Re: [Ocaml-lib-devel] Ocaml indent?

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

On Wed, 26 Feb 2003, John Max Skaller wrote:

> I personally DESPISE make and friends, I think they're
> total garbage. While they automate some tasks nicely,
> trying to fool make into doing all the build/test/install
> tasks correctly requires considerably expertise and hackery.

I have to agree with you there.  Plain make is nigh unto unusable, even 
for a small project (dozens of files).  Requiring gnu make helps, but 
doesn't solve the problem- for example, how do you write a rule that deals 
with yacc outputting both a foo.c and a foo.h, such that if either file 
needs to be rebuilt yacc is run, but if both files need to be rebuilt yacc 
is only run once?  I still haven't solved that one.  And I'm not sure it's 
solvable.

For the record, I also dislike ant.  If I was willing to forego partial 
recompilation and dependency checking, I'd write a fargin shell script.  

Brian

Re: [Ocaml-lib-devel] Ocaml indent?

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

On Tue, 25 Feb 2003, Nicolas Cannasse wrote:

> The current goal is not to put every existing (although very used) ocaml
> library into the ExtLib. For example PXP, which is a very good XML parser -
> and everybody is using XML in today applications - should remain a separate
> library. The ExtLib should remain somehow small :)
> 

I agree that having six different tree implementations- or even just six 
different map implementations- isn't usefull.  But one of the things I 
like about Java is it's (bloated, huge) libraries.  Yes, it makes Java 
have a footprint that would shock a brontosaurus, but it also makes Java 
programmers more likely to use the libraries that exist.  Why write your 
own (badly implemented and non-conformant) XML parser when you can just 
use the (well implemented and conformant) standard XML parser?  Why write 
your own configuration file parser when you can use XML?  Etc.

Huge libraries- like GUI interface or 3D libraries- should be on their 
own.  But unless we're talking megabytes of library here, I'd perfer to 
download and install *one* library, not thirty.  And, IMHO, XML parsing is 
small enough and there are enough possible uses for it that I'd like it in 
the library.

Note that the definition for inclusion shouldn't just be *current* uses, 
but also *potiential* uses were it everywhere.  Take XML for example- it 
probably isn't a bad format for configuration files, should an XML parser 
be handy.  It's almost certainly not worth it to write an XML file parser 
just to parse your configuration file, but if it was there, people would 
use it for that.

Brian

Re: [Ocaml-lib-devel] Re: [Caml-list] OCaml standard library improvement

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

On Tue, 25 Feb 2003, fva wrote:

> If what Zacchiroli is true (read the news article) we may be in for a 
> disappointment being hosted in SourceForge... Can anybody give further 
> news about this claim of relinquishing our rights & work for the benefit 
> of SourceForge if we are hosted with them?

I'd be as much or more concerned with 'political' interference at Savannah 
as I'd be at SourceForge.  This may come as a surprise, being that I am a 
big GPL fan, but several of RMS' moves recently scare me.  In addition to 
the whole lignux / gnu/linux thing, consider this as well:
http://slashdot.org/article.pl?sid=01/08/19/2039211&mode=nested

IMHO, Stallman has gotten a stick up his butt recently about being 
'forgotten' by the open/free source community.  As if that could happen.  
What I really think is happening is that he is not the only big figure 
anymore- the playing field has opened up, and lots more people have made 
names for themselves- Linus, Miguel, Xavier (hey, I can dream, can't I?), 
etc.

Not that SourceForge is beyond reproach by any strech of the imagination.  
I'd be much happier with a box controlled by someone known on this list.  
But as I don't have that box to offer, I haven't been offering an opinion.

Brian

Re: [Ocaml-lib-devel] Ocaml indent?

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

On Tue, 25 Feb 2003, Maxence Guesdon wrote:

> What a pity when the type of a function (for example the order of
> arguments) is *almost* what we need and we have to create a dummy
> function, for example to change the order of the arguments...

How much of a problem is this?  I mean, to do:
let foo x y = bar y x ;;
strikes me as being seriously trivial.

A bigger problem for me is to make the arguments in a standard order.  One 
thing that *always* annoys me in C is:
    fprintf(stream, "string");
    fputs("string", stream);

I'd much perfer to have a standard order for arguments, to make them 
easier to remember.  For example, in data-structure oriented APIs, the 
data structure to act upon/use should always be the first argument.  Etc.
Having to look up the order of arguments every time you use the function 
encourages programmers to not use the function.

Speaking of which- I came upon an issue writting my psqueue library.  For 
data structures that have uniqueness constraints (hashes, trees, etc) what 
happens when you add an element that is already there, or modify/remove an 
element that isn't there?  There are two sets of ideology on this that I 
know of:

- The "loose" philosophy- quietly do "the right thing".  Adding an element
(or key)  that already exists simply replaces the previous element(key).  
Removing or modifying a key that doesn't exist does nothing.  The belief 
here is that what the programmer meant, or what is likely to do the least 
damage, is obvious, and you shouldn't blow up the entire program when 
there is an obvious way to continue.

- The "strict" philosophy- throw an exception on these cases.  The 
programmer asked to do something "nonsensical" and should fix his program, 
rather than take the chance that the library will guess wrong what the 
correct behavior is.  And the sooner the library helps the programmer 
catch his mistake, the easier it is to fix.

My "solution" is to provide both and let the programmer pick which he
wants.  IIRC, I used add/remove for the loose versions, and insert/delete
for the strict versions.


> 
> BTW, what about labels ? with or without ? I vote for only optional labels,
> except for functions with plenty of arguments of the same type.

My general philosophy on labels is that they should only be used when 
there is a real good reason to use them.  What a 'real good reason' is I'm 
still working on.

Brian

Re: [Ocaml-lib-devel] Ocaml indent?

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

On Wed, Feb 26, 2003 at 04:38:15AM +1100, John Max Skaller wrote:
> >>For that, we already have a decomposition to follow, that of the
> >>standard library itself.  We need a name, a license, a compilation
> >>strategy, and an installation strategy.
> 
> I think we should be careful here. 

Indeed. I actually now think that we should not rely on anything
the ocaml core team does not rely on. Under unix, that means
ocaml and make. If they don't need python to install the ocaml
libraries, we don't need it for ExtLib either.

So, my proposal would be like this: we create a `ocamlc -where`/extlib
directory, with extlib.cm* files in it. To use extlib, 
you need to compile with +extlib extlib.cma. (Please
forgive my unixisms; if something will not work under
Windows, please free to suggest alternatives that will).

Now, for the level of the library, what I see for the first
phase is (I think) very close to Stefano's:
We need things like String.of_char and List.rev_combine.
It seems to me that the simplest way to get them is by writing
.ml files like this string.ml:

   include String
   let of_char = String.make 1

and .mli files that replicate the string.mli from the stdlib and
add the extensions of extlib. Then we just pack everything in
extlib.cma. The ocaml team can decide to move things for stdlib
to extlib (or the other way round) as they wish.

> In my opinion Boost went entirely
> off the rails by chosing a special make tool, and then modifying
> that so that to actually build boost became a total nightmare.
> 
> They failed to follow my recommendation:-)
> 
> I recommended Python script as the build tool, and they
> thought it was 'too heavy' which of course turned out
> to be a joke compared to having to download and build
> a custom tool -- which needed constant modification.
> 
> I personally DESPISE make and friends, I think they're
> total garbage. While they automate some tasks nicely,
> trying to fool make into doing all the build/test/install
> tasks correctly requires considerably expertise and hackery.
> 
> Python, on the other hand, is a full scale programming language.
> 
> Well, we should probably use ocaml script instead :-)
> 
> -- 
> John Max Skaller, mailto:sk...@oz...