在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进行有效的替换。如果我们知道要用路径代替节点，我们可以使用拉链。

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

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