Che cos'è un DList?

Question

Ho provato su google per questo, ma tutto ciò che ho ottenuto sono state storie di celebrità minori. Data la mancanza di documentazione, che cos'è un DList?

Answer 1

Si tratta di un elenco diverso, lungo le linee di "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 Efficiente:

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

inefficiente accodamento. Questo crea una lista intermedia (l1 ++ l2), poi ((l1 ++ l2) ++ L3)

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

DList memorizza fino alle aggiunge, e ha solo bisogno di creare un elenco completo, efficace invocando:

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

Answer 2

È un tipo di dati nel pacchetto scalaz non canonico, utile per le liste digitate con accesso a tempo costante alle due estremità. (Il trucco è google per "scala" AND "dlist".)

Answer 3

Dal project page of scalaz:

dlist, un tipo di dati per rappresentare elementi dello stesso tipo con le operazioni di accodamento/prepend tempo costanti.

Answer 4

liste differenza sono una struttura di dati lista-like che supporta operazioni O (1) accodamento.

Accoda e altre operazioni che modificano un elenco sono rappresentate tramite la funzione di composizione delle funzioni di modifica, piuttosto che copiare direttamente l'elenco.

Un esempio, da 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 tecnica risale almeno al Hughes 84, Una nuova rappresentazione di liste e la sua applicazione alla funzione "reverse", R. John Hughes, 1984. , dove, propone rappresentazioni di liste come funzioni, e aggiunge come composizione di funzioni, permettendo ad es invertire per correre in tempo lineare. Dalla carta:

---

---