Was ist ein DList?

Question

Ich habe versucht, dafür zu googeln, aber alles, was ich bekam, waren Geschichten über kleine Prominente. Angesichts der fehlenden Dokumentation, was ist ein DList?

Answer 1

Es ist eine andere Liste, nach dem Vorbild der "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) 

Effiziente Prepending:

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

Ineffiziente Anfügen. Dies schafft eine Zwischenliste (l1 ++ l2), dann ((l1 ++ l2) ++ l3)

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

DList speichert den Appends auf und benötigt nur eine komplette Liste zu erstellen, effektiv Aufruf:

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

Answer 2

Es ist ein Datentyp im nicht-kanonischen scalaz-Paket, nützlich für typisierte Listen mit Konstantenzugriff an beiden Enden. (Der Trick ist für "scala" Google und "DLIST".)

Answer 3

Vom project page of scalaz:

DList, ein Datentyp für Elemente desselben Typs mit konstanter Zeit append/prepend Operationen darstellen.

Answer 4

Difference Listen eine Liste artigen Datenstruktur, die O (1) Operationen unterstützt anhängen.

Append und andere Operationen, die eine Liste ändern, werden über die Funktionszusammensetzung der Änderungsfunktionen dargestellt, anstatt die Liste direkt zu kopieren.

Ein Beispiel von 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 

Die Technik geht mindestens auf Hughes 84, Eine neuartige Darstellung von Listen und ihre Anwendung auf die Funktion "reverse", R. John Hughes 1984 zurück. , wo er vorschlägt, Listen als Funktionen darzustellen und als Funktionszusammensetzung anzufügen, die z umgekehrt, um in linearer Zeit zu laufen. Vom Papier:

---

---