haskell - 在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你树中的每一个，搜索你想要替换的特定的。如果我们知道更多信息，我们可以做得更好。如果树以某种方式排序和排序，那么您可以使用fingertreeorsplaytree进行有效的替换。如果我们只知道我们想用它的路径替换的节点，我们可以使用 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

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