> It would be great to know of a completely general (any
> nested structures) and fast solution (without copying)
> how to produce unshared data structures.

 If you like to play with fire you can use this unsharing function
 (that is not complete with respect to any data type, but it is sufficient
 for my needs). Since it works on the run-time representation of data,
 it can even unshare abstract data types.

exception CanNotUnshare;;

(* [unshare t] gives back a copy of t where all sharing has been removed   *)
(* Physical equality becomes meaningful on unshared terms. Hashtables that *)
(* use physical equality can now be used to associate information to evey  *)
(* node of the term.                                                       *)
val unshare: ?already_unshared:('a -> bool) -> 'a -> 'a

let unshare ?(already_unshared = function _ -> false) t =
 let obj = Obj.repr t in
  let rec aux obj =
   if already_unshared (Obj.obj obj) then
    obj
   else
    (if Obj.is_int obj then
      obj
     else if Obj.is_block obj then
      begin
       let tag = Obj.tag obj in
        if tag < Obj.no_scan_tag then
         begin
          let size = Obj.size obj in
           let new_obj = Obj.new_block 0 size in
            Obj.set_tag new_obj tag ;
            for i = 0 to size - 1 do
             Obj.set_field new_obj i (aux (Obj.field obj i))
            done ;
            new_obj
         end
        else if tag = Obj.string_tag then
         obj
        else
         raise CanNotUnshare
      end
     else
      raise CanNotUnshare
    )
  in
   Obj.obj (aux obj)
;;

-- 
----------------------------------------------------------------
Real name: Claudio Sacerdoti Coen
Doctor in Computer Science, University of Bologna
E-mail: sacerdot@cs.unibo.it
http://www.cs.unibo.it/~sacerdot
----------------------------------------------------------------