通用量化和统一，一个例子

Question

给定运行 monad ST

的以下签名

runST :: (forall s. ST s a) -> a

和函数

newVar  :: a -> ST s (MutVar s a) 
readVar :: MutVar s a -> ST s a

然后 Haskell 编译器将拒绝以下类型错误的表达式

let v = runST (newVar True)
in runST (readVar v)

因为要计算 runST，需要类型

readVar v :: ST s Bool

必须概括为

∀s . ST s Bool

我的问题是这里通用量词的唯一工作是确保类型变量 s 在避免泛化的评估上下文中始终是自由的，对吗？或者这里有关于全称量词的更多信息？

Answer 1

我觉得你漏掉了什么。 GHCi 给出的实际消息是：

Prelude> :m +Control.Monad.ST
Prelude Control.Monad.ST> data MutVar s a = MutVar
Prelude Control.Monad.ST> :set -XRankNTypes
Prelude Control.Monad.ST> data MutVar s a = MutVar
Prelude Control.Monad.ST> let readVar = undefined :: MutVar s a -> ST s a
Prelude Control.Monad.ST> let newVar = undefined :: a -> ST s (MutVar s a)
Prelude Control.Monad.ST> runST $ readVar $ runST $ newVar True

<interactive>:14:27:
    Couldn't match type ‘s’ with ‘s1’
    ‘s’ is a rigid type variable bound by
        a type expected by the context: ST s Bool at <interactive>:14:1
    ‘s1’ is a rigid type variable bound by
        a type expected by the context: ST s1 (MutVar s Bool)
        at <interactive>:14:19
    Expected type: ST s1 (MutVar s Bool)
    Actual type: ST s1 (MutVar s1 Bool)
    In the second argument of ‘($)’, namely ‘newVar True’
    In the second argument of ‘($)’, namely ‘runST $ newVar True’

Haskell 编译器拒绝它不是因为任何与 readVar 有关，而是因为 newVar 有问题ST s (MutVar s a) 允许 s 通过跳转到 MutVar 表达式来 "escape" 其上下文。

Answer 2

让我们读一下runST的类型。我也为 a 添加了一个显式限定符。

runST :: forall a . (forall s. ST s a) -> a

合约内容如下：

来电者选择固定类型a
调用者提供了一个参数x
对于 s 的任何选择，参数 x 必须是 ST s a 类型。换句话说，s 将由 runST 选择，而不是由调用者选择。

让我们看一个类似的例子：

runFoo :: forall a . (forall s. s -> [(s,a)]) -> [a]
runFoo x =
    let part1 = x "hello!"          -- here s is String
        -- part1 has type [(String, a)]
        part2 = x 'a'               -- here s is Char
        -- part2 has type [(Char, a)]
        part3 = x (map snd part2)   -- here s is [a]   (!!!)
        -- part3 has type [([a],a)]
    in map snd part1 ++ map snd part2 ++ map snd part3

test1 :: [Int]
test1 = runFoo (\y -> [(y,2),(y,5)])   -- here a is Int

test2 :: [Int]
test2 = runFoo (\y -> [("abc" ++ y,2)])       -- ** error
-- I can't choose y :: String, runFoo will choose that type!

上面，注意a是固定的（到Int），我不能对y的类型做任何限制。此外：

test3 = runFoo (\y -> [(y,y)])    -- ** error

这里我不是提前固定a，而是在尝试选择a=s。我不允许这样做：runFoo 可以根据 a 选择 s（参见上面的 part3），因此 a 必须固定在前进。

现在，以你的例子为例。问题出在

runST (newSTRef ...)

这里，newSTRef returns一个ST s (STRef s Int)，所以它正在尝试选择a = STRef s Int。因为a依赖于s，这个选择是无效的。

这个 "trick" 被 ST monad 用来防止从 monad 引用 "escape"。也就是说，保证在 runST returns 之后，所有引用现在都不再可访问（并且可能会被垃圾收集）。因此，在 ST 计算期间使用的可变状态已被丢弃，runST 的结果确实是一个纯值。毕竟，这是 ST monad 的主要目的：它旨在允许（临时）可变状态用于纯计算。

通用量化和统一，一个例子

Universal quantification and unification, an example

haskell

types