Haskell中FreeState转State的eval函数实现正确性问询

一、State Monad 核心概念 #

State s a 本质是带状态的计算，可以理解为一个函数：

s -> (a, s)

• 输入：初始状态 s
• 输出：计算结果 a + 更新后的状态 s

常用辅助工具与操作：

• runState :: State s a -> s -> (a, s)：执行带状态的计算，传入初始状态，得到最终的结果-状态对
• put :: s -> State s ()：将当前状态设置为给定值，无实际计算结果（返回()）
• get :: State s s：获取当前状态，结果就是当前状态值
• return :: a -> State s a：不修改状态，直接返回结果a

你的FreeState其实是State操作的自由 monad，每个构造子对应State的基础操作：

• Put s next：先把状态设为s，再执行后续计算next
• Get f：先获取当前状态s，再执行f s生成的后续计算
• Return a：终止计算，返回结果a

二、你的实现问题分析 #

直接结论：你的实现不正确，错误点在于没有保留后续计算的状态变化，强行固定了最终状态。

逐一拆解：

1. Return 分支：
   你的代码State (\s -> (a, s))是正确的，符合return语义——不修改状态，直接返回结果。

2. Put 分支：
   你的代码：

   eval (Put s z) = State (\_ -> (fst (runState (eval z) s), s))
   

   错误在于：执行eval z后会得到新状态s'，但你强行把最终状态设为s（Put的参数），丢弃了z执行后的状态变化。正确逻辑应该是：先将初始状态替换为s，然后执行eval z，直接复用eval z输出的结果-状态对。

3. Get 分支：
   你的代码：

   eval (Get z) = State (\s -> (fst $ (runState (eval (z s)) s), s))
   

   错误在于：执行eval (z s)后会得到新状态s'，但你强行把最终状态设为原状态s，同样丢弃了后续计算的状态变化。正确逻辑应该是：用当前状态s调用z得到后续计算，执行该计算后直接复用其输出的结果-状态对。

三、正确实现写法 #

写法1：用do notation（更直观） #

import Control.Monad.State

data FreeState s a = 
      Get (s -> FreeState s a)
    | Put s (FreeState s a)
    | Return a

eval :: FreeState s a -> State s a
eval (Return a) = return a
eval (Put s next) = do
  put s       -- 先设置状态为s
  eval next   -- 执行后续计算，自动传递状态变化
eval (Get f) = do
  s <- get    -- 获取当前状态
  eval (f s)  -- 用当前状态生成后续计算并执行

写法2：直接展开为函数形式（更底层） #

import Control.Monad.State

data FreeState s a = 
      Get (s -> FreeState s a)
    | Put s (FreeState s a)
    | Return a

eval :: FreeState s a -> State s a
eval (Return a) = State (\s -> (a, s))
eval (Put s next) = State (\old -> runState (eval next) s)
-- 不管旧状态，直接用s作为初始状态执行next，结果就是next的输出
eval (Get f) = State (\curr -> runState (eval (f curr)) curr)
-- 用当前状态curr生成next，执行next后的结果就是整个Get操作的输出

内容的提问来源于stack exchange，提问作者someStudentCS