什么是数据列表?

这是一份不同的清单 "Difference List as functions"

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)

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)

O(1) 追加操作。

Append和其他修改列表的操作通过修改函数的函数组合来表示,而不是直接复制列表。

例如,来自 Haskell's dlist library

-- 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”中的应用 ,右。johnhughes,1984,其中,他建议将列表表示为函数,并将其附加为函数组合,例如允许在线性时间内运行reverse。来自报纸:

它是一种非规范的数据类型 scalaz

从 project page of scalaz :