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

Question

与我最近关于处理大型数据块的问题密切相关,我已经达到了这样的程度,即我需要采用一个大的不可变数据块,使其对某些操作变得可变,然后在完成后再次使其变为不可变.

由于我想保留至少纯度的外观,可变数据将是原始不可变数据的可变副本.作为参考,我正在查看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,在类型中定义的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由归国PARAM 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生活在一个小的局部范围内的向量才有意义.