如何在STArray中使用`getBounds'？

Question

我正在尝试使用STArray编写Fisher-Yates shuffle算法.与我在网上找到的所有其他示例不同,我试图避免使用本机列表.我只想在适当的位置随机播放一个阵列.

这就是我所拥有的:

randShuffleST arr gen = runST $ do
    _ <- getBounds arr
    return (arr, gen)

arr是STArray,gen将是类型的生成器状态(RandomGen g).

我希望我可以依赖MArray中定义的(MArray (STArray s) e (ST s)) 实例声明来使用MArray,getBounds但GHCi无法推断出它的类型randShuffleST.它失败了:

Could not deduce (MArray a e (ST s))
  arising from a use of `getBounds'
from the context (Ix i)
  bound by the inferred type of
           randShuffleST :: Ix i => a i e -> t -> (a i e, t)
  at CGS/Random.hs:(64,1)-(66,25)
Possible fix:
  add (MArray a e (ST s)) to the context of
    a type expected by the context: ST s (a i e, t)
    or the inferred type of
       randShuffleST :: Ix i => a i e -> t -> (a i e, t)
  or add an instance declaration for (MArray a e (ST s))
In a stmt of a 'do' block: _ <- getBounds arr
In the second argument of `($)', namely
  `do { _ <- getBounds arr;
        return (arr, gen) }'
In the expression:
  runST
  $ do { _ <- getBounds arr;
         return (arr, gen) }

有趣的是,如果我像这样删除对`runST'的调用:

randShuffleST arr gen = do
    _ <- getBounds arr
    return (arr, gen)

它编译很好,带有类型签名

randShuffleST :: (Ix i, MArray a e m) => a i e -> t -> m (a i e, t)

.我在Arch Linux上使用GHC 7.4.2.

请在回复中提供明确的类型签名,以帮助我理解您的代码,谢谢.

编辑:我真的很喜欢Antal SZ的答案,但我不能选择它,因为坦率地说我并不完全理解它.也许一旦我更好地理解了自己的问题,我将来会回答我自己的问题...谢谢.

Answer 1

你可能不应该runST在你的功能中使用.runST应该使用一次,在一些内部使用变异但具有纯接口的计算的外部.您可能希望您的shuffle函数(就地将数组混洗)具有类似STArray s i e -> ST s ()(或可能是更通用的类型)的类型,然后具有runST用于呈现纯接口的不同函数(如果您需要)(该函数)虽然可能需要复制值.一般来说,目标ST是STRefs和STArrays永远不会从一次runST调用中逃脱并在另一次调用中使用.

为您的函数推断的类型没有问题runST,只是更多态(它适用于IO数组,ST数组,STM数组,无盒数组等).但是,如果指定显式类型签名,则可以更轻松地使用推理错误.

Answer 2

发生这种情况是因为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必须是a MArray并且我们不关心它具有哪些元素或索引类型(只要它的索引在其中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
    ...

等一下:？这哪儿来from‽我们没有在任何地方提到过这样的类型的变量!答案是,它来自于定义中的.一般来说,有类型(为方便起见,重命名一些类型变量); 当我们在这里使用它时,我们将它限制在类型中.这里发生的事情是,它就像一个lambda(事实上,它是一个lambda),在括号内局部绑定.因此,当返回类型的东西,我们可以统一用---但我们不能统一用,因为在范围上是没有的.在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?runSTsa??ss1

所以错误是公平的:我们声称对于某些特定的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)适用于所有的 s,但我们仍然可以得到一个类型错误.看来,"GHC不支持多态约束箭头左边的" -和在事实上,虽然谷歌搜索周围试图找到这些信息,我发现了一个优秀的博客文章在"主通常是一个功能",它运行到与您相同的问题,解释错误,并提供以下解决方法.(他们也得到了优秀的错误信息"格式错误的类断言",这表明这样的事情是不可能的;这可能是由于GHC版本的不同.)

这个想法是,当我们想要从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> 

现在,只要我们有一个类型的值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的参数列表中,s从evidence被固定为特定值太早,所以我们需要把这个关; (我认为因为推断更高级别的类型很难)我们还需要提供一个显式类型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...

现在,正如我在开头所说,还有一个问题需要解决.在上面的代码中,永远不会有一种构造类型值的方法forall s. MArrayE a e (ST s),因为forall s. MArray a e (ST s)约束约束是不可满足的.出于同样的原因,在原始代码中,randShuffleST即使没有遇到类型错误也无法写入,因为您无法编写返回STArray外部的函数ST.

之所以这两个问题是相同的:一个STArray"第一个参数是国家线程它活在.该MArray例如STArray是instance MArray (STArray s) e (ST s),所以你将永远有各类形式的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);

unsafeThaw在这里使用可能是灾难性的,因为你传递的是一个你无法控制的不可变数组!这一切都会给我们带来类似的东西:

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'')

再次,你可以用Data.Array.Unsafe.unsafeFreezein 替换freeze 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]

成功,终于!(方式太长了,真的.很抱歉这个答案的长度.)