在haskell中重寫樹

Question

一般情況：
我想知道如何寫入樹（即更改底層的特定節點，將其替換爲具有舊節點作爲其左側子節點的不同值的節點和一個新的節點作爲右子）


具體的應用程序，計劃使更多的困難：
我試圖把一個遊戲類似於20道題，從文件中讀取現有的樹，詢問用戶的各種問題，如果它不知道答案會詢問用戶在最終猜測和正確答案以及正確答案之間的區別問題，並將新條目添加到遊戲中E（更換位置的猜測與新問題是在指向的猜測，答案節點）

Answer 1

時常有單子結構，這種樹嫁接之間的緊密對應關係。這裏有一個例子

data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Functor 

instance Monad Tree where 
    return = Leaf 
    Leaf a >>= f = f a 
    Branch l r >>= f = Branch (l >>= f) (r >>= f) 

凡(>>=)所做的無非就是基於一些功能f :: a -> Tree a葉延伸（樹嫁接）更多。

然後，我們可以很容易地進行嫁接你正在尋找

graftRight :: Eq a => a -> a -> Tree a -> Tree a 
graftRight a new t = t >>= go where 
    go a' | a' == a = Node a new 
     | otherwise = Leaf a' 

但是，這是低效得不得了，因爲它會在你的樹尋找你想更換一個具體參觀每Leaf。如果我們知道更多信息，我們可以做得更好。如果樹以某種方式訂購併分類，那麼您可以使用fingertree或splaytree進行有效的替換。如果我們知道節點，我們可以使用Zipper來替換它的路徑。

data TreeDir = L | R 
data ZTree a = Root 
      | Step TreeDir (Tree a) (ZTree a) 

它可以讓我們一步進出的樹

stepIn :: Tree a -> (Tree a, ZTree a) 
stepIn t = (t, Root) 

stepOut :: (Tree a, ZTree a) -> Maybe (Tree a) 
stepOut (t, Root) = Just t 
stepOut _   = Nothing 

根的，一旦我們在裏面，走在任何方向上我們喜歡

left :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a) 
left (Leaf a, zip) = Nothing 
left (Branch l r, zip) = Just (l, Step R r zip) 

right :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a) 
right (Leaf a, zip) = Nothing 
right (Branch l r, zip) = Just (r, Step L l zip) 

up :: (Tree a, ZTree a) -> Maybe (Tree a, ZTree a) 
up (tree, Root) = Nothing 
up (tree, Step L l zip) = Just (branch l tree, zip) 
up (tree, Step R r zip) = Just (branch tree r, zip) 

和編輯葉子

graft :: (a -> Tree a) -> (Tree a, ZTree a) -> Maybe (Tree a, ZTree a) 
graft f (Leaf a, zip) = Just (f a, zip) 
graft _ _    = Nothing 

或者也許所有o f使用我們從上面的綁定在某個位置下的葉子！

graftAll :: (a -> Tree a) -> (Tree a, ZTree a) -> (Tree a, ZTree a) 
graftAll f (tree, zip) = (tree >>= f, zip) 

，然後我們可以做我們的移植

graftBelow :: (a -> Tree a) -> [TreeDir] -> Tree a -> Maybe (Tree a) 
graftBelow f steps t = perform (stepIn t) >>= stepOut where 
    perform =  foldr (>=>) Just (map stepOf steps)   -- walk all the way down the path 
      >=> (Just . graftAll f)      -- graft here 
      >=> foldr (>=>) Just (map (const up) steps)  -- walk back up it 
    stepOf L = left 
    stepOf R = right 

---

>>> let z = Branch (Branch (Leaf "hello") (Leaf "goodbye")) 
        (Branch (Branch (Leaf "burrito") 
            (Leaf "falcon")) 
          (Branch (Leaf "taco") 
            (Leaf "pigeon"))) 

>>> graftBelow Just [] z == z 
True 

>>> let dup a = Branch (Leaf a) (Leaf a) 
>>> graftBelow dup [L, R] z 
Just (Branch (Branch (Leaf "hello") 
        (Branch (Leaf "goodbye") 
          (Leaf "goodbye"))) 
      (Branch (Branch (Leaf "burrito") (Leaf "falcon")) 
        (Branch (Leaf "taco") (Leaf "pigeon")))) 

>>> graftBelow dup [L, R, R] z 
Nothing 

之前走在樹中的任意點一般有很多的方式來實現這一目標。