Haskell - 混合状态计算

Question

鉴于以下结构:

data Computation a = Pure (CState -> (a, CState))
                   | Action (CState -> IO (a, CState))

(CState 是一些用于保持状态的结构，但现在没有多大意义。)
现在我想让它成为 Monad 的一个实例，它基本上只是一个状态 monad，可以很容易地用 StateT 实现。它唯一的补充是，我想跟踪生成的计算是纯计算还是操作，并且我希望能够在执行之前检查计算是否包含任何操作一个 Action(因此 Action 中的 IO 不会被执行)。

还应该注意的是，Computation 有两个构造函数并不重要。我刚刚开始使用这些构造函数来实现这一点。

判断a >> b是否是Pure的规则很简单:如果 a 和 b 都是 Pure，则 a >> b 是 Pure，否则这是一个 Action 。

现在我开始实现 Monad 实例:

instance Monad Computation where
    return x = Pure $ \s -> (x, s)
    (Action c) >>= f = Action . runStateT $
                         (StateT $ unpackAction oldComp) >>= (StateT . unpackAction . f)
    p@(Pure c) >>= f
      | givesPure f = Pure . runState $
                        state oldF >>= (state . unpackPure . f)
      | otherwise = liftComp p >>= f -- Just lift the first argument and recurse, to make an action

-- Helper functions used above:
unpackAction :: Computation a -> (CState -> IO (a, CState))
unpackAction (Pure c) = return . c 
unpackAction (Action c) = c

-- Make an Action out of a Pure
liftComp :: Computation a -> Computation a
liftComp (Pure c) = Action $ return . c
liftComp a@(Action _) = a

所以唯一缺少的部分是givesPure函数，我不确定是否可以实现它。我曾经有过这样的实现:

givesPure :: (a -> Computation b) -> Bool
givesPure f = isPure $ f undefined -- I actually used error with a custom message instead of undefined, but that shouldn't matter

isPure :: Computation a -> Bool
isPure (Pure _) = True
isPure (Action _) = False

这是可行的，但假设我绑定(bind)的函数总是返回具有相同纯度的计算，无论其输入是什么。这个假设对我来说似乎很合理，因为计算的纯度应该明确说明，而不是依赖于某些计算，直到我注意到以下形式的函数不适用于此假设:

baz :: Int -> Computation b
baz x = if x > 5 
        then foo
        else bar
-- foo and bar both have the type Computation b

所以在我看来，不可能做到这一点，因为我需要当前状态来应用第一个计算，以获得函数的正确输入来获得第二个计算并测试它是否是纯的。

有没有人找到解决方案或有证据表明这是不可能的？

Answer 1

您已经遇到这样的事实:一元计算不适合静态分析，因为效果(在您的情况下，效果的存在)取决于计算本身期间获得的值。如果不运行计算，您就无法预测它们。

当你从Applicative到Arrow再到Monad时，你会获得“力量”(你可以表达更多的计算)，但会失去易于静态分析。

对于Applicative，有一个现成的Lift将纯计算添加到现有应用程序的数据类型。但它没有 Monad 实例。