1

これは、私が以前に尋ねた質問のフォローアップです。のすべての呼び出しでIORef、受け入れられたソリューションで以下のリストが更新される方法がそうであるかどうか疑問に思っています。おそらく、リストの先頭へのポインターを保持している可能性が高いためだと思います（毎回O（n）になるリスト全体をトラバースしてコピーするのではなく）新しいヘッドへのポインターを変更するだけで、O（1）になるはずです。リスト全体の熱心な評価を防ぎます)。ただし、その低レベルのコードは表示されません。だから、ここで尋ねる：O(1)fetchIORefghc-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 に答える