[Haskell-cafe] Reference for technique wanted

[Derek Elkins]

On Sun, Oct 31, 2010 at 9:02 PM, wren ng thornton <wren at freegeek.org> wrote:
> On 10/31/10 7:10 PM, Derek Elkins wrote:
>>
>> Well, you can get "A Novel Representation of Lists and Its Application
>> to the Function 'Reverse'" by John Hughes online published in 1986
>> which is referenced by Wadler's 1987 "The Concatenate Vanishes" and
>> references Richard Bird's 1984 paper "Transformational programming and
>> the paragraph problem" though I'd be quite surprised if that was the
>> first place the representation appeared in print.
>
> Barring the "worse than useless" appellation, the technique has been around
> in logic programming (and classic Lisp, IIRC) for a few decades longer. I've
> always heard it referred to as part of the folklore of logic/functional
> programming though, so I'm not sure of any earlier print references
> off-hand.

I agree that difference lists have been around quite a bit longer, but
they are something different.

> (Though I find it curious that you think the logic version is so
> different...)

I'm curious as to how you find them similar.  Beyond both of them
being ways to get fast appends in a declarative language, they have no
similarities.  To begin, Prolog is a first order language so it
clearly can't represent functional lists.  Meanwhile, difference lists
rely on, at least, single assignment variables which Haskell does not
have as a language feature so Haskell can't represent difference lists
outside of a monad.  The use of logic variables requires a "linear"
use of a difference list within a branch of non-deterministic
computation, i.e. difference lists are not persistent.  Functional
lists clearly are.  As a simple example, if xs is a functional list, I
can return a pair (xs . ys, xs . zs), if I tried to do that with
difference lists I would be unifying ys and zs.  If I -really- wanted
to do that with difference lists I would have to use a difference list
copy predicate to do it.  Functional lists are an opaque data
structure.  If I want to know what the head of a functional list is, I
have to first turn it into a real list and then take the head.  With
difference lists, I can just look at the head, and this is cheap and
easy.  Both representations have junk, though I'm inclined to say the
functional representation has quite a bit more.  At any rate, the junk
is rather different.  The junk of a the functional representation is
any [a] -> [a] function that can't be put into the form (xs ++) for
some list xs.  For example, reverse.  Difference lists are pairs of
lists where the latter is a suffix of the former.  The junk in the
typical representation, i.e. just pairs of lists, are pairs that don't
meet that criterion.  The idea behind difference lists is to represent
the list xs as the pair (xs ++ ys, ys), i.e. xs ++ ys - ys = xs is
where the name "difference list" comes from.  One way of motivating
the functional representation is that it is nothing more than the
natural embedding of the list monoid into its monoid of endofunctions;
for every set X, X -> X is a monoid, and for every monoid (M,*,1),
curry (*) is a monoid homomorphism from M to (M -> M).  I'm unsure how
to apply either of these views to the other representation.  In fact,
difference lists are nothing more than the normal imperative way of
handling appends quickly for singly-linked lists, with NULL replaced
by an unbound variable.

To simplify, the difference in persistence between the two
representations is enough to consider them very different as it makes
a dramatic difference in interface.