2

与我最近关于处理大数据块的问题密切相关，我已经到了需要获取一个大的不可变数据块，使其对某些操作可变，然后在完成后再次使其不可变的地步。

由于我想至少保留纯洁的外观，可变数据将是原始不可变数据的可变副本。作为参考，我正在查看 Real World Haskell 中的Bloom Filter示例，但发现我实际上无法让我的代码在 runST 中运行。

我的数据结构，首先是纯的，然后是不纯的：

import Data.Vector.Unboxed (Vector)
import Data.Vector.Unboxed.Mutable (MVector)

data PixelMap = Bitmap Int Int (Vector Bool)
data MPixelMap s = MBitmap Int Int (MVector s Bool)

然后我只创建了一个基本的 newBitmapM 函数：

newBitmapM :: (Int, Int) -> ST s (MPixelMap s)
newBitmapM (width, height) = MBitmap width height `liftM` MV.replicate (width * height) False

这可以很好地加载到 GHCI 中，但随后我尝试运行它：

> runST $ newBitmapM (15, 15)

<interactive>:78:9:
    Couldn't match type `a' with `PixelMapMutable s'
      `a' is a rigid type variable bound by
          the inferred type of it :: a at <interactive>:78:1
    Expected type: ST s a
      Actual type: ST s (PixelMapMutable s)
    In the return type of a call of `newBitmapM'
    In the second argument of `($)', namely `newBitmapM (15, 15)'
    In the expression: runST $ newBitmapM (15, 15)

这个错误信息对我来说毫无意义。 a, 在类型中定义的 forrunST应该是多态的，因此根本不是“固定的”。任何人都可以对此进行解码以告诉我代码到底有什么问题吗？

4

1 回答 1

6

的完整类型签名runST是forall a. (forall s. ST s a) -> a. 在您提供的具体示例中，forall s. ST s a所有出现的s参数都由 量化forall s，包括s您的 。MPixelMap s事实上，所有的 Haskell 类型参数都必须通过量化在某处引入，只是大多数时候它都是隐式的，a就像runST. 此处参数的范围s仅限于ST s a. a由返回的参数runST包含参数没有意义s，因为范围内不再有这样的s参数！

实际上，这意味着您不能提取任何runST依赖于内部状态参数的东西。这实际上是 ST monad 的核心安全特性。如果函数独立于某个状态，则它是纯函数。类型量化技巧确保runST在外界看来是纯粹的。

s如果从返回的类型中消除 ，则可以使示例代码工作。在可变向量的情况下，freeze正是unsafeFreeze这样做的。您可以通过冻结其状态相关字段来冻结您的位图：

freezeMPixelMap :: MPixelMap s -> ST s PixelMap
freezeMPixelMap (MBitmap width height vec) = 
    Bitmap width height `liftM` V.freeze vec

然后您可以PixelMap随时使用runST.

当然，您可以使用和的不安全版本在不可变/可变向量freeze之间thaw进行转换，而无需复制。通常很容易确定unsafeFreeze没有什么坏事；您只需要确保在 ST 操作中不再使用可变向量。unsafeThaw可能会更棘手，因为您必须确保您的整个程序unsafeThaw没有引用您的不可变向量，因此仅对存在于较小局部范围内的向量有意义。

于 2014-03-28T07:48:01.403 回答