arrays - 如何将 `getBounds' 与 STArray 一起使用？

Question

我正在尝试使用 STArray 编写 Fisher-Yates 洗牌算法。与我在网上找到的所有其他示例不同，我试图避免使用 native 列表。我只想就地洗牌数组。

这就是我所拥有的:

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

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

我希望我可以依靠 (MArray (STArray s) e (ST s)) instance declaration在 MArray 中定义，以便能够使用 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 S-Z 的答案，但我无法选择它，因为坦白说我并不完全理解它。也许一旦我更好地理解了自己的问题，我将来就会回答自己的问题......谢谢。

Answer 1

您可能不应该在函数中使用runST。 runST 应该在某些内部使用突变但具有纯接口(interface)的计算外部使用一次。您可能希望您的 shuffle 函数(就地对数组进行洗牌)具有类似 STArray s i e -> ST s () 的类型(或者可能是更通用的类型)，然后具有不同的函数如果您需要的话，它使用 runST 来呈现纯接口(interface)(不过，该函数可能需要复制值)。一般来说，ST 的目标是 STRef 和 STArray 永远无法从一次 runST 调用中逃脱，并且用于另一个。

在没有 runST 的情况下为函数推断的类型很好，只是更加多态(它适用于 IO 数组、ST 数组、STM 数组、未装箱数组等)。不过，如果您指定显式类型签名，您将更容易遇到推理错误。