ocaml-lib-devel

[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

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

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

Hello everyone.  Sorry for the silence- I had a cold.

On Wed, 26 Feb 2003, Michal Moskal wrote:

> On Wed, Feb 26, 2003 at 11:01:04AM +0900, Nicolas Cannasse wrote:
> >  val copy : 'a t -> 'a t -> unit
> 
> Ordering of arguments is copy dst src? I thought copy src dst, but...

This is one of those things which, IMHO, should be standardized- all 
library functions do it the same way.  I can see it woring either way:
copy src1 src2 src3 ... dst
copy dst src1 src2 src3 ...
both work.  I just want to pick *one* and stick with it.

Brian

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

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