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存储追加，只需要创建一个完整的列表，有效地调用：

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，A novel representation of lists and its application to the function "reverse"，R. John Hughes，1984.，其中，他建议将列表表示为函数，并附加为函数组合，例如反向以线性时间运行。从论文中：

---

---

Answer 3

它是非规范scalaz包中的一种数据类型，对于在两端具有恒定时间访问的类型列表很有用。（诀窍是用谷歌搜索“scala”和“dlist”。）

Answer 4

从scalaz 的项目页面：

DList，一种数据类型，用于表示具有恒定时间附加/前置操作的相同类型的元素。