Prolog:列表和差异列表的图表示

Question

我一直在试图理解一个列表和一个不同列表在图结构中的样子。我理解[a1，a2，a3，..an|[]等列表的基本结构。

​

​

但我不明白一个不同的列表会是什么样子？

例如，1,2,3,4-3,4

Answer 1

X-Y是术语-(X, Y)。因此，[1,2,3,4]-[3,4]主要是一对两个列表，每个列表都可以很容易地显示在树中，就像显示的那样。

现在考虑一下表单[E1,E2,...,E_n|Rest]的列表，即最后的尾尚未实例化。同样，您可以很容易地在树中显示这一点，就像显示的那样，只需将end-of-list替换为Rest (无论如何，这是错误的，因为它实际上应该是原子0：[])。

现在的想法是始终跟踪尚未实例化的尾，这是一个单一的逻辑变量。通过实例化此变量，再次将其实例化到其尾部尚未实例化的列表中，并再次单独跟踪其尾部，您始终可以在与原始列表已经达到的长度无关的时间内追加进一步的元素。

您可以将这样的列表及其最后的尾表示为对[E1,E2,...,E_n|Rest]-Rest，但实际上最好使用两个不同的参数并将列表及其未实例化的最终尾传递为两个单独的参数(explanation)。