发生这种情况是因为 rank-2 类型runST阻止您为 . 提供有意义的类型randShuffleST。（编写的代码存在第二个问题：可变 ST 数组不能有意义地存在于STmonad 之外，因此runST不可能从内部返回一个，并且构造一个传递给纯函数的可能性充其量是不可能的。这是“无趣的”，但最终可能会让人感到困惑；有关如何解决它，请参阅此答案的底部。）
那么，让我们看看为什么不能写下类型签名。值得一提的是，我同意 shachaf关于编写您正在编写的函数的最佳方法：留在内部ST，并且runST在最后只使用一次。如果您这样做，那么我在答案的底部包含了一些示例代码，显示了如何成功编写代码。但是我认为理解为什么会出现错误是很有趣的；像您遇到的错误是您不想以这种方式编写代码的一些原因！
首先，让我们先看一下产生相同错误消息的函数的简化版本：
bounds arr = runST (getBounds arr)
现在，让我们尝试给bounds. 显而易见的选择是
bounds :: (MArray a e (ST s), Ix i) => a i e -> (i,i)
bounds arr = runST (getBounds arr)
我们知道它arr必须是 anMArray并且我们不关心它有什么元素或索引类型（只要它的索引在 中Ix），但我们知道它必须存在于STmonad 中。所以这应该有效，对吧？没那么快！
ghci> :set -XFlexibleContexts +m
ghci> :module + Control.Monad.ST Data.Array.ST
ghci> let bounds :: (MArray a e (ST s), Ix i) => a i e -> (i,i)
ghci| bounds arr = runST (getBounds arr)
ghci|
<interactive>:8:25:
Could not deduce (MArray a e (ST s1))
arising from a use of `getBounds'
from the context (MArray a e (ST s), Ix i)
bound by the type signature for
bounds :: (MArray a e (ST s), Ix i) => a i e -> (i, i)
at <interactive>:7:5-38
...
等一下：？这是哪里来的？我们在任何地方都没有提到过这样的类型变量！答案是它来自的定义。一般来说，有类型（为方便起见重命名一些类型变量）；当我们在这里使用它时，我们将它限制为 type 。这里发生的是，就像一个 lambda（实际上，它是一个 lambda），在括号内进行本地绑定。因此，当返回 type 的东西时，我们可以与--- 统一，但我们不能将与统一，因为不在范围内。在 GHC 中，类型变量为Could not deduce (MArray a e (ST s1))s1runSTboundsrunSTrunST :: (forall σ. ST σ α) -> α(forall σ. ST σ (i,i)) -> (i,i)forallσgetBounds arrST s (i,i)α(i,i)σsσrunST是sand a， not σand α，所以它重命名s为 tos1以消除歧义，您看到的是这种类型的变量。
所以这个错误是公平的：我们声称对于某些特定s的 ,MArray a e (ST s)成立。但runST需要对每个 s. 但是，该错误非常不清楚，因为它引入了一个您实际上无法引用的新类型变量（因此“可能的修复”是没有意义的，尽管它无论如何都没有帮助）。
现在，显而易见的问题是，“那么我可以写一个正确的类型签名吗？” 答案是“……有点”。（但您可能不想这样做。）所需的类型如下所示：
ghci> :set -XConstraintKinds -XRank2Types
ghci> let bounds :: (forall s. MArray a e (ST s), Ix i) => a i e -> (i,i)
ghci| bounds arr = runST (getBounds arr)
ghci|
<interactive>:170:25:
Could not deduce (MArray a e (ST s))
arising from a use of `getBounds'
from the context (forall s. MArray a e (ST s), Ix i)
...
这个约束表示每个 都MArray a e (ST s)成立，但我们仍然会遇到类型错误。似乎“GHC 不支持箭头左侧的多态约束” ——事实上，在谷歌搜索试图找到该信息时，我在“主要是通常是一个函数”上找到了一篇很棒的博客文章，它遇到了与您相同的问题，解释错误，并提供以下解决方法。（他们还会收到更高级的错误消息“malformed class assertion”，这清楚地表明这样的事情是不可能的；这可能是由于不同的 GHC 版本。） s
当我们想要从 GHC 的内置系统中获得更多的类型类约束时，这个想法很常见，通过（ab）使用 GADT 来为这种类型类的存在提供明确的证据：
ghci> :set -XNoFlexibleContexts -XNoConstraintKinds
ghci> -- We still need -XRank2Types, though
ghci> :set -XGADTs
ghci> data MArrayE a e m where
ghci| MArrayE :: MArray a e m => MArrayE a e m
ghci|
ghci>
现在，只要我们有一个 type 的值MArrayE a e m，我们就知道这个值一定是用MArrayE构造函数构造的；只有当有可用的约束时才能调用此构造函数MArray a e m，因此模式匹配MArrayE将使该约束再次可用。（唯一的另一种可能性是您的该类型的值未定义，这就是为什么实际上需要模式匹配的原因。）现在，我们可以将其作为bounds函数的显式参数提供，因此我们将其称为bounds MArrayE arr：
ghci> :set -XScopedTypeVariables
ghci> let bounds :: forall a e i.
ghci| Ix i => (forall s. MArrayE a e (ST s)) -> a i e -> (i,i)
ghci| bounds evidence arr = runST (go evidence)
ghci| where go :: MArrayE a e (ST s) -> ST s (i,i)
ghci| go MArrayE = getBounds arr
ghci|
ghci> -- Hooray!
请注意我们必须将主体分解为它自己的功能并在那里进行模式匹配的奇怪之处。发生的情况是，如果您在bounds的参数列表中进行模式匹配，则sfromevidence过早地固定为特定值，因此我们需要将其推迟；并且（我认为因为使用更高级别的类型进行推断很困难）我们还需要为 提供一个显式类型go，这需要作用域类型变量。
最后，返回您的原始代码：
ghci> let randShuffleST :: forall a e i g. Ix i => (forall s. MArrayE a e (ST s))
ghci| -> a i e
ghci| -> g
ghci| -> (a i e, g)
ghci| randShuffleST evidence arr gen = runST $ go evidence
ghci| where go :: MArrayE a e (ST s) -> ST s (a i e,g)
ghci| go MArrayE = do _ <- getBounds arr
ghci| return (arr, gen)
ghci|
ghci> -- Hooray again! But...
现在，正如我一开始所说，还有一个问题需要解决。在上面的代码中，永远不会有一种方法可以构造一个 type 的值forall s. MArrayE a e (ST s)，因为forall s. MArray a e (ST s)constraint 约束是不可满足的。出于同样的原因，在您的原始代码中，randShuffleST即使没有遇到类型错误，您也无法编写代码，因为您无法编写返回STArray外部ST.
这两个问题的原因是一样的：anSTArray的第一个参数是它所在的状态线程。的MArray实例STArray是instance MArray (STArray s) e (ST s)，因此您将始终拥有 form 的类型ST s (STArray s i e)。因为runST :: (forall s. ST s a) -> a，跑步会以非法的方式runST mySTArrayAction“泄漏”出来。s调查
runSTArray :: Ix i => (forall s. ST s (STArray s i e)) -> Array i e
和它未装箱的朋友
runSTUArray :: Ix i => (forall s. ST s (STUArray s i e)) -> UArray i e.
你也可以使用
unsafeFreeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
做同样的事情，只要你保证这是你在可变数组上调用的最后一个函数；该freeze函数放宽了这个限制，但必须复制数组。同样，如果您想将数组而不是列表传递给函数的纯版本，您可能还想要
thaw :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e);
usingunsafeThaw在这里可能会是灾难性的，因为您正在传递一个您无法控制的不可变数组！这一切都会给我们带来类似的东西：
ghci> :set -XNoRank2Types -XNoGADTs
ghci> -- We still need -XScopedTypeVariables for our use of `thaw`
ghci> import Data.Array.IArray
ghci> let randShuffleST :: forall ia i e g. (Ix i, IArray ia e)
ghci| => ia i e
ghci| -> g
ghci| -> (Array i e, g)
ghci| randShuffleST iarr gen = runST $ do
ghci| marr <- thaw iarr :: ST s (STArray s i e)
ghci| _ <- getBounds marr
ghci| iarr' <- unsafeFreeze marr
ghci| return (iarr', gen)
ghci|
ghci> randShuffleST (listArray (0,2) "abc" :: Array Int Char) "gen"
(array (0,2) [(0,'a'),(1,'b'),(2,'c')],"gen")
这需要O ( n ) 时间来复制输入的不可变数组，但是通过优化 - 需要O (1) 时间来冻结输出的可变数组，因为STArray和Array在引擎盖下是相同的。
特别是将此应用于您的问题，我们有以下内容：
{-# LANGUAGE FlexibleContexts #-}
import System.Random
import Control.Monad
import Control.Applicative
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import Data.Array.IArray
updateSTRef :: STRef s a -> (a -> (b,a)) -> ST s b
updateSTRef r f = do
(b,a) <- f <$> readSTRef r
writeSTRef r a
return b
swapArray :: (MArray a e m, Ix i) => a i e -> i -> i -> m ()
swapArray arr i j = do
temp <- readArray arr i
writeArray arr i =<< readArray arr j
writeArray arr j temp
shuffle :: (MArray a e (ST s), Ix i, Random i, RandomGen g)
=> a i e -> g -> ST s g
shuffle arr gen = do
rand <- newSTRef gen
bounds@(low,_) <- getBounds arr
when (rangeSize bounds > 1) .
forM_ (reverse . tail $ range bounds) $ \i ->
swapArray arr i =<< updateSTRef rand (randomR (low,i))
readSTRef rand
-- Two different pure wrappers
-- We need to specify a specific type, so that GHC knows *which* mutable array
-- to work with. This replaces our use of ScopedTypeVariables.
thawToSTArray :: (Ix i, IArray a e) => a i e -> ST s (STArray s i e)
thawToSTArray = thaw
shufflePure :: (IArray a e, Ix i, Random i, RandomGen g)
=> a i e -> g -> (a i e, g)
shufflePure iarr g = runST $ do
marr <- thawToSTArray iarr
g' <- shuffle marr g
iarr' <- freeze marr
return (iarr',g')
shufflePure' :: (IArray a e, Ix i, Random i, RandomGen g)
=> a i e -> g -> (Array i e, g)
shufflePure' iarr g =
let (g',g'') = split g
iarr' = runSTArray $ do
marr <- thaw iarr -- `runSTArray` fixes the type of `thaw`
void $ shuffle marr g'
return marr
in (iarr',g'')
同样，您可以将 freeze 替换为Data.Array.Unsafe.unsafeFreezein shufflePure; 这可能会产生加速，因为如果它是一个Array i e. 该runSTArray函数安全地包装unsafeFreeze，所以这不是shufflePure'. （两者是等价的，以一些关于拆分 PRNG 的细节为模。）
我们在这里看到了什么？重要的是，只有可变代码会引用可变数组，并且它保持可变（即，返回内部的东西ST s）。由于shuffle进行了就地洗牌，因此不需要返回数组，只需返回 PRNG。为了构建一个纯接口，我们thaw将一个不可变数组转换为一个可变数组，就地打乱该freeze数组，然后将生成的数组重新转换为一个不可变数组。这很重要：它可以防止我们将可变数据泄漏回纯粹的世界。您不能直接可变地打乱传入的数组，因为它是不可变的；相反，您不能直接将可变混洗数组作为不可变数组返回，因为它是可变的，如果有人可以改变它怎么办？
这不会与我们在上面看到的任何错误发生冲突，因为所有这些错误都来自对runST. 如果我们限制我们对 的使用runST，只有在我们组装了一个纯结果后才运行它，所有内部状态线程都可以自动发生。由于runST是唯一具有 rank-2 类型的函数，因此它是唯一可以产生严重类型怪异的地方；其他一切都只需要您标准的基于类型的推理，尽管可能需要更多考虑以保持s状态线程参数的一致性。
你瞧：
*Main> let arr10 = listArray (0,9) [0..9] :: Array Int Int
*Main> elems arr10
[0,1,2,3,4,5,6,7,8,9]
*Main> elems . fst . shufflePure arr10 <$> newStdGen
[3,9,0,5,1,2,8,7,6,4]
*Main> elems . fst . shufflePure arr10 <$> newStdGen
[3,1,0,5,9,8,4,7,6,2]
*Main> elems . fst . shufflePure' arr10 <$> newStdGen
[3,9,2,6,8,4,5,0,7,1]
*Main> elems . fst . shufflePure' arr10 <$> newStdGen
[8,5,2,1,9,4,3,0,7,6]
成功，终于！（真的太久了。对不起这个答案的长度。）