20

私はHaskellで循環バッファを必要とする小さなコンセプトプロジェクトに取り組んでいます。O（1）回転の配列を使用してバッファーを作成できましたが、もちろん挿入/削除にはO（N）が必要です。挿入と削除にO（1）がかかるように見えるリストを使用する実装を見つけましたが、左右のリストを維持するため、回転時に特定の境界を越えるとO（N）時間がかかります。命令型言語では、O（1）の挿入、削除、およびローテーションを使用して、二重にリンクされた循環バッファーを実装できます。Haskellのような純粋な関数型言語ではこれは不可能だと思いますが、私が間違っているかどうか知りたいです。

4

3 に答える 3

11

償却されたO（1）操作を処理できる場合は、おそらくData.Sequenceコンテナー・パッケージまたはData.Dequeueデキュー・パッケージのいずれかから使用できます。前者はフィンガーツリーを使用し、後者は岡崎の純粋関数型データ構造（以前のバージョンはオンライン）の「Banker'sDequeue」を使用します。

于 2010-02-08T16:52:40.127 に答える
6

モナドを使用すると、STHaskellで命令型アルゴリズムを記述して実行できます。二重リンクリストの可変ポインタにSTRefsを使用できます。

を使用して記述された自己完結型アルゴリズムは、を使用しSTて実行されrunSTます。異なる実行では、データ構造（、、..）runSTを共有できない場合があります。STSTRefSTArray

アルゴリズムが「自己完結型」ではなく、使用の合間に実行されるIO操作でデータ構造を維持する必要がある場合は、モナドでアルゴリズムstToIOにアクセスするために使用できます。IO

これが純粋関数型であるかどうかについては、そうではないと思いますか？

于 2010-02-08T16:30:54.473 に答える
3

（二重リンクリストについて言及したので）これよりも少し複雑なものが必要になるかもしれませんが、おそらくこれが役立つでしょう。mapこの関数は、可変サイクリックリストのように機能します。

mapOnCycling f = concat . tail . iterate (map f)

次のように使用します：

*Main> (+1) `mapOnCycling` [3,2,1]

[4,3,2,5,4,3,6,5,4,7,6,5,8,7,6,9,8,7,10,9...]

そして、これがmapAccumLのように機能するものです。

mapAccumLOnCycling f acc xs = 
    let (acc', xs') =  mapAccumL f acc xs
     in xs' ++ mapAccumLOnCycling f acc' xs'

とにかく、データ構造が正確に「実行」できるようにするために必要なことについてさらに詳しく説明したいのであれば、私はそれについて聞くことに本当に興味があります。

編集：camccannが述べたように、これを使用できますData.Sequence。これは、ドキュメントによると、シーケンスの左側と右側の両方に要素を表示または追加するために、O1時間の複雑さ（O1償却時間などがありますか？）を与えるはずです。 、および途中で端を変更します。これで必要なパフォーマンスが得られるかどうかはわかりません。

「現在の場所」をシーケンスの左端として扱うことができます。ここでは、シーケンスに沿って前後にシャトルし、値の無限のリストを生成します。コンパイルされない場合は申し訳ありませんが、現時点ではGHCを使用していません。

shuttle (viewl-> a <: as) = a : shuttle $ rotate (a+1 <| as)
    where rotate | even a    = rotateForward
                 | otherwise = rotateBack
          rotateBack (viewr-> as' :> a')    = a' <| as'
          rotateForward (viewl-> a' <: as') = as' |> a'
于 2010-02-10T02:42:22.843 に答える