[Haskell-cafe] Reference for technique wanted
ok at cs.otago.ac.nz
Sun Oct 31 22:26:46 EDT 2010
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.
More information about the Haskell-Cafe