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