हास्केल में पेड़ के बीच एक उपट्री कैसे स्थानांतरित करें?

Question

दो मल्टी-वे पेड़, t1 और टी 2 के लिए, का उपयोग करके परिभाषित

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

कैसे मैं एक समारोह है कि t1 से एक सबट्री हटाने और t2 में दिए गए नोड पर से जोड़ दिया जाएगा लिख ​​सकता है?

मैं कल्पना हस्ताक्षर की तरह

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

कुछ ऐसा दिखाई देगा यानी यह एक पेड़ और माता पिता के नोड एक सबट्री को परिभाषित करने लग जाते हैं हटा दिया जाना चाहिए, और एक दूसरे पेड़ और नोड कि जिस पर मूल डालने के लिए के बिंदु को परिभाषित सबट्री।

निकालने के लिए अलग-अलग फ़ंक्शन और फिर आवश्यक होने पर उपट्री को जोड़ा जा सकता है।

Answer 1

आप एक पेड़ में संपादन कर सकते हैं और "पथ पर" पढ़ सकते हैं।

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

और फिर एक और

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

दिलचस्प बात यह है के लिए इस उपकरण "कॉपी और पेस्ट" एक पथ से subtrees आप कर सकते हैं का उपयोग कर, "पथ पर सबट्री" का निर्माण एक Lens जो इन दोनों के बीच सामान्य संरचना subsumes संचालन।