A difference list is really a layer on top of another data structure that you can use for cheap appending, later extracting the underlying data structure when you’re done with all the appending. It’s kind of like an array buffer or a string buffer and it’s very simple to implement. You can back a difference list with any data structure that allows you to add an item cheaply to the start or end.
Here are two examples, one using cons-lists in Clojure and one using tables in Lua. Appending two Clojure cons-lists and Lua tables is normally a O(n) operation, making it O(n^2) for appending multiple lists or tables. Difference lists let you append in O(1) and produce the final list or table in O(n), regardless of how many difference lists you’ve appended together.
One interesting thing about difference lists is that a difference list is really a function. Calling it with an argument extracts the backing list from the difference list by appending or prepending to the argument, so calling a