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?

Answer 1

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

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:

---

---

Answer 3

From the project page of scalaz:

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

Answer 4

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)