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 difference list containing [1 2 3] in Clojure with [4 5 6] will prepend the difference list to the argument, producing the list [1 2 3 4 5 6]. Calling it with an empty list would produce just the list [1 2 3]. In Lua, it’s cheap to append an item to a list, but expensive to prepend an item, which is the opposite of lists in LISP, so difference lists in Lua will append the to the argument instead of prepending to it. Also, appending to a list in Lua is a destructive operation, so the argument will be modified. You don’t have to worry about this in LISP, though. We can protect people from side effects by defining an “undl” function that passes in its own list so that the developer can treat difference lists as data structures, possibly never even realizing that they are really sneaky functions.
By the way, if you think about what happens when you have an empty difference list, you’ll realize that since it prepends or appends nothing at all to the argument, it just has to return the argument itself, making it just the identity function.
Here is the code for Clojure, taken from my stack overflow comment on idiomatic ways to prepend a vector in Clojure It’s just 5 one-line functions:
(defn dl
"Return a difference list for a list"
[l]
(fn [x] (concat l x)))
; Return an empty difference list
(def dlempty identity)
(defn undl
"Return a list for a difference list (just call the difference list with nil)"
[aDl]
(aDl nil))
(defn dlcons
"Cons an item onto a difference list"
[item aDl]
(fn [x] (cons item (aDl x))))
(defn dlappend
"Append two difference lists"
[dl1 dl2]
(fn [x] (dl1 (dl2 x))))
Here’s the explanation I give in the stack overflow article:
dl: A difference list is actually a function which concats its own contents with the argument and returns the resulting list. Every time you produce a difference list, you're creating a little function that acts like a data structure.
dlempty: Since a difference list just concats its contents to the argument, an empty difference list is the same thing as the identity function.
undl: Because of what difference lists do, you can convert a difference list to a normal list just by calling it with nil, so this function isn't really needed; it's just for convenience.
dlcons: conses an item to the front of the list -- not totally necessary, but consing is a common enough operation and it's just a one-liner (like all of the functions, here).
dlappend: concats two difference lists. I think its definition is the most fun -- check it out! :)
You can see this code in action with this:
(undl (dlappend (dl '(1 2 3)) (dl '(4 5 6))))
which returns:
(1 2 3 4 5 6)
This also returns the same thing:
((dl '(1 2 3)) '(4 5 6))
#The Lua Code
And now, I’ll take a bit of a different approach for Lua. In Lua, it’s cheap to add an item to the end of a list, but this destructively modifies the list, so I’ll define a difference list as a function that takes a table, appends its items to the table, and returns the table. Also, I’ll define a difference list constructor using varargs, so that it can take items that can optionally be other difference lists. That way, there can just be 3 functions: dl.un which returns a list of all of the elements in the difference list, dl, which serves as the dlempty, dlcons, and dlappend functions, above, and dl.table, which functions like dl above (letting you wrap a whole table in a difference list). I'm also adding dl.is which returns whether or not an object is a difference list. Using these, you can construct a difference list like this:
dl(1, dl(2, 3), dl.table({4, 5, 6}), 7)
and calling dl.un with it, like this dl.un(dl(1, dl(2, 3), dl.table({4, 5, 6}), 7)), would give you this table:
{1, 2, 3, 4, 5, 6, 7}
To allow dl to handle both difference lists and elements, I need to be able to identify what's a difference list. Functions can't have properties, so I’ll use a trick and store them in a weak keyed table. Here’s that difference list code!
local diffLists = setmetatable({}, {__mode = 'k'})
local function isDiffList(obj) return diffLists[obj] end
local function undl(l) return l({}) end
local function dl(self, ...)
local items = {...}
local function f(buf)
for i = 1, #items do
if isDiffList(items[i]) then
items[i](buf)
else
buf[#buf + 1] = items[i]
end
end
return buf
end
diffLists[f] = true
return f
end
local function dltable(t) return dl(unpack(t)) end
return setmetatable({table = dltable, un = undl, is = isDiffList}, {__call = dl})
You can use this with Lua 5.1, like this (for 5.2, change unpack to table.unpack):
dl=require('dlists')
print(table.concat(dl.un(dl(1,dl(2,3),dl.table({4,5,6}),7)), ', '))
You can do difference lists with a variety of backing data structures and in a variety of languages. They're really useful -- I use them all the time. Hopefully this will inspire other people to explore using them in other languages besides just Clojure and Lua.
-- Bill