haskell - 修改 monad 状态

Question

对于编程练习，我应该采用数据类型的树

data Tree a = Branch (Tree a) a (Tree a) | Leaf
    deriving (Eq, Ord, Show)

并用 Int 标记每个 a，越来越多地按深度优先顺序使用状态 monad，并计算 monadic Action 的数量。例如，表达式

let tree = Branch (Branch Leaf "B" Leaf) "A" Leaf
in run (label tree) 42

应该评估为

(Branch (Branch Leaf (42, "B") Leaf) (43, "A") Leaf
, Counts {binds = 10,returns = 5, gets = 4, puts = 2})

状态的类型是:

newtype State' s a = State' { runState' :: (s, Counts) -> (a, s, Counts) }

这是我对 label 和 run 的实现

label :: MonadState m Int => Tree a -> m (Tree (Int, a))
label Leaf                      = return Leaf
label (Branch left value right) = do
                                  newLeft  <- label left
                                  int <- get
                                  put (int + 1)
                                  newRight <- label right
                                  return (Branch newLeft (int, value) newRight)


run :: State' s a -> s -> (a, Counts)
run s ns = let (a, _, counts) = runState' s (ns, Counts 0 0 0 0) in (a, counts)

但是，当我运行测试用例时，我的结果是

(Branch (Branch Leaf (42,"B") Leaf) (42,"A") Leaf
, Counts {binds = 12, returns = 5, gets = 6, puts = 2})

Int 似乎根本没有更新。这很奇怪，因为作业的每个部分都有单独的测试用例，除此之外的所有内容都是正确的。无论如何，这里是 get 和 put 的实现:

-- get :: State' s s
get = State' (\(s, counts) -> (s, s, counts <> oneGet))

-- put :: s -> State' s ()
put x = State' (\(x, counts) -> ((), x, counts <> onePut))

我这里真的是一头雾水。我不知道为什么 Int 根本不受影响。非常感谢任何帮助。

Answer 1

问题出在

put x = State' (\(x, counts) -> ((), x, counts <> onePut))

在这里你应该将 x 放入一个状态，但它在 (x, counts) 模式中被隐藏了。做到这一点

put x = State' (\(_, counts) -> ((), x, counts <> onePut))

只要您不关心 monad 法则就应该没问题，因为您的任务迫使您违反它们:

count the number of monadic actions

其中一个规律是(return x >>= f) ~ f x，但是前一个表达式有额外的return和(>>=) 在里面。