Qu'est-ce qu'un DList?

Question

J'ai essayé de googler pour cela mais tout ce que j'ai eu étaient des histoires de célébrités mineures. Compte tenu du manque de documentation, qu'est-ce qu'un DList?

Answer 1

Il est une autre liste, le long des lignes 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) 

appending efficace:

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

appending inefficiente. Cela crée une liste intermédiaire (++ l1 l2), puis ((++ l1 l2) ++ l3)

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

DList magasins les Juxtapose, et n'a besoin que de créer une liste complète, invoquant efficacement:

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

Answer 2

Il s'agit d'un type de données dans le package non-canonique scalaz, utile pour les listes typées avec un accès constant aux deux extrémités. (L'astuce est de google pour "scala" ET "dlist".)

Answer 3

De l'project page of scalaz:

dlist, un type de données pour représenter des éléments du même type avec des opérations append/de PREPEND à temps constant.

Answer 4

listes de différence sont une structure de données liste de type qui prend en charge O (1) ajouter des opérations.

Ajout, et d'autres opérations qui modifient une liste sont représentées via la fonction de composition des fonctions de modification, plutôt que de copier directement la liste.

Un exemple 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 technique remonte au moins à Hughes 84, Une nouvelle représentation des listes et son application à la fonction "inverse", R. John Hughes, 1984. , où, il propose de représenter les listes comme des fonctions, et d'ajouter comme composition de fonction, permettant par exemple inverser pour fonctionner en temps linéaire. Extrait du document:

---

---