What is a DList?

Question

I tried googling for this but all I got were stories about minor celebrities. Given the lack of documentation, what is a DList?

Glimp

I only clicked on this question for a chance to make a facetious comment about celebrities. But it was already there in the question... +1 – Trevethick

Answer 1

It's a Difference 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)

Bunker

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? – Thermomotor

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) – Bunker

Answer 2

Difference lists are a list-like data structure that supports O(1) append operations.

Append, and other operations that modify a list are represented via function composition of the modification functions, rather than directly copying the list.

An example, from 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

The technique goes back at least to Hughes 84, A novel representation of lists and its application to the function "reverse", R. John Hughes, 1984., where, he proposes representing lists as functions, and append as function composition, allowing e.g. reverse to run in linear time. From the paper:

---

---

Niles

It would be good to add an a -> DList a example: singleton = \a -> DL ((:) a) – Xylene

Answer 3

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".)

Nu

I assumed it was non-scala-specific – Glimp

DList were found to overflow the stack and were deleted from Scalaz: code.google.com/p/scalaz/issues/detail?id=19 – Fermata

@WillSargent DList was added back to Scalaz in 2011 github.com/scalaz/scalaz/commit/… – Thermochemistry

Answer 4

From the project page of scalaz:

DList, a data type for representing elements of the same type with constant time append/prepend operations.

Monstrosity