A difference list is an abstraction representing a list that supports \(\mathcal{O}\)(1) append and snoc operations, making it useful for replacing frequent applications of ++ such as logging and pretty printing (esp. if those uses of ++ are left-nested).

fromList xs is a DList representing the list xs.

fromList obeys the laws:

toList . fromList = id
fromList . toList = id

This function is implemented with ++. Repeated uses of fromList are just as inefficient as repeated uses of ++. If you find yourself doing some form of the following (possibly indirectly), you may not be taking advantage of the DList representation and library:

fromList . f . toList

More likely, you will convert from a list, perform some operation on the DList, and convert back to a list:

toList . g . fromList

toList xs is the list represented by xs.

toList obeys the laws:

toList . fromList = id
fromList . toList = id

Evaluating toList xs may “collapse” the chain of function composition underlying many DList functions (append in particular) used to construct xs. This may affect any efficiency you achieved due to laziness in the construction.

apply xs ys is the list represented by the xs after appending ys to it.

\(\mathcal{O}\)(1).

apply obeys the law:

apply xs ys = toList xs ++ ys

empty is a DList with no elements.

empty obeys the law:

toList empty = []

singleton x is a DList with the single element x.

singleton obeys the law:

toList (singleton x) = [x]

cons x xs is a DList with the head x and the tail xs.

\(\mathcal{O}\)(1).

cons obeys the law:

toList (cons x xs) = x : toList xs

snoc xs x is a DList with the initial DList xs and the last element x.

\(\mathcal{O}\)(1).

snoc obeys the law:

toList (snoc xs x) = toList xs ++ [x]

append xs ys is a DList obtained from the concatenation of the elements of xs and ys.

\(\mathcal{O}\)(1).

append obeys the law:

toList (append xs ys) = toList xs ++ toList ys

concat xss is a DList representing the concatenation of all DLists in the list xss.

\(\mathcal{O}\)(length xss).

concat obeys the law:

toList (concat xss) = concat (map toList xss)

replicate n x is a DList of length n with x as the value of every element.

\(\mathcal{O}\)(n).

replicate obeys the law:

toList (replicate n x) = replicate n x

head xs is the first element of xs. If xs is empty, an error is raised.

\(\mathcal{O}\)(1).

head obeys the law:

head xs = head (toList xs)

tail xs is a list of the elements in xs excluding the first element. If xs is empty, an error is raised.

\(\mathcal{O}\)(length (toList xs)).

tail obeys the law:

tail xs = tail (toList xs)

unfoldr f z is the DList constructed from the recursive application of f. The recursion starts with the seed value z and ends when, for some z' : b, f z' == Nothing.

\(\mathcal{O}\)(length (unfoldr f z)).

unfoldr obeys the law:

toList (unfoldr f z) = unfoldr f z

foldr f z xs is the right-fold of f over xs.

\(\mathcal{O}\)(length (toList xs)).

foldr obeys the law:

foldr f z xs = foldr f z (toList xs)

map f xs is the DList obtained by applying f to each element of xs.

\(\mathcal{O}\)(length (toList xs)).

map obeys the law:

toList (map f xs) = map f (toList xs)

intercalate xs xss is the concatenation of xss after the insertion of xs between every pair of elements.

\(\mathcal{O}\)(length xss).

intercalate obeys the law:

toList (intercalate xs xss) = intercalate (toList xs) (map toList xss)