在 haskell 中重写树

Question

一般情况：
我想知道如何写入树（即更改底层的特定节点，将其替换为具有不同值的节点，该节点将旧节点作为其左子节点，将新节点作为右子节点）


特定的应用程序使它变得更加困难：
我试图将一个类似 20 个问题的游戏放在一起，从文件中读取现有的树，询问用户各种问题，如果不知道答案，则会询问用户区分最终猜测和正确答案以及正确答案之间的问题，并将新条目添加到游戏中（用指向猜测和答案的节点中的新问题替换猜测所在的位置）

Answer 1

通常，Monad 结构和这种树嫁接之间存在紧密的对应关系。这是一个例子

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

或者也许使用我们从上方绑定的某个位置下方的所有叶子！

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

一般来说，有很多方法可以实现这一目标。