I thought this was an interesting data structure, which is mainly used by Haskell and Prolog programmers.
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.
Well, self-correction: not a binary tree in the traditional sense, since only the leaf nodes contain the elements. It's that each of the two tree pointers either points to another subtree, or to the start of a list, but not both.
3 comments
[ 3.3 ms ] story [ 14.3 ms ] threadWhen 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.
So, a difference list is a rope, but encoded with closures instead of explicit trees.