list - 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（无论如何这是错误的，因为它实际上应该是原子 nil: []）Rest。

现在的想法是始终跟踪尚未实例化的尾部，这是一个单一的逻辑变量。通过再次实例化这个变量到一个列表，它的尾部还没有被实例化，并且你再次单独跟踪它的尾部，你总是可以附加更多的元素，在时间上独立于原始列表已经达到的长度。

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