問題タブ [finger-tree]

単調な優先度キューに次のものを含めることは可能ですか?

1. 最も優先度の高いアイテムを見つけて削除する場合は O(1)、
2. 与えられた優先度が他のすべてのアイテムよりも低いと仮定してアイテムを挿入するための O(1)、
3. 仮定なしでアイテムを挿入および削除するためのO(log n)?

リンクされたリストを使用して、挿入と削除が O(n) に許可されているかどうかを知っています。スキップリストも考えました。ただし、最悪の場合、項目の挿入と削除は O(n) です。

Decrease-key は必要ありません。

時間の経過とともにバージョンとブランチを進化させることができるエンティティ (ファイルまたはライブラリ/パッケージなど) が与えられ、バージョンを介してエンティティの特定のインスタンスに移動できるようにする最適化されたデータ構造を探します。

たとえば（少し不自然な例）、次のようなエントリが与えられます。

私は、そのようなものが既に存在しているのではないかと考えています (パッケージ管理またはソース コード管理は、上記のアクセス セマンティクスと同様のものを利用しているため)。

上記のメモリ内データ構造を探していましたが、最新/最古のアクセス時間は良好ですが、挿入/削除速度も下降しています。

残忍な力のアプローチでは、バージョンを持つことができるすべてのブランチに対してMin Max ヒープを使用して上記を実装できると思います。

とはいえ、もっと良いものがすでにあるかもしれません。これらのタイプのものの通常のソースであるRedissonもチェックしましたが、上記のデータ構造の明示的な実装があるかどうかはわかりませんでした

上記の DSL は私が独自に作成したものであり、おそらく穴もいくつかあるため、この種のデータ アクセスに適した DSL/API があれば、それも学びたいと考えています。

Hinzeによる (Haskell) 論文(このブログも参照) で説明されているように、2 ～ 3 個のフィンガー ツリーで遊んでみたいと思いました。

今、viewl関数を機能させることができません。型の不一致について不平を言っています:

FingerTree<'a> が必要ですが、FingerTree> が指定されています。

''a' と 'Node<'a>' FingerTree を統合すると、結果の型は無限になります。

以前にこのエラーが発生しましprependたが、関数に完全な型情報を追加することで解決できました。

これではviewl十分ではないようですので、関数の途中に型を追加してみました (コメントを探してください)。うまくいきませんでした。

私はエラーとそれがどこから来ているのかを理解しています。誰でもこれを機能させる方法を教えてもらえますか? 私見、そうでなければprependコンパイルもできないので、それは可能であるはずです。たぶん、このようなトリックが役立ちますか？（それは理解できませんが）。

PS:ブラウザで遊んでみるためのコードもFsSnipに置きました。

通常、インスタンスのパフォーマンスは非常に良好ですApplicative。Data.Sequenceほとんどすべての方法は、時間と空間において徐々に漸近的に最適化されます。つまり、完全に強制/実現された入力が与えられると、漸近的に最適な時間とメモリ常駐で結果の任意の部分にアクセスできます。残りの例外が 1 つあります(<*)。私はまだそれを実装する2つの方法しか知りません:

1. デフォルトの実装

   この実装ではO(|xs| * |ys|)、結果を完全に実現するのに時間とスペースが必要ですが、結果の th 要素だけO(log(min(k, |xs|*|ys|-k)))にアクセスするだけです。k

2. 「モナド」実装

   これにはO(|xs| * log |ys|)時間とスペースしかかかりませんが、増分ではありません。結果の任意の要素にアクセスするには、O(|xs| * log |ys|)時間とスペースが必要です。

私は長い間、私たちのケーキを持って食べることも可能だと信じてきましたが、そこにたどり着くのに十分なほど頭の中でうまくジャグリングすることができませんでした. liftA2そのためには、との実装からのアイデア (ただし、実際のコードではない) の組み合わせが必要なようですreplicate。これはどのように行うことができますか？

rigidify注: のメカニズムのようなものを組み込む必要はありませんliftA2。のような部分は、ユーザー提供のツリーから取得するためreplicateに使用する種類の「剛体」構造のみを確実に生成する必要があります。rigidify

更新 (2020 年 4 月 6 日)

任務完了！私はそれを行う方法を見つけることができました。残念ながら、進行中のすべてを理解するには少し複雑すぎます。また、コードは...かなり不透明です。私は、私が書いた内容の適切な説明に賛成票を投じて受け入れます。また、GitHub での明確化の改善やコメントに対する提案も喜んで受け入れます。

更新 2

Li-Yao Xia と Bertram Felgenhauer には、私のドラフト コードのクリーンアップと文書化を手伝ってくれて、とても感謝しています。理解するのがかなり簡単になり、次のバージョンの に表示されcontainersます。この質問を締めくくる答えが得られればなお良いでしょう。