¿Qué es una DList?
Intenté buscar esto en Google, pero todo lo que obtuve fueron historias sobre celebridades menores. Dada la falta de documentación, ¿qué es un DList?
4 answers
Es una Lista Diferente, a lo largo de las líneas de "Lista de diferencias como funciones"
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)
Antepasado eficiente:
scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
Appending ineficiente. Esto crea una lista intermedia (l1 ++ l2), luego ((l1 ++ l2) ++ l3)
scala> l1 ++ l2 ++ l3 // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
DList almacena los anexos, y solo necesita crear una lista completa, invocando efectivamente:
scala> List(l1, l2, l3) reduceRight ( _ ::: _)
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-07-28 13:53:32
Las listas de diferencias son una estructura de datos similar a una lista que admite O(1) las operaciones de anexar.
Append, y otras operaciones que modifican una lista se representan a través de la composición de funciones de las funciones de modificación, en lugar de copiar directamente la lista.
Un ejemplo, de La biblioteca dlist de 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
La técnica se remonta al menos a Hughes 84, Una novedosa representación de listas y su aplicación a la función "reverse" , R. John Hughes, 1984., donde, propone representar listas como funciones, y anexar como composición de funciones, lo que permite, por ejemplo, invertir para ejecutar en tiempo lineal. Del documento:
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-06-11 16:46:39
Es un tipo de datos en el paquete no canónico scalaz, útil para listas escritas con acceso en tiempo constante en ambos extremos. (El truco es buscar en Google "scala "Y"dlist".)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-07-28 11:48:06
De la página del proyecto de scalaz :
DList, un tipo de datos para representar elementos del mismo tipo con tiempo constante anexar/anteponer operaciones.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-05-02 05:38:25