Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!mailrus!ames!amdcad!sun!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: In defence of difference-lists.
Keywords: Difference-lists, Dataflow analysis, Program transformation.
Message-ID: <542@quintus.UUCP>
Date: 14 Oct 88 23:16:57 GMT
References: <3002@mulga.oz>
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 36

In article <3002@mulga.oz> harald@mulga.oz (Harald Sondergaard) writes:
[a lot of sensible things about difference lists]

I would like to suggest that most of the trouble comes from trying
to form a single data structure Front\Back and think of this as a
list in its own right.  If instead you think in terms of
"difference PAIRS" -- that is, pairs of arguments to a relation
which makes a statement about the difference between them -- you
run into less trouble (or at any rate I do).

For example, suppose we want to express
	double(X, Y) :- append(X, X, Y)
in terms of differences.  I would _think_ and write

	%   double(X0,X, Y0,Y)
	%   is true when Y0\Y = (X0\X)<>(X0\X)

	double(X0,X, Y0,Y) :-
		append(DX, X, X0),
		append(DX, Y1, Y0),
		append(DX, Y,  Y1).

and would start my transformation from that, arriving at

	double(X0, X, Y0, Y) :-
		double(X0, X, Y0, Y1, Y1, Y).

	double(X, X, Y, Y, Z, Z).
	double([E|X1], X, [E|Y1], Y, [E|Z1], Z) :-
		double(X1, X, Y1, Y, Z1, Z).

without any false steps.

Using difference pairs rather than "difference lists" also tends to
result in more efficient programs, as you aren't all the time unpacking
Front\Back terms and building new ones.