I tried googling for this but all I got were stories about minor celebrities. Given the lack of documentation, what is a DList?
+1
A:
It's a data type in the non-canonical scalaz package, useful for typed lists with constant-time access at both ends. (The trick is to google for "scala" AND "dlist".)
Kilian Foth
2010-07-28 11:48:06
I assumed it was non-scala-specific
oxbow_lakes
2010-07-28 13:14:13
A:
From the project page of scalaz:
DList, a data type for representing elements of the same type with constant time append/prepend operations.
michael.kebe
2010-07-28 11:51:47
+10
A:
It's a Different List, along the lines of "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)
Efficient prepending:
scala> l1 ::: l2 ::: l3
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
Inefficient appending. This creates an intermediate list (l1 ++ l2), then ((l1 ++ l2) ++ l3)
scala> l1 ++ l2 ++ l3 // inefficient
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
DList
stores up the appends, and only needs to create one complete list, effectively invoking:
scala> List(l1, l2, l3) reduceRight ( _ ::: _)
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
retronym
2010-07-28 13:53:32
Isn't prepending regular Scala lists with ::: still linear in the length of the prefixes? Or is there some additional code that exploits their immutability to do better?
Kris Nuttycombe
2010-07-28 16:16:27
With a `DList`, the total operation is still `O(n * m)`, where `n` is number of chunks and `m` is the chunk size. With `++`, the operation is `O(n * n * m)`
retronym
2010-07-28 16:53:12