haskell - 如何在 Either 中收集 ST 操作列表？

Question

我该如何转换 [Either ST]到 Either [ST]然后按顺序运行这些 Action ？下面的代码似乎适用于运行 ST 操作列表，但是当尝试在 Either 中生成操作列表时(交换下面的 test 定义)，类型不再排列。我本来希望列表的类型是相同的，因此我将非常感谢对差异的任何解释。

{-# LANGUAGE RankNTypes #-}

import qualified Data.STRef as ST
import qualified Control.Monad.ST as ST

run :: (forall s. [ST.STRef s Int -> ST.ST s Int]) -> Int
run fs =
  ST.runST $ do
    x <- ST.newSTRef 0
    mapM_ (\f ->
        f x >>= ST.writeSTRef x
      ) fs
    ST.readSTRef x

action :: ST.STRef s Int -> ST.ST s Int
action = \x -> ST.readSTRef x >>= \y -> return (y + 1)

-- test :: Either String Int
-- test = mapM (const (return action)) [0..5] >>= \fs -> return (run fs)

test :: Int
test = run (map (const action) [0..5])

main = print test

Answer 1

存在更高级别类型的类型推断是不可判定的。 GHC 的类型推断算法做了一些简化的假设，这使得它不完整。其中包括:

GHC 将假定由 lambda 绑定(bind)的变量是单型(它不包含(前导？)forall s)

当您使用多态函数时，GHC 将假定其类型中的自由类型变量将被实例化为单型

如果您礼貌地要求 GHC 使用特定的多型，这两个假设都可以被覆盖。

现在，您希望您的程序如何进行类型检查？

为了 run fs要进行类型检查，我们最好有 fs :: forall s. [ST.STRef s Int -> ST.ST s Int]

所以，根据上面的第一点，我们必须在绑定(bind)它的 lambda 上写下这个类型签名:\(fs :: forall s. [ST.STRef s Int -> ST.ST s Int]) -> ... (使用 ScopedTypeVariables )

现在考虑使用 >>= .它的类型是Monad m => m a -> (a -> m b) -> m b .但是，我们需要 a = forall s. [ST.STRef s Int -> ST.ST s Int] .所以，根据上面的第二点，我们需要给出 >>=类型签名，如

... `op` (\(fs :: forall s. [ST.STRef s Int -> ST.ST s Int]) -> ...)
    where op :: Monad m
             => m (forall s. [ST.STRef s Int -> ST.ST s Int])
             -> ((forall s. [ST.STRef s Int -> ST.ST s Int]) -> m b)
             -> m b
          op = (>>=)

现在我们遇到了一种新的问题。在 op 的这个应用程序中，第一个参数的类型为 Either String (forall s. [ST.STRef s Int -> ST.ST s Int]) .不允许将类型构造函数((->) 除外)应用于多类型，除非您打开(损坏的)ImpredicativeTypes。但是，我们可以打开它并继续...

深入第一个参数，我们可以看到我们需要 return :: Monad m => a -> m a实例化于 a = forall s. ST.STRef s Int -> ST.ST s Int .因此，我们需要在 return 中添加另一个类型签名。

同样，我们需要 mapM :: Monad m => (a -> m b) -> [a] -> m [b]实例化于 b = forall s. ST.STRef s Int -> ST.ST s Int

如果您密切注意，您会注意到另一个问题:mapM 的结果有类型

Either String [forall s. ST.STRef s Int -> ST.ST s Int]

但是 (>>=) 的论点必须是类型

Either String (forall s. [ST.STRef s Int -> ST.ST s Int])

你需要在这些之间进行转换。实际上这是一个空操作，但 GHC 不够聪明，无法知道它，所以你必须做一个线性时间转换，比如

liftM (\x -> map (\(y :: forall s. ST.STRef s Int -> ST.ST s Int) -> y) x)

(除了 liftM 将需要另一个类型签名)

故事的寓意:你可以这样做，但你不应该这样做。

如果您隐藏 forall，您通常会更轻松。 s里面的新类型，比如

newtype S s = S { unS :: forall s. ST.STRef s Int -> ST.ST s Int }

这使得在您的程序中引入多态性的点更加明确(通过 S 和 unS 的出现)。