Qu'est-ce qu'une DList?
j'ai essayé de googler pour ça mais tout ce que j'ai eu c'est des histoires sur des célébrités mineures. Étant donné le manque de documentation, qu'est-ce qu'un DList?
4 réponses
la Liste est Différente, le long des lignes de "Différence" Liste des fonctions"
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)
préparation efficace:
scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
ajout inefficace. 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 stocke les annexes, et n'a besoin de créer qu'une liste complète, en invoquant effectivement:
scala> List(l1, l2, l3) reduceRight ( _ ::: _)
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
les listes de différences sont une structure de données de type liste qui supporte O (1) ajouter des opérations.
ajouter, et d'autres opérations qui modifient une liste sont représentées via la composition des fonctions de modification, plutôt que de copier directement la liste.
Un exemple Haskell dlist bibliothèque:
-- 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,, R. John Hughes, 1984., où, il propose de représenter des listes en tant que fonctions, et d'ajouter en tant que composition de fonction, permettant par exemple à l'inverse de fonctionner en temps linéaire. À partir du document:
C'est un type de données dans le non-canonique scalaz paquet, utile pour les listes dactylographiées avec un accès en temps constant aux deux extrémités. (Le truc est de chercher sur google pour "scala"et " dlist".)
DList, un type de données pour représenter des éléments du même type avec des opérations d'ajout/pré-ajout de temps constant.