如何不纯地修改与对象关联的状态？

Question

在Haskell中,我有一个容器,如:

data Container a = Container { length :: Int, buffer :: Unboxed.Vector (Int,a) }

这个容器是一棵扁平的树.它的访问器通过向量(!)执行二进制(log(N))搜索,以便找到index存储的正确存储桶.

(!) :: Container a -> Int -> a
container ! index = ... binary search ...

由于连续访问可能位于同一个存储桶中,因此可以通过以下方式进行优化:

if `index` is on the the last accessed bucket, skip the search

棘手的一点是这last accessed bucket部分.在JavaScript中,我只是不明确地修改容器对象上的隐藏变量.

function read(index,object){

    var lastBucket = object.__lastBucket;

    // if the last bucket contains index, no need to search
    if (contains(object, lastBucket, index))
        var bucket = lastBucket;

    // if it doesn't
    else {
        // then we search the bucket
        var bucket = searchBucket(index,object);

        // And impurely annotate it on the container, so the
        // next time we access it we could skip the search.
        container.__lastBucket = bucket;
    }

    return object.buffer[bucket].value;
}

由于这只是一个优化,结果与所采用的分支无关,我相信它不会破坏参照透明度.在Haskell中,如何不可能修改与运行时值相关联的状态？

〜

我想过两种可能的解决方案.

1. 一个全局的,可变的hashmap,用于链接指向该lastBucket值的指针,并使用unsafePerformIO对其进行写入.但我需要一种方法来获取对象的运行时指针,或者至少是某种类型的唯一ID(如何？).

2. 添加一个额外的领域Container,lastBucket :: Int以及在某种程度上不纯内进行修改(!),并认为该领域内(因为它显然打破引用透明).

Answer 1

使用解决方案（1），我设法得到以下设计。首先，我添加了一个__lastAccessedBucket :: IORef Int按照 @Xic\xc3\xb2 的建议向我的数据类型添加了一个字段：

\n\n

data Container a = Container { \n    length :: Int, \n    buffer :: V.Vector (Int,a), \n    __lastAccessedBucket :: IORef Int }\n

\n\n

然后，我必须更新创建新的函数Container，以便使用以下命令创建新的 IORefunsafePerformIO：

\n\n

fromList :: [a] -> Container a\nfromList list = unsafePerformIO $ do\n    ref <- newIORef 0\n    return $ Container (L.length list) buffer ref\n    where buffer = V.fromList (prepare list)\n

\n\n

最后，我创建了两个新函数，findBucketWithHint一个纯函数，它用猜测搜索索引的存储桶（即您认为它可能在的存储桶），以及一个unsafeFindBucket替换纯函数的函数findBucket需要性能时通过始终使用来最后访问的存储桶作为提示：

\n\n

unsafeFindBucket :: Int -> Container a -> Int\nunsafeFindBucket findIdx container = unsafePerformIO $ do \n    let lastBucketRef = __lastAccessedBucket contianer\n    lastBucket       <- readIORef lastBucketRef\n    let newBucket     = findBucketWithHint lastBucket findIdx container\n    writeIORef lastBucketRef newBucket\n    return $ newBucket\n

\n\n

这样，从unsafeFindBucket技术上讲，它是一个纯函数，具有与原始findBucket函数相同的 API，但在某些基准测试中速度快了一个数量级。我不知道这有多安全以及在哪里可能会导致错误。线程肯定是一个问题。

\n