Come spostare un sottoalbero tra gli alberi in Haskell?

Question

Per due alberi multidirezionali, t1 e t2, definito utilizzando

type Forest a = [Tree a] 
data Tree a = Node { 
     rootLabel :: a,  
     subForest :: Forest a 
    } 

come posso scrivere una funzione che rimuove una sottostruttura da t1 e inserirla in un dato nodo t2?

immagino la firma sarebbe simile

moveSubTree :: ((Tree x a) x (Tree x a)) -> (Tree x Tree) 

cioè ci vuole un nodo della struttura e genitore che definisce una sottostruttura di essere rimosso, e un secondo albero e il nodo che definisce il punto in cui inserire l'originale sottostruttura.

Separare le funzioni per rimuovere e quindi aggiungere la sottostruttura potrebbe essere composto se necessario.

Answer 1

È possibile apportare modifiche e letture "su un percorso" in un albero.

data Dir = L | R 
type Path = [Dir] 
data Tree a = Leaf | Node a (Tree a) (Tree a) 

read :: Path -> Tree a -> Maybe (Tree a) 
read []  t = t 
read (s:ss) t = case t of 
    Leaf  -> Nothing 
    Node a l r -> case s of 
    L -> read ss l 
    R -> read ss r 

edit :: Path -> (Tree a -> Tree a) -> Tree a -> Maybe (Tree a) 
edit []  f t = Just (f t) 
edit (s:ss) f t = case t of 
    Leaf  -> Nothing 
    Node a l r -> case s of 
    L -> do 
     l' <- edit ss f l 
     return (Node a l' r) 
    R -> do 
     r' <- edit ss f r 
     return (Node a l r') 

E quindi utilizzando questo strumento è possibile "copia e incolla" sottostrutture da un percorso a un altro

cnp :: Path -> Path -> Tree a -> Maybe (Tree a) 
cnp readPath writePath t = do 
    subtree <- read readPath t 
    edit writePath (const subtree) t 

È interessante notare che, "sotto-albero nel percorso" forma un Lens che sussume la struttura comune tra questi due operazioni.