haskell - 如何在 ST monad 中创建基于向量的新数据类型

Question

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

因为我想至少保留纯粹的外观，所以可变数据将是原始不可变数据的可变副本。作为引用，我正在查看 Bloom Filter Real World Haskell 中的示例，但发现我实际上无法让我的代码在 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，在 runST 的类型中定义，应该是多态的，因此根本不是“固定的”。任何人都可以对此进行足够的解码以告诉我代码的真正问题是什么吗？

Answer 1

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 才有意义存在于一个小局部范围内的向量。