On Sun, Oct 31, 2010 at 9:02 PM, wren ng thornton <w...@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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
