Haskell -混合状态计算

Question

鉴于以下结构：

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

(CState是一种用来保持状态的结构，但现在不太感兴趣了。)

现在我想让它成为monad的一个实例，它基本上只是一个状态Monad，可以很容易地用StateT实现。它唯一的补充是，我想要跟踪，结果计算是纯的还是操作的，我希望能够在执行Action之前检查计算是否包含任何Action(这样Action中的IO就不会被执行)。

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

确定a >> b是否为纯的规则很简单:如果a和b都是Pure，那么a >> b就是Pure，否则它就是一个动作。

现在我开始实现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

这是可行的，但是假设我绑定到的函数总是以相同的纯度返回计算，而不管它的输入是什么。这个假设在我看来是合理的，因为计算的纯度应该清楚地说明，并且不依赖于某些计算，直到我注意到以下形式的函数不适用于这个假设：

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

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

有没有人看到解决这一问题的办法，或者有证据证明这是不可能的？

Answer 1

您可以尝试使用GADT：

data Pure
data Action

data Computation t a where
   Pure :: (CState -> (a, CState))      -> Computation t a
   Action :: (CState -> IO (a, CState)) -> Computation Action a

其思想是，值x :: Computation Action a可以执行IO (但也可以是纯的)，而值y :: Computation Pure a不能执行IO。

例如,

liftComp :: Computation t a -> Computation Action a
liftComp (Pure c) = Pure c
liftComp x@(Action c) = x

Answer 2

您已经遇到了一个事实，即一元计算不适合静态分析，因为效果(在您的例子中，影响的存在)取决于在计算过程中获得的值。如果不运行计算，就无法预测它们。

当您从Applicative到Arrow到Monad时，您获得了"power“(您可以表示更多的计算)，但是在静态分析方面失去了灵活性。

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