[Caml-list] sharing problem ...

[Caml-list] sharing problem ...

[Pietro Abate]

[-- Attachment #1: Type: text/plain, Size: 1652 bytes --]

Hi all,
I'm trying to implement a (string * set) hashtbl
where some element (set) should be shared between different
objects.
the main point is that when I clone an object I want to duplicate
some sets and shared others (sticky sets)

I tried to achieve this result with the method below.
it use the set_copy to duplicate a set and does nothing when then 
element is marked as "shared".

        method copy =
            let set_copy s =
                MySet.fold (
                    fun e s ->
                        MySet.add e s
                ) MySet.empty s
            in
            let map_copy m =
                MyMap.fold (
                    fun k (s,t) m ->
                        (* this one should be the same set *)
                        if t then MyMap.add k (s,t) m
                        (* this one should be a copy !! *)
                        else MyMap.add k (set_copy(s),t) m
                ) MyMap.empty m
        in {< sets = map_copy sets >}

Of course this is not the right way of doing it as the map with key "a"
(in the small example attached) is not shared at all...
this is the result I'd like to get:

a1: 
a(shared) : [1;2;3;]
b:[1;2;3;]

a2: 
a(shared) : [1;2;3;4;5;]
b:[1;2;3;4;5;]

a1: 
a(shared) : [1;2;3;4;5]            <---------------here !!!
b:[1;2;3;]


how can I efficiently share elements in this kind of structure ?

p

-- 
++ Our capacity for understanding is inversely proportional to 
   how much we think we know. The more I know, the more I know 
   I don't know...
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html

[-- Attachment #2: htest.ml --]
[-- Type: text/plain, Size: 2409 bytes --]



module MyMap = Map.Make(
    struct
        type t = string
        let compare = compare 
    end)

module MySet = Set.Make(
    struct
        type t = int
        let compare = compare
    end)


class mystruct l =
    object(self)
        initializer List.iter (fun (h,s) -> self#add_name ~t:s h ) l
        
        val mutable sets = MyMap.empty

        method add_name ?(t=false) name=
            if not(MyMap.mem name sets) then
                sets <- MyMap.add name (MySet.empty,t) sets
            else ()
        
        method clone = {< sets = sets >}

        method copy =
            let set_copy s =
                MySet.fold (
                    fun e s ->
                        MySet.add e s
                ) MySet.empty s
            in
            let map_copy m =
                MyMap.fold (
                    fun k (s,t) m ->
                        if t then MyMap.add k (s,t) m
                        else MyMap.add k (set_copy(s),t) m
                ) MyMap.empty m
        in {< sets = map_copy sets >}

        method add_elem name tl =
            try
                let (set,t) = MyMap.find name sets in
                let set' =
                    List.fold_left (
                        fun s t -> MySet.add t s
                    ) set tl
                in
                sets <- MyMap.remove name sets;
                sets <- MyMap.add name (set',t) sets
            with Not_found ->
                Printf.printf "%s : " name;
                failwith "My not declared"

        method print =
            MyMap.iter (
                fun k (s,t) ->
                    print_string k ;
                    if t then print_string "(shared) : "
                    else  print_string ":";
                    print_string "[";
                    MySet.iter (
                        fun e ->
                            print_int e; 
                            print_string ";"
                    ) s;
                print_endline "]"
            ) sets

end

let a1 = new mystruct ["a",true;"b",false] ;;

let _ =
    a1#add_elem "a" [1;2;3];
    a1#add_elem "b" [1;2;3];
    print_endline "a1: ";
    a1#print;
    print_newline ();;

let a2 = a1#copy;;

let _ =
    a2#add_elem "a" [4;5];
    a2#add_elem "b" [4;5];
    print_endline "a2: ";
    a2#print;
    print_newline ();
    print_endline "a1: ";
    a1#print;
    print_newline ();;

Re: [Caml-list] sharing problem ...

[Nicolas Cannasse]

> Hi all,
> I'm trying to implement a (string * set) hashtbl
> where some element (set) should be shared between different
> objects.
> the main point is that when I clone an object I want to duplicate
> some sets and shared others (sticky sets)
>
> I tried to achieve this result with the method below.
> it use the set_copy to duplicate a set and does nothing when then
> element is marked as "shared".
[...]
>
> how can I efficiently share elements in this kind of structure ?

The main problem is that you're comparing the sets based on a structural
polymorphic equality (compare) while what you want/need is physical
comparison, which is of course faster and is the only way to detect shared
structures. Sadly, there is no :  phys_compare : 'a -> 'a -> int  in OCaml,
so you might use the following method :

Add an unique integer "id" to your set in a record, that will enable you to
maintain a hashtbl (or set) of shared structures based on integer comparison
between their id's. That's what OCaml is doing inside the compiler.

Regards,
Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] sharing problem ...

[Damien Doligez]

On Monday, January 26, 2004, at 11:43 AM, Pietro Abate wrote:

> I'm trying to implement a (string * set) hashtbl
> where some element (set) should be shared between different
> objects.
> the main point is that when I clone an object I want to duplicate
> some sets and shared others (sticky sets)

This doesn't make sense because your set type is built from the
standard library's Set module.  Thus your sets are purely applicative:
you cannot modify them with side-effects.

Shared or not, the elements of a1 will not change when you change
the elements of a2, because changing the elements of a2 doesn't
change the elements themselves, it only replaces them with new
elements (which are not shared, by definition).

That can be seen in your code:

                 sets <- MyMap.remove name sets;
                 sets <- MyMap.add name (set',t) sets

You don't change the shared set, you remove it from the map and then
add a new one under the same name.

If you really need mutable sets, maybe you should use the Hashtbl
module instead of Set.

-- Damien

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] sharing problem ...

[Pietro Abate]

[-- Attachment #1: Type: text/plain, Size: 784 bytes --]

Tnx for you comments. My example was wrong as Damien pointed out
because sets are immutable and I was using them in a very wrong way.
I got around the problem using an object with a mutable val. I don't
think this is the best solution but I couldn't figure out how to do it
with using simple records...

attacched there is the code snippet...

tnx.

p


On Mon, Jan 26, 2004 at 02:27:46PM +0100, Damien Doligez wrote:
> If you really need mutable sets, maybe you should use the Hashtbl
> module instead of Set.

-- 
++ Our capacity for understanding is inversely proportional to 
   how much we think we know. The more I know, the more I know 
   I don't know...
++ Please avoid sending me Word or PowerPoint attachments.
   See http://www.fsf.org/philosophy/no-word-attachments.html

[-- Attachment #2: htest1.ml --]
[-- Type: text/plain, Size: 2521 bytes --]



module MyMap = Map.Make(
    struct
        type t = string
        let compare = compare 
    end)

module MySet = Set.Make(
    struct
        type t = int
        let compare = compare
    end)

class set t =
    object
        val mutable value = MySet.empty
        val shared = t
        method shared = shared
        
        method copy = {<>}
            
        method add_list tl =
            value <-
                List.fold_left (
                    fun set term -> MySet.add term set
            ) value tl
            
        method print =
            if shared then print_string "(shared) : "
            else print_string ":";
            print_string "[";
            MySet.iter (
                fun e ->
                    print_int e;
                    print_string ";"
                ) value;
            print_endline "]"
    end
    
class mystruct l =
    object(self)
        initializer List.iter (fun (s,t) -> self#add_name ~t:t s ) l
        
        val mutable sets = MyMap.empty

        method add_name ?(t=false) name=
            if not(MyMap.mem name sets) then
                sets <- MyMap.add name (new set t) sets
            else ()
        
        method copy =
            let map_copy m =
                MyMap.fold (
                    fun k s m ->
                        if s#shared then MyMap.add k s m
                        else MyMap.add k s#copy m
                ) m MyMap.empty 
        in {< sets = map_copy (sets) >}

        method add_elem name tl =
            try
                let set = MyMap.find name sets in
                set#add_list tl;
                (* sets <- MyMap.remove name sets;
                sets <- MyMap.add name set sets *)
            with Not_found ->
                Printf.printf "%s : " name;
                failwith "My not declared"

        method print =
            MyMap.iter (
                fun k s ->
                    print_string k;
                    s#print
            ) sets

end

let a1 = new mystruct ["a",true;"b",false] ;;

let _ =
    a1#add_elem "a" [1;2;3];
    a1#add_elem "b" [1;2;3];
    print_endline "a1: ";
    a1#print;
    print_newline ();;

let a2 = a1#copy;;

let _ =
    a2#add_elem "a" [4;5];
    a2#add_elem "b" [4;5];
    print_endline "a2: ";
    a2#print;
    print_newline ();
    print_endline "a1: ";
    a1#print;
    print_newline ();
    a1#add_elem "a" [6];
    print_endline "a2: ";
    a2#print;
    print_endline "a1: ";
    a1#print;
    print_newline ();;