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是否为Pure的规则很简单： 如果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

所以在我的看来，这似乎是不可能的，因为我需要当前状态来应用第一个计算，以获取函数的正确输入，从而获得第二个计算并测试其是否纯净。

有人看到解决方案吗？还是有证据表明这是不可能的？

- Kritzefitz

---

其实这与“Comp”是一样的，只是我有点混淆了，因为在实际代码中我使用了“Computation”，但在这里想要缩短它，结果大部分时间都写全了。我编辑了答案，使得“Computation”在所有地方都出现了。 - Kritzefitz

Answer 1

您遇到了单子计算不适用于静态分析的事实，因为效果（在您的情况下，存在效果）取决于计算本身期间获得的值。 您无法在运行计算之前预测它们。

当您从“Applicative”转移到“Arrow”再到“Monad”时，您在“能力”方面有所增加（可以表达更多计算），但在静态分析方面则会减少。

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

- danidiaz

Answer 2

你可以尝试使用 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

- chi

---

那有什么不同之处（更重要的是它如何帮助），与我已经拥有的有何不同？ - Kritzefitz

@Kritzefitz，你有一个类型为Computation Pure a的东西，它保证里面有一个Pure而不是一个Action。 - chi

我对 forall 及其含义并不是很了解。我该如何使 t 成为多态的？ - Kritzefitz

定义 x = Pure... 可以使其具有多态性，同时如果 x1, x2 都是多态的话，x1 >> x2 就是多态的；如果一个是多态，另一个是单态，则 x1 >> x2 是单态的，因为多态被实例化了。 - chi

但我仍然不知道我的Monad实例应该是什么样子。 - Kritzefitz