Demystifying DList

When you ignore the fact that it's implemented with functions, it seems that a difference list is a binary tree of lists. Appending two difference lists is just creating a new root and making them the new children of the root. When you convert a difference list into a list, you're flattening the tree into a list of sublists, and then flattening those sublists into a list.

The most interesting part is that the tree is made of closures that capture the sublists, and flattening the tree of sublists into a list of sublists and then into just a list, is just function application done on all those closures.

If you're unfamiliar with Haskell syntax, note that (xs ++) is shorthand for (\ys -> xs ++ ys), which, in Lisp syntax, would be like (lambda (ys) (append xs ys)). The notation (f . g) is shorthand; "(f . g) x" is equivalent to "f (g x)", so just writing "(f . g)" is the same as a function that returns the result of applying g and passing the result to f. Finally, "$" is the function application operator, so "f $ x" is equivalent to "f x", and "f $ g x" is equivalent to "f (g x)"; its only purpose is to reduce the number of parentheses you have to write when applying lots of functions.