Haskell:map runST

Question

我有一个类型的绑定[ST s (Int, [Int])],我试图runST使用map 应用于每个元素,如下所示:

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和函数组成,但我不确定这是否适用.

谢谢大家的时间!

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.您可以映射runST多态r1的列表(带-XImpredicativeTypes):

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

但是,您无法映射runST非多态r1的列表.

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,[Int])具有完全相同的 s '.但看看的类型runST:

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

这种类型意味着"一种能够进行状态计算的功能,s 可以是任何你能想象到的东西 ".这些类型的计算不是一回事.最后:

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

你看,你的列表应该包含比现在更多的多态值.s类型可以在列表的每个元素中不同,它可能与in中的类型不同name.更改类型签名name,一切都应该没问题.可能需要启用一些扩展,但GHC应该能够告诉您哪些扩展.

Answer 3

我会试着解释一下这种runST类型的推理:

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

为什么它不像这个简单的:

alternativeRunST :: ST s a -> a

请注意,这alternativeRunST对您的程序有用.

alternativeRunST也会让我们把变量泄漏出STmonad:

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.类型系统不允许这样做.