列表的 IORef 处理

Question

这是我之前提出的问题的后续。我想知道在 fetch 的每次调用中，接受的解决方案中下面 IORef 中更新列表的方式是否是 O(1)。我怀疑这是因为 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)。从 IORefs 读取和写入的内容与实现中的其他所有内容用作数据表示的指针完全相同。实际上，您可以 仅从 writeIORef 的类型 知道它对其数据没有任何特殊处理：

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

因为a是完全不受约束的，writeIORef不能检查数据，特别是不能遍历你交给它的任何列表。（这不太令人信服——运行时可以做任何它喜欢的事情，即使是不受约束的类型，你可能认为 writeIORef 是一个运行时原语——但无论如何在这种情况下它都是真的。）

列表的 IORef 处理

IORef handling of list

haskell

time-complexity

ioref