Difference Lists
Difference ListsOften algorithm and/or data modelling decisions can have a larger impact on performance than other factors. Difference lists are an example.
Difference lists use the same principle as the Russian Dolls with an extra argument. Just as in that case, they can make for faster processing.
Difference lists use a pair of lists to represent a list:
The first is the full list;
the second is the tail of the first.
For example, to represent [a,b,c] as a difference list pair: [a,b,c|X],
X.
Consider parsing - want to find a noun, say [washing, machine], from the front
of a list [washing,
machine, spinning, out, of, control] and also get the rest of the list [spinning, out,
of, control] for further parsing. A simple fact
and quick unification does the job with a difference list:
noun( [washing, machine | X], X ).
Without the difference list we would need append/3 or a similar predicate to split the list.
See the natural_language files in samples/singles.
