list - DList とは何ですか?

Question

これについてグーグルで調べてみましたが、得られたのはマイナーな有名人に関する話だけでした. ドキュメントが不足しているため、DListとは何ですか?

Answer 1

これは、 「関数としての差分リスト」の行に沿った差分リストです。

scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9))
l1: List[Int] = List(1, 2, 3)
l2: List[Int] = List(4, 5, 6)
l3: List[Int] = List(7, 8, 9)

効率的なプリペンド:

scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

非効率的な追加。これにより、中間リスト (l1 ++ l2) が作成され、次に ((l1 ++ l2) ++ l3) が作成されます。

scala> l1 ++ l2 ++ l3  // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

DList追加を保存し、1 つの完全なリストを作成するだけでよく、以下を効果的に呼び出します。

scala> List(l1, l2, l3) reduceRight ( _ ::: _) 
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)

Answer 2

差分リストは、O(1)追加操作をサポートするリストのようなデータ構造です。

追加、およびリストを変更するその他の操作は、リストを直接コピーするのではなく、変更関数の関数構成によって表されます。

Haskell の dlist ライブラリからの例:

-- Lists as functions
newtype DList a = DL { unDL :: [a] -> [a] }

-- The empty list
empty       = DL id

-- The append case: composition, a la Hughes
append xs ys = DL (unDL xs . unDL ys)

-- Converting to a regular list, linear time.
toList      = ($[]) . unDL

この手法は、少なくともHughes 84にまでさかのぼります。リストの新しい表現と関数 "reverse" への適用、R. John Hughes、1984 年。逆に線形時間で実行します。紙から：

---

---

Answer 3

これは non-canonical scalazパッケージのデータ型で、両端で一定時間アクセスする型付きリストに役立ちます。(トリックは、「scala」と「dlist」をグーグルで検索することです。)

Answer 4

scalazのプロジェクトページから:

DList は、一定時間の追加/前置操作で同じ型の要素を表すためのデータ型です。