リストの先頭と末尾に2つのビューを持たせることができるリストデータ構造を効率的に実装するにはどうしたらいいですか？ すなわち：Haskellの効率的なキュー
start x = []
end x = reverse start -- []
start1 = [1,2,3] ++ start
end start1 -- [3,2,1]
最後は「逆」を呼び出す単に自動的に逆にされたリストの観点から、指定されたリストを見ずにこれを行うことができるはずです。連結から新しいリストを作成して開始する場合も同様です。
あなたはいつもちょうどData.Sequenceを使用することができます。
純粋に機能的なキューのよく知られた実装は、2つのリストを使用することです。 1つはエンキュー用、もう1つはデキュー用です。エンキューは単にエンキューリストとは対照的です。デキューはデキューリストの先頭をとります。デキューリストが空の場合は、エンキューリストを逆にしてリキューします。 Chris Okasaki氏を参照してください。Purely Functional Datastructures.
この実装ではreverseが使用されますが、この償却された時間コストは漸近的に重要ではありません。それはすべてのエンキューのためにデキューリスト補充のためにΘ（1）の時間負債が発生するように動作します。したがって、デキューの予想時間はエンキューの予想時間の2倍です。これは一定の要因であるため、両方の操作のコストはΘ（1）です。
エフェメリアルに使用されている場合は、そのわずかな*のみ*。アプリケーションが永続性に依存している場合は、キューにアクセスするたびにそのO（n）のケースを実行することが可能です。 – Juliet
@Juliet怠惰とメモを使うと、永続性を保ちながら、償却された境界はまだO（1）です。 – Yuhta
@Yuhtaは、怠惰とメモを使って例を示すことができますか？ – CMCDragonkai
私は実際にハスケルのユーザーではありませんが、償却された一定時間で操作できるHaskellキューを記述するとa blog postが主張しています。 Chris Okasakiの優れたPurely Functional Data Structuresのデザインに基づいています。
Data.Dequeueあなたが探しているのは？
（それはreverseを持っていませんが、あなたはかなり簡単にそれを追加し、作者にパッチを送ることができます。）
ハスケルでは値を変更できません。 'start'は常に空リストになり、' end'は常にその 'reverse'（空のリスト）になります。あなたが州を維持したいなら、あなたは州のモナドを見るべきです。 –
修正：更新によって私は再バインドを意味する。 – TheOne
@Absolute：あなたはそれをHaskellで変更することはできない究極の真実を変えないと言います（IOにもかかわらず）。あなたは物事を再結合することはできません。 –