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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe