[Haskell-cafe] Reference for technique wanted

[Richard O'Keefe]

On 1/11/2010, at 2:02 PM, wren ng thornton wrote:
> 
> 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.
> 
> (Though I find it curious that you think the logic version is so different...)


The logic programming version
  uses a SINGLE data structure for lists and differences, so that
  + "converting" from the difference representation to the "plain" representation
    involves no more than binding a single (logic) variable
  + does not involve ANY overheads compared with building a list directly
  + can easily be traversed while still under construction, as in the
	queue([s(...s(z)...), [X1,...,Xn|Hole], Hole)
    representation for a queue, which allows O(1) worst case enqueue and dequeue.
	enqueue(X, queue(N,List,[X|Hole]),    queue(s(N),List,Hole)).
	dequeue(X, queue(s(N),[X|List],Hole), queue(N,List,Hole)).
   (Fernando Pereira taught me this one.)
  - can only be used once, after which the "hole" has *gone*.

The closure version
  uses TWO data structures, so that
  - converting from the difference representation to the plain list representation
    involves building a whole new data structure at O(n) time and space cost
  - requires building closures which have no other reason to exist, which may
    retain references to data that would otherwise be dead
  - cannot be traversed while under construction
  + can be used as many times as you want

I don't see the "closure" technique used in logic programming at all.