list - Haskell リストの内部表現?

Question

Haskell は、 、 、 など、リストを再帰するためのいくつかの基本的な操作をサポートしていheadます。内部的には、Haskell がリスト データをどのように表現しているのか疑問に思っています。単一リンクのリストの場合、リストが大きくなるにつれて操作にコストがかかる可能性があります。二重にリンクされたリストの場合、4 つの操作はすべて非常に簡単に実行できますが、メモリがいくらか消費されます。いずれにせよ、適切なコードを書くことができるように、それを知ることは私にとって重要です。(ただし、関数型プログラミングの精神は、「どのように行うかではなく、何を行うかを問う」の 1 つであるようです)。tailinitlastinitlastO(1)

Answer 1

リストは ... 単独でリンクされたリストとして表されます。定義は次のように与えられます。

data [] a = [] | a : [a]

次のように書くことができます：

data List a = Empty | Cons a (List a)

メモリ レイアウトは、これによって完全に定義されます。

• コンストラクターはヒープに割り当てられます
• 内部ポリモーフィック フィールドは、割り当てられた他のノードへのポインタです
• 背骨がだるい

したがって、次のような結果になります。

この構造のO(1)もそうheadですが、 orはO(n)ですlast(++)

Haskell のデータ構造に魔法はありません。単純な定義により、複雑さがどうなるか (モジュロ遅延) が完全に明確になります。別の複雑さが必要な場合は、別の構造 (IntMap、Sequence、HashMap、Vector など) を使用してください...

Answer 2

Haskell リストは単独でリンクされているためcons、headとtailは O(1) でありinit、 とlastは O( n ) です。

より良いパフォーマンスが必要な場合は、リストの両端への O(1) アクセスを提供するData.SequenceSeqの型の使用を検討してください。内部的には2 ～ 3 本のフィンガー ツリーを使用します。