Difference Lists
prolog1-5 and prolog1-6 covered ordinary Prolog lists — [H|T], recursion over them, the everyday tools. This chapter revisits those same lists with a performance question those chapters never raised: what happens when you need to build up a large list by repeatedly concatenating pieces onto it? The naive answer turns out to be genuinely slow — and difference lists are the real, standard technique for fixing that.
The Problem — Naive append/3 Is O(n), and Repeated Appending Is Worse
Every call to append/3 walks the entire first list, one element at a time, before it can even begin producing the combined result — a call on a list of length n costs n steps. That's fine for one call. It becomes a real problem the moment you need to build a list by appending onto it repeatedly inside a loop or a recursive accumulation — say, flattening a list of ten thousand small lists one at a time. Each append call re-walks everything accumulated so far, so the total cost isn't 10,000 cheap steps — it's O(n²), the same quadratic blowup that shows up whenever repeated concatenation is done the naive way in any language.
The Idea — An Open List With a Known "Hole"
A difference list represents a list not as one closed term, but as a pair: the list itself, and a variable marking its own currently-unbound tail — conventionally written List-Hole. For example, [a, b, c | Hole] paired with that same Hole represents the list [a, b, c], but with its tail left deliberately open rather than closed off with [].
The entire point of leaving that tail open: concatenating two difference lists no longer requires walking either one. It's a single unification.
Read this literally: the first difference list is "some list A, whose open tail is B." The second is "some list B, whose open tail is C." Concatenating them means unifying the first list's hole (B) directly with the second list's own list (also written B) — which is the second list, spliced straight into the first one's open tail, for free.
A Concrete Worked Example
H1 — the first list's hole — unifies with L2, the entire second list, so L1 becomes [1, 2, 3, 4, 5 | H2] without a single element of either original list ever being walked or copied. The combined difference list still has an open tail, H2 — concatenation didn't close anything, it just spliced two open lists into one, still open.
Closing a Difference List
An open difference list isn't yet an ordinary Prolog list — closing one just means unifying its remaining hole with []:
Only at this final step does the term become a genuine, closed [1, 2, 3, 4, 5] — indistinguishable at that point from a list built the ordinary way.
| Technique | Cost per concatenation | Cost of N repeated concatenations |
|---|---|---|
| Naive append/3 | O(length of first list) | O(n²) overall |
| Difference lists | O(1) — one unification | O(n) overall |
prolog2-5's Definite Clause Grammars translate every --> rule into ordinary clauses threading a pair of list arguments through the whole grammar — that threaded pair genuinely is a difference list, doing exactly the same job it does here, just generated automatically by DCG notation instead of written out by hand.
[] (or anything else) before every intended concatenation has happened, the list is prematurely closed — any later dl_concat call expecting to splice something into that hole will simply fail to unify, often with no obvious error pointing back at the real cause.
Coding Challenges
Write the dl_concat/3 predicate exactly as shown in the chapter, build two difference lists representing [a, b] and [c, d, e], concatenate them, and close the result to show the final ordinary list [a, b, c, d, e].
📄 View solutionExtend Challenge 1 to concatenate three difference lists together (rather than two) using dl_concat/3 twice, and explain in a comment why this stays O(1) per concatenation regardless of how long each individual list is.
📄 View solutionWrite a short comment demonstrating, with a concrete query, what goes wrong if a difference list's hole is unified with [] before a second dl_concat/3 call tries to splice another list into it.
📄 View solutionChapter 4 Quick Reference
- Naive append/3 costs O(length of the first list) per call — repeated appending in a loop becomes O(n²) overall
- A difference list is represented as List-Hole, where Hole is the list's own currently-unbound tail variable
- dl_concat(A-B, B-C, A-C). — concatenation is one unification (the first hole becomes the second list), genuinely O(1)
- Close a difference list by unifying its remaining hole with []
- DCGs (prolog2-5) generate exactly this pattern automatically via the --> notation's threaded list-pair arguments
- The hole must stay genuinely unbound until deliberately closed — binding it early silently breaks any later concatenation