1

这是我之前提出的问题的后续。我想知道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
4

1 回答 1

7

是的，在 GHC 中它是 O(1)。从 s 读取和写入IORef的内容与实现中其他所有内容用作数据表示的指针完全相同。事实上，你可以从它的类型知道它对它writeIORef的数据没有什么特别的：

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

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

于 2016-06-05T17:48:51.513 回答