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.
Interesting discussion. I still think it is the same idea, namely to represent not-yet-known list tails by variables, embedded into two different kinds of languages. \rest->start++rest [start|rest]\rest -- '\' is an infix constructor The differences arise from the different handling of variables and scoping in those languages: - functional languages: explicit, local scopes, variables are bound by injecting values from outside the scope (applying the binding construct to values); scoped expressions can be copied, allowing multiple instantiations of variables - logic languages: implicit, global scopes, variables are bound by finding possible values inside the scope (unifying bound variables); outside of non-determinism/ sets-of-solutions handling, only non-scoped terms can be copied, allowing single instantiation only If current functional language implementations had not abandoned support for reducing under binders, one could float out the binder for a difference list, and get limitations closer to those of logic languages (though binding to values would then become much more unwieldy). If logic languages allowed local binders in terms, one could copy difference lists more easily (though substitution and unification would then involve binders). So, yes, the realization of the idea is different, as are the language frameworks, and the junk in the representations, but the idea is the same. Btw, functional language implementations not reducing under binders also implies that functional difference list operations are not shared to the same extent as logic difference list operations are - copying a closure copies un-evaluated expressions, to be re-evaluated every time the closure is opened with different variable bindings, so the functional representation is not as efficient as the logical one, in most implementations. I can't confirm the reference, but several authors point to this for an early description [CT77] Clark, K.L.; Tärnlund, S,Å: A First Order Theory of Data and Programs. In: Inf. Proc. (B. Gilchrist, ed.), North Holland, pp. 939-944, 1977. To close the circle: I understand that difference lists in Prolog might have been a declarative translation of in-place updating in Lisp lists:-) Claus _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe