列表的IORef处理

Question

这是我之前问过的一个question的后续。我想知道在下面的IORef中更新的方式列表在接受的解决方案中是否是O(1)，在fetch的每个调用中都是这样。我怀疑这是因为IORef可能只是保留一个指向列表头的指针(而不是每次遍历和复制整个列表，即O(n) )。只是改变指针到新的头部应该是O(1)，并应防止急于评估整个列表)。但是，ghc-core不会显示低级别的代码。所以，在这里问：

mklstream :: L.ByteString -> (IO S.ByteString -> IO r) -> IO r
mklstream lbs sink = do
  ref <- newIORef (L.toChunks lbs)
  let fetch :: IO S.ByteString
      fetch = do chunks <- readIORef ref
                 case chunks of
                   [] -> return S.empty
                   (c:cs) -> do writeIORef ref cs
                                return c
  sink fetch

Answer 1

是的，在GHC中是O(1)。从IORef中读取和写入的内容与实现中的其他所有元素作为数据表示使用的指针完全相同。实际上，您可以从writeIORef的类型中了解到，它对其数据没有什么特殊的作用：

writeIORef :: IORef a -> a -> IO ()

因为a是完全不受约束的，所以writeIORef不能检查数据，特别是不能遍历传递给它的任何列表。(这并不完全令人信服--运行时可以做它喜欢的任何事情，即使是不受约束的类型，而且您可能相信writeIORef是一个运行时原语--但在这种情况下，事实证明是正确的。)