Что такое DList?

Ответ 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)

Ответ 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., где он предлагает представлять списки как функции и добавлять в качестве составной функции, позволяя, например, назад для запуска в линейном времени. Из статьи:

Ответ 3

Это тип данных в неканоническом пакете scalaz, полезном для типизированных списков с постоянным доступом на обоих концах. (Трюк заключается в google для "scala" и "dlist".)

Ответ 4

На странице страницы проекта scalaz:

DList - тип данных для представления элементов одного и того же типа с постоянными операциями добавления/добавления времени.