Re: Exchanging trees

[Vincent.Prunet@sophia.inria.fr (Vincent Prunet)]

=> How can I exchange two arbitrary subtrees of the same tree, i.e.
=> 
=> 	exchange-tree : TREE1, TREE2 -> WHATEVER
=> 
=> regardless of their relative position within the surrounding tree.
=> 
=> Annotations of both of the trees also have to be swapped around:
=> 
=> 
=> 	    /\ 		              /\
=>            /  \   exchangeex-tree    /  \
=> 	  /    \  --------------->  /    \
=> 	 /x____y\	           /x____y\
=> 	  |    |  	            |    |
=>        a1-T1   T2-a2	         a2-T2   T1-a1
=> 
=> Thanks for any hint
=> 
=> 		Guido

Unfortunately, the exchange-tree function is not implemented by the core VTP.
In fact, we don't have a pattern language to express tree modifications.

However the exchange-tree may be implemented without tree duplications by
using a metavariable.

(de exchange-tree (var x y)
;;; -------------
;;; var is a {variable}
;;; x, y are disjoint subtrees of the variable root.
;;;
   (let ((hole (replace-by-hole var x)))
     ({variable}:change var y x ()) ;; the last argument tells the message
                                    ;;  system not to update the display.
     ({variable}:change var hole y) ;; a message is emitted, the display is
                                    ;;  automatically updated
     )
   )


(de replace-by-hole (var tree)
;;; ---------------
;;; var is a {variable}
;;; tree is a subtree of the variable root.
;;; tree is replaced by a metavariable tree.
;;; The metavariable tree is returned.
;;;
   (let ((rank ({tree}:rank tree))
         (parent ({tree}:erase tree))
         )
     ({tree}:down parent rank)
     )
   )

Hope this may help you.

Vincent