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）。从 IORef 读取和写入的内容与实现中用作数据表示的其他所有内容完全相同的指针。事实上，你可以从writeIORef的类型知道它对其数据没有任何特殊作用：

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

由于a完全不受约束，因此writeIORef无法检查数据，特别是无法遍历您提交的任何列表。（这不太令人信服 - 即使使用不受约束的类型，运行时也可以做任何它喜欢的事情，你可能会认为writeIORef是运行时原语 - 但