Fw: [Caml-list] Missing a function

Fw: [Caml-list] Missing a function

[Frédéric Gava]

Hi,
>
> > Another option is to build on top of the stdlib Map functor another
> > functor that keeps track of the cardinal of a map :
> >
> > module CMap = functor (Ord : Map.OrderedType) ->
> >   (struct
> >     module M = Map.Make (Ord)
> >
> >     type key = M.key
> >     type 'a t = int * 'a M.t
> >
> >     let cardinal = fst
> >
> >     let empty = 0, M.empty
> >
> >     let add k v (n, m) = (n + 1, M.add k v m)
> >
> >     let find k (_, m) = M.find k m
> >
> > ....
> >    : sig
> >        include Map.S
> >        val cardinal : 'a t -> int
> >      end)
> >
Hum. To remove an element, you have to test is its exists or not before
decrease n. It could be to much cost expansive...no ?

Regards,
Frédéric Gava

Re: [Caml-list] Missing a function

[Olivier Andrieu]

 > Frédéric Gava [Sun, 30 Jan 2005]:
 > Hi,
 > >
 > > > Another option is to build on top of the stdlib Map functor another
 > > > functor that keeps track of the cardinal of a map :
 > > >
 > > > module CMap = functor (Ord : Map.OrderedType) ->
 > > >   (struct
 > > >     module M = Map.Make (Ord)
 > > >
 > > >     type key = M.key
 > > >     type 'a t = int * 'a M.t
 > > >
 > > >     let cardinal = fst
 > > >
 > > >     let empty = 0, M.empty
 > > >
 > > >     let add k v (n, m) = (n + 1, M.add k v m)
 > > >
 > > >     let find k (_, m) = M.find k m
 > > >
 > > > ....
 > > >    : sig
 > > >        include Map.S
 > > >        val cardinal : 'a t -> int
 > > >      end)
 > > >
 > Hum. To remove an element, you have to test is its exists or not
 > before decrease n. It could be to much cost expansive...no ?

Oh right. And a test is needed for `add' too since the cardinal will
not change if the key is already bound in the map. So, all in all it's
not a very good idea :)

-- 
   Olivier

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 29 Jan 2005 21:34:28 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> I do not have the ocaml sources handy right now but... Set and Map are
> probably RB-trees.

Map is not a RB-tree but a height balanced tree: HB(2). (haven't looked at Set)

BTW, what does the license say about reusing the code in map.ml?
Please use simple terms for people that don't like to deal with
administrative stuff. The ideal response would be: do it / don't do it
:)

(Now that I have read the code I would probably write it very
similarly even if I would not look at it any more...)

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Missing a function

[Olivier Andrieu]

 > Radu Grigore [Sat, 29 Jan 2005]:
 > On Sat, 4 Dec 2004 15:13:44 +0100, Frédéric Gava
 > <frederic.gava@wanadoo.fr> wrote:
 > 
 > > > let cardinal e = fold (fun _ _ x -> succ x) e 0;;
 > > [...] Map are also implemented as balanced
 > > tree (like sets) and therefore, it is easy to add a function of "cardinal".
 > 
 > I agree it's strange not to have "cardinal" in Map.Make. The
 > implementations of Set and Map are likely to be very similar anyway.

Another option is to build on top of the stdlib Map functor another
functor that keeps track of the cardinal of a map :

module CMap = functor (Ord : Map.OrderedType) ->
  (struct
    module M = Map.Make (Ord)
	
    type key = M.key
    type 'a t = int * 'a M.t

    let cardinal = fst

    let empty = 0, M.empty

    let add k v (n, m) = (n + 1, M.add k v m)

    let find k (_, m) = M.find k m
	  
	....
   : sig
       include Map.S
       val cardinal : 'a t -> int
     end)

-- 
   Olivier

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 29 Jan 2005 21:34:28 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> for Set the complexity [of cardinal] isn't specified. It is probably
> O(lg n).

Strike that :( I don't know what went in my mind. I should probably
make a habit of waiting 5min before pressing "send" :(

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Missing a function

[Radu Grigore]

On Sat, 4 Dec 2004 15:13:44 +0100, Frédéric Gava
<frederic.gava@wanadoo.fr> wrote:

> > let cardinal e = fold (fun _ _ x -> succ x) e 0;;
> [...] Map are also implemented as balanced
> tree (like sets) and therefore, it is easy to add a function of "cardinal".

I agree it's strange not to have "cardinal" in Map.Make. The
implementations of Set and Map are likely to be very similar anyway.

I do not have the ocaml sources handy right now but... Set and Map are
probably RB-trees. In this case there are at least 2 pointers for
links (left and right children),  one pointer for key and, for maps,
one pointer for data.  So a set of N elements occupies at least 12xN
bytes, while a map occupies at least 16xN bytes. If an element counter
is added then the sizes would increase to 16xN and 20xN. That doesn't
seem too bad. The advantages would be:

a. O(1) cardinal function. Right now for Map the user can implement a
O(n) one and for Set the complexity isn't specified. It is probably
O(lg n).

b. O(lg n) indexed access.

Such a change implies minimal modification of existing functions:
Set.cardinal becomes faster (if my guess -- lg n -- was correct) and
add/remove will be _slightly_ slower. The advantage would be
Map.cardinal and indexed access.

-- 
regards,
 radu
http://rgrig.idilis.ro/

Re: [Caml-list] Missing a function

[Frédéric Gava]

> > I have done a comparaison on three data structures of the stdlib of
OCaml (I
> > do parallel implementation of this data structure) and I find that the
> > module Map does not contain any function for counting the number of
elements
> > of the data structure:
> >    Set, cardinal: t -> int
> >    Hashtbl,  lenght : ('a,'b) t -> int
> >    Map,    you have to do   "let length the_map = fold (fun _ _ i ->
i+1)
> > the_map 0 "
> > And Set and Hastbl have also fold...
> > Is there an explanation (or is it just a missing ;-) ) ?
>
> There is a 'fold' function in functor Make.
> val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
> so :
> let cardinal e = fold (fun _ _ x -> succ x) e 0;;

Hi,

> >    Map,    you have to do   "let length the_map = fold (fun _ _ i ->
i+1)
> let cardinal e = fold (fun _ _ x -> succ x) e 0;;

Ok. That is the same things (except the name) that I have written  in  my
mail... but this method is not very efficient because you apply many time
a function without using its arguments. Map are also implemented as balanced
tree (like sets) and therefore, it is easy to add a function of "cardinal".

Cheers,
Frédéric Gava

Re: [Caml-list] Missing a function

[sejourne_kevin]

Frédéric Gava wrote:
> Hi,
> 
> I have done a comparaison on three data structures of the stdlib of OCaml (I
> do parallel implementation of this data structure) and I find that the
> module Map does not contain any function for counting the number of elements
> of the data structure:
>    Set, cardinal: t -> int
>    Hashtbl,  lenght : ('a,'b) t -> int
>    Map,    you have to do   "let length the_map = fold (fun _ _ i -> i+1)
> the_map 0 "
> 
> And Set and Hastbl have also fold...
> 
> Is there an explanation (or is it just a missing ;-) ) ?

There is a 'fold' function in functor Make.
val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

so :

let cardinal e = fold (fun _ _ x -> succ x) e 0;;