哈斯克爾：地圖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。類型系統不允許這樣做。