了解差异列表 [英] Understanding Difference Lists

问题描述

我正在尝试理解 Prolog 中的差异列表，但我很难真正正确地实现一个，每次我尝试这样做时，我都会得到一个列表列表，但这不是我想要的.我正在尝试实现一个附加谓词，但到目前为止运气不佳.很少尝试，所有这些都不起作用.

I'm trying to understand difference lists in Prolog, but I'm struggling to actually implement one properly, everytime I try to do it, I get a list of lists, but that's not what I want. I'm trying to implement an append predicate, but having little luck so far. Few attempts, all of which don't work.

app(X, Y, Z) :- Z = [X|Y].

?- app([a,b,c], [z], Z).
Z = [[a,b,c],z].

或

app(X, Y, Z) :- Z = [X|Hole], Hole = Y.

结果与第一个相同，(它们似乎基本相同).我在一本书中有一个确实有效的示例(尽管它不是谓词)，但我不明白其中的区别.X 实例化为正确答案 [a,b,c,z]，这与我的第二个示例有何不同?

Same results as the first one, (they do seem to be basically the same). I have an example in a book that does work (although it's not a predicate), and I don't understand the difference. X becomes instantiated to the proper answer [a,b,c,z], how is that much different than my second example?

X = [a,b,c|Y], Y = [z].

我错过了什么?谢谢.

推荐答案

理解差异列表的关键是理解它们在表示列表的嵌套复合词的级别上是什么.通常，我们会看到这样的列表:

The key to understanding difference lists is understanding what they are on the level of the nested compound term that represents lists. Normally, we see a list like that:

[a, b, c]

这是一个包含三个元素的列表.使用点作为列表函子 ./2 和原子 [] 作为空列表的完全相同的嵌套项是:

This is now a list with three elements. The exactly same nested term using the dot as the list functor, ./2, and the atom [] as the empty list, would be:

.(a, .(b, .(c, [])))

在这里很重要的是，列表函子是一个带有两个参数的复合词:元素和列表的其余部分.空列表是一个原子，非正式地，可以将其视为具有 0 元数的复合词，即没有参数.

It is important here that the list functor is a compound term with two arguments: the element and the rest of the list. The empty list is an atom, which, informally, could be seen as a compound term with arity 0, that is, without arguments.

现在，这是一个包含三个元素的列表，其中最后一个元素是一个自由变量:

Now, this is a list with three elements where the last element is a free variable:

[a, b, Last]

等同于:

.(a, .(b, .(Last, [])))

另一方面，这是一个包含两个元素和一个自由变量作为列表其余部分的列表，或者 tail:

This, on the other hand, is a list with two elements and a free variable as the rest of the list, or the tail:

[a, b|Tail]

等同于:

.(a, .(b, Tail))

你看到 .(a, .(b, .(Last, []))) 和 .(a, .(b, Tail)) 不一样吗??

从顶层尝试这个(我正在使用 SWI-Prolog 7，它需要 --traditional 标志来将 ./2 视为列表术语):

Trying this on from the top-level (I am using SWI-Prolog 7, which needs the --traditional flag to treat the ./2 as the list term):

$ swipl --traditional
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.26)
Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [a, b, Last] = [a, b|Tail].
Tail = [Last].

?- .(a, .(b, .(Last, []))) = .(a, .(b, Tail)).
Tail = [Last].

现在，差异列表"是这样的列表:[a, b|Tail]，等同于 .(a, .(b, Tail))，你持有变量 Tail 持有尾部.在 Tail 被实例化为一个正确的列表之前，这不是一个正确的列表！

Now, a "difference list" is a list like this: [a, b|Tail], identical to .(a, .(b, Tail)), where you hold on the variable Tail that holds the tail. This is not a proper list until the Tail has been instantiated to a proper list!

?- L = [a, b|Tail], is_list(L).
false.

?- L = [a, b|Tail], Tail = [c,d,e], is_list(L).
L = [a, b, c, d, e],
Tail = [c, d, e].

您可以查看前面的查询以了解 Tail = [c, d, e] 在这种结合中究竟做了什么.

You can look at the previous queries to understand what exactly Tail = [c, d, e] does in this conjunction.

在使用差异列表的谓词中，您需要两个参数，或者有时需要一个对，以保持不完整列表及其尾部，就像这样:

In a predicate that uses a difference list, you need two arguments, or sometimes, a pair, to hold on to the incomplete list and its tail, like this:

% using two arguments
foo([a,b|Tail], Tail).
% using a pair
foo([a,b|Tail]-Tail).

第一个 foo/2 有两个参数，第二个有一个，这是一个对".现代 Prolog 代码似乎更喜欢两个参数而不是一对参数，但您经常在教科书和教程中看到这对参数.

The first foo/2 has two arguments, the second has one, which is a "pair". Modern Prolog code seems to prefer two arguments to a pair, but you see the pair in textbooks and tutorials quite often.

到您的附加或 app/3:当您使用差异列表时，您需要额外的参数(或一对)，以便您可以访问您正在处理的列表的尾部.如果你只有将在前面的列表尾部，你仍然可以编写一个只有三个参数的 append，因为只需要将第一个列表的尾部与第二个列表统一起来:

To your append, or app/3: When you are working with difference lists, you need the extra argument (or a pair) so that you can access the tail of the list you are dealing with. If you only have the tail of the list that will be at the front, you can still write an append that only has three arguments, because all it takes is to unify the tail of the first list with the second list:

% app(List1, Tail1, List2)
app(List1, Tail1, List2) :- Tail1 = List2.

或直接在头脑中统一:

app(_L1, L2, L2).

?- L1 = [a,b|Tail], app(L1, Tail, [c]).
L1 = [a, b, c],
Tail = [c].

这与@Wouter 提供的链接中的代码完全相同.

This is the exact same code as in the link provided by @Wouter.

如果你有两个列表的尾部，你将用第二个列表替换第一个列表的尾部，并保留第二个列表的尾部.

If you had the tails of both lists, you will replace the tail of the first list with the second list, and keep the tail of the second list.

app(List1, Tail1, List2, Tail2) :- Tail1 = List2.

同样，您可以在头脑中进行统一.

Again, you could have done the unification in the head.

编辑:

一旦列表已经完全实例化，你就不能制造洞".你会如何从这个 .(a, .(b, .(c, []))) 到这个: .(a, .(b, .(c, Tail)))?你不能，除了从头到尾遍历列表并将[]替换为Tail，但这正是普通的append/3代码> 确实如此.试试:

You can't make a "hole" once the list is already fully instantiated. How would you go from this .(a, .(b, .(c, []))) to this: .(a, .(b, .(c, Tail)))? You can't, except for traversting the list head to end and replacing the [] with Tail, but this is exactly what the ordinary append/3 does. Try:

?- L = [a,b,c,d], append(L, Back, Front), Back = [x,y,z].
L = [a, b, c, d],
Back = [x, y, z],
Front = [a, b, c, d, x, y, z].

或者，如果您将 diflist_append/3 定义为:

Or, if you have a diflist_append/3 defined as:

diflist_append(Front, Back, Back).

将列表的Back与第三个参数统一起来:

Which unifies the Back of list with the third argument:

?- L = [a,b,c,d], append(L, Back, Front), diflist_append(Front, Back, [x,y,z]).
L = [a, b, c, d],
Back = [x, y, z],
Front = [a, b, c, d, x, y, z].

对于你的例子，X = [a,b,c], Y = [X|Z], Z = [z]，这与:

As for your example, X = [a,b,c], Y = [X|Z], Z = [z], this is the same as:

X = .(a, .(b, .(c, []))),
Y = .(X, Z), % Y = .(.(a, .(b, .(c, []))), Z)
Z = [z] % Y = .(.(a, .(b, .(c, []))), .(z, []))

所以你现在看到了吗?

这篇关于了解差异列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！