Что такое DList?

Это список различий в духе "Список различий как функции".

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)

Списки различий представляют собой спископодобную структуру данных, поддерживающую операции добавления O(1).

Добавление и другие операции, которые изменяют список, представлены через функциональную композицию функций модификации, а не путем прямого копирования списка.

Пример из библиотеки dlist Haskell:

-- 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, Новое представление списков и его применение к функции «обратно», Р. Джон Хьюз, 1984 г., где он предлагает представлять списки как функции и добавлять их как композицию функций, что позволяет, например, реверс для работы в линейном времени. Из бумаги:

Это тип данных в неканоническом пакете scalaz, полезный для типизированных списков с константами. временной доступ на обоих концах. (Хитрость заключается в том, чтобы погуглить «scala» И «dlist».)

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

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