使用 State Monad 插入树

Question

我有一个树和插入操作定义为 "Learn You a Haskell for Great Good!" :

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

treeInsert :: (Ord a) => a -> Tree a -> Tree a  
treeInsert x EmptyTree = Node x EmptyTree EmptyTree
treeInsert x (Node a left right)   
    | x == a = Node x left right  
    | x < a  = Node a (treeInsert x left) right  
    | x > a  = Node a left (treeInsert x right)

我想使用 State Monad 重新实现 treeInsert，但我什至不确定函数声明应该是什么样子。到目前为止我有这个：

treeInsert :: (Ord a) => a -> Tree a -> State (Tree a) a

你会如何使用 State Monad 编写 treeInsert？

Answer 1

警告：此回答包含剧透。

您可以很容易地围绕现有的 treeInsert 函数编写一个包装器，使您可以按照自己的方式使用 do-notation。根据评论，有一个函数 modify 接受修改函数 f :: s -> s 并将其转换为 State s () ，这是一个 "action" 来修改状态 s .这意味着你可以写：

stateTreeInsert :: (Ord a) => a -> State (Tree a) ()
stateTreeInsert x = modify (treeInsert x)

或更简洁：

stateTreeInsert :: (Ord a) => a -> State (Tree a) ()
stateTreeInsert = modify . treeInsert

然后，您可以定义一个 "action"，例如：

insertSomeStuff :: (Ord a, Num a) => State (Tree a) ()
insertSomeStuff = do
  stateTreeInsert 0
  stateTreeInsert 1
  stateTreeInsert 2

然后使用 execState:

将其应用于特定的树

main = print $ execState insertSomeStuff EmptyTree

不过，我猜你更感兴趣的是 re-implementing treeInsert 从头开始 state-manipulating 形式。

问题是 "straightforward" 这样做的方式不是很有趣或惯用。这很尴尬。它看起来像这样：

awkwardTreeInsert :: (Ord a) => a -> State (Tree a) ()
awkwardTreeInsert x = do
  t <- get
  case t of
    EmptyTree -> put $ Node x EmptyTree EmptyTree
    Node a l r -> case compare x a of
      LT -> do put l                 -- replace tree with left child
               awkwardTreeInsert x   -- insert into left child
               l' <- get             -- get the answer
               put $ Node a l' r     -- overwrite with whole tree w/ updated left child
      GT -> do put r
               awkwardTreeInsert x
               r' <- get
               put $ Node a l r'
      EQ -> return ()

这里的问题是，正如我们所写的，状态一次只能容纳一棵树。所以，如果我们要递归调用算法在分支中插入一些东西，我们需要用它的children之一覆盖"big tree"，运行递归插入，得到答案，并用 "big tree" 覆盖它并替换为适当的 child。

无论如何，它的工作方式与 stateTreeInsert 相同，所以：

insertSomeStuff :: (Ord a, Num a) => State (Tree a) ()
insertSomeStuff = do
  awkwardTreeInsert 0
  awkwardTreeInsert 1
  awkwardTreeInsert 2

main = print $ execState insertSomeStuff EmptyTree

使用 State Monad 插入树

Tree Insert using State Monad

haskell

tree

monads

state-monad