¿Qué es un DList?

Question

Traté de buscar en Google para esto, pero todo lo que obtuve fueron historias sobre celebridades menores. Dada la falta de documentación, ¿qué es un DList?

Answer 1

Es una lista diferente, a lo largo de las líneas de "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) 

prepending eficiente:

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

ineficiente adjuntas. Esto crea una lista intermedia (L1 L2 ++), entonces ((L1 L2 ++) ++ L3)

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

DList almacena hasta las anexa, y sólo necesita crear una lista completa, invocando de manera efectiva:

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

Answer 2

Es un tipo de datos en el paquete no canónico scalaz, útil para listas tipadas con acceso de tiempo constante en ambos extremos. (El truco es Google de "Scala" AND "DLIST".)

Answer 3

Desde el project page of scalaz:

DList, un tipo de datos para la representación de elementos del mismo tipo con las operaciones append/Prepend de tiempo constantes.

Answer 4

listas de la diferencia son una estructura de datos-lista como que soporta operaciones O (1) append.

Añadir, y otras operaciones que modifican una lista se representan mediante la composición de funciones de las funciones de modificación, en lugar de copiar directamente la lista.

Un ejemplo, de 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 

La técnica se remonta al menos a Hughes 84, Una novela representación de las listas y su aplicación a la función "inverso", R. John Hughes, 1984. , donde, propone representar listas como funciones, y anexar como composición de funciones, permitiendo, por ejemplo, invertir para ejecutar en tiempo lineal. A partir del documento:

---

---