Wie verschiebe ich einen Teilbaum zwischen Bäumen in Haskell?

Question

Für zwei Mehrweg-Bäume, T1 und T2 definiert

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

Wie kann ich eine Funktion schreiben, die eine Teilstruktur von t1 entfernen werden und es zu einem bestimmten Knoten in t2 einfügen?

Ich stelle mir die Signatur so etwas wie

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

aussehen würde also ein Baum und übergeordneten Knoten, die einen Teilbaum nimmt entfernt werden, und einen zweiten Baum, und der Knoten, der den Punkt, an dem bestimmt den ursprünglichen einzufügen Teilbaum.

Getrennte Funktionen zum Entfernen und Hinzufügen des Teilbaums können bei Bedarf zusammengestellt werden.

Answer 1

Sie können Änderungen vornehmen und "an einem Pfad" in einem Baum lesen.

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') 

Und dann mit diesem Tool können Sie „Kopieren und Einfügen“ Teilbäume von einem Pfad zu einem anderen

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

Interessanterweise „Baum, der an Pfad“ bildet eine Lens, die die gemeinsame Struktur zwischen diesen beiden subsumiert Operationen.