哈斯克尔：地图runST

Question

的类型[ST s (Int, [Int])]我有一个绑定，我试图用图如下申请runST每一个元素：

name :: [ST s (Int, [Int])] --Of Course there is a real value here 
map runST name 

这给了我一个错误信息

Couldn't match expected type `forall s. ST s b0' 
    with actual type `ST s0 (Int, [Int])' 
Expected type: [forall s. ST s b0] 
    Actual type: [ST s0 (Int, [Int])] 
In the second argument of `map', namely `name' 
In the expression: map runST name 

肯定有我误解的东西。我知道runST and function composition，但我不确定这是否适用。

感谢大家的时间！

Answer 1

每次运行带有runST的状态变换器时，它都会在与所有其他状态变换器分开的某个本地状态上运行。 runST将创建一个新的状态类型并使用该类型调用其参数。因此，举例来说，如果执行

let x = runST (return()) 
    y = runST (return()) 
in (x, y) 

然后第一return()和第二return()都会有不同的类型：ST s1()和ST s2()，对于一些未知类型s1和s2由runST创建。

您正在尝试拨打runST，该参数的状态类型为s。这不是runST创建的状态类型，也不是您可以选择的任何其他类型。要调用runST，您必须传递一个参数，该参数可以有任何状态类型。下面是一个例子：

r1 :: forall s. ST s() 
r1 = return() 

由于r1是多态的，它的状态可具有任何类型，包括任何类型由runST选择。您可以通过多态r1 s的列表（-XImpredicativeTypes）映射runST：

map runST ([r1, r1] :: [forall t. ST t()]) 

但是，你不能过度的非多态性r1的List映射runST。

map runST ([r1, r1] :: forall t. [ST t()]) -- Not polymorphic enough 

类型forall t. [ST t()]说，所有列表元素都有状态类型t。但是他们都需要独立的状态类型，因为每个状态都会调用runST。这就是错误信息的含义。

如果可以对所有列表元素给予相同的状态，那么您可以拨打runST一次，如下所示。显式类型签名不是必需的。

runST (sequence ([r1, r1] :: forall t. [ST t()])) 

Answer 2

您的name不够多态。您的发言

name :: [ST s (Int, [Int])] 

的意思是 '有状态的计算返回列表（智力，[INT]），其中有完全相同s'。但看看runST类型：

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

这种类型的意思是“一个函数，它接受一个有状态计算，其中s可以是任何你能想象”。这些类型的计算不是一回事。最后：

map runST :: [forall s. ST s a] -> [a] 

你看，你的列表应该包含比现在更多的多态值。 s类型在列表中的每个元素中可能不同，它可能与name中的类型不同。更改name的类型签名，并且全部都应该正常。它可能需要启用一些扩展，但GHC应该能够告诉你哪些扩展。

Answer 3

我会尽力解释为runST的类型推理：

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

，为什么它是不是这样简单的一个：

alternativeRunST :: ST s a -> a 

注意，这alternativeRunST将工作过为你的程序。

alternativeRunST也已经让我们泄露变量出ST单子：

leakyVar :: STRef s Int 
leakyVar = alternativeRunST (newSTRef 0) 

evilFunction :: Int -> Int 
evilFunction x = 
    alternativeRunST $ do 
    val <- readSTRef leakyVar 
    writeSTRef leakyVar (val+1) 
    return (val + x) 

然后，你可以去ghci中做：

>>> map evilFunction [7,7,7] 
[7,8,9] 

evilFunction不是引用透明！

顺便说一下，尝试一下自己这里来运行上面的代码所需要的“坏ST”的框架：

{-# LANGUAGE GeneralizedNewtypeDeriving #-} 
import Control.Monad 
import Data.IORef 
import System.IO.Unsafe 
newtype ST s a = ST { unST :: IO a } deriving Monad 
newtype STRef s a = STRef { unSTRef :: IORef a } 
alternativeRunST :: ST s a -> a 
alternativeRunST = unsafePerformIO . unST 
newSTRef :: a -> ST s (STRef s a) 
newSTRef = ST . liftM STRef . newIORef 
readSTRef :: STRef s a -> ST s a 
readSTRef = ST . readIORef . unSTRef 
writeSTRef :: STRef s a -> a -> ST s() 
writeSTRef ref = ST . writeIORef (unSTRef ref) 

真正runST不允许我们构建这样的“恶”的职能。它是如何做到的？这是有点棘手，见下图：

试图运行：

>>> runST (newSTRef "Hi") 
error: 
    Couldn't match type `a' with `STRef s [Char]' 
... 

>>> :t runST 
runST :: (forall s. ST s a) -> a 
>>> :t newSTRef "Hi" 
newSTRef "Hi" :: ST s (STRef s [Char]) 

newSTRef "Hi"不适合(forall s. ST s a)。由于可以使用更简单的例子来也看到了，在那里GHC为我们提供了一个相当不错的错误：

dontEvenRunST :: (forall s. ST s a) -> Int 
dontEvenRunST = const 0 

>>> dontEvenRunST (newSTRef "Hi") 
<interactive>:14:1: 
    Couldn't match type `a0' with `STRef s [Char]' 
     because type variable `s' would escape its scope 

请注意，我们也可以写

dontEvenRunST :: forall a. (forall s. ST s a) -> Int 

它相当于省略forall a.因为我们之前做过。

请注意，a的范围大于s的范围，但在newSTRef "Hi"的情况下，其值应取决于s。类型系统不允许这样做。