sorting - Prolog - 如何让尾部不为空

Question

I have the following problem:

Define a predicate sorted(LL), that is satisfied when the list LL contains other lists that are sorted in order of increasing length. For example:

?- sorted([[],[1],[1,1],[1,1,1]]) -> yes.
?- sorted([[],[1],[1,1]]) -> yes.
?- sorted([[1],[],[1,1],[1,1,1]]) -> no.

到目前为止我有这段代码:

% shorter/2

shorter([],_).
shorter([_|T1], [_|T2]) :- shorter(T1,T2).

% sorted/1

sorted([]).
sorted([_]).
sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).

问题包含在上面的行中:sorted([L2,T])。当列表列表中只剩下一个元素时，该调用将附加一个空列表 [] 因为 shorter/2 将失败。它在以下 SWIPL 跟踪中进行了描述。

[trace]  ?- sorted([[1],[2,3]]).
   Call: (6) sorted([[1], [2, 3]]) ? creep
   Call: (7) shorter2([1], [2, 3]) ? creep
   Call: (8) shorter2([], [3]) ? creep
   Exit: (8) shorter2([], [3]) ? creep
   Exit: (7) shorter2([1], [2, 3]) ? creep
   Call: (7) sorted([[2, 3], []]) ? creep <-- empty list appended
   Call: (8) shorter2([2, 3], []) ? creep
   Fail: (8) shorter2([2, 3], []) ? creep
   Fail: (7) sorted([[2, 3], []]) ? creep
   Fail: (6) sorted([[1], [2, 3]]) ? creep

Answer 1

@PauloMoura 已经给了你正确的答案。这方面有什么值得学习的吗？你是怎么遇到那个问题的？如何系统地定位这些问题？我假设您不是出于纯粹的好奇心和动画 gif 供应不足而跳入调试器查看所有这些痕迹。

您遇到了问题。也就是说，您的目标 sorted([[1],[2,3]]). 您希望成功，但它没有。所以你在这里遇到了一些意外的失败。有时也称为不足 或不完整。这意味着 sorted/1 的定义过于特化，它描述了一组太小的解决方案——至少它错过了 sorted([[1],[2,3] ]).

首先，它通常有助于最大限度地减少问题。 sorted([[],[3]]) 也失败了，尽管我们预计它会成功。并且 sorted([[],[]]) 偶数循环。

理解非终止

循环？这通常更容易在纯 Prolog 程序中进行本地化。我将在程序中添加目标 false 和类似 T = [] 的目标。生成的程序片段(称为 failure slice )肯定会变得完全无法正常工作。但它将保留一个非常好的属性。对于:如果这个新的片段循环，那么原来的程序也会循环。这是仍在循环的程序:

?- sorted([[],[]]), false.sorted([]) :- false.sorted([_]) :- false.sorted([L1,L2 | T]) :- T = [], L1 = [], L2 = [],   shorter(L1, L2),   sorted([L2,T]).shorter([],_).shorter([_|T1], [_|T2]) :- false,   shorter(T1,T2).

in other words:

sorted([[],[]]) :-
   shorter([],[]),
   sorted([[],[]]).

因此，从程序上讲，该规则不会(总是)减少列表的长度。

结束阅读

理解问题的另一种方法是阅读递归规则在箭头指向的方向上从右到左。实际上，:- 是用来象征 ←，嗯，1970 年代的风格(听这个 French 1972 summerhit to 直到你明白)。所以让我们试试这个。我会读:

sorted([L1,L2 | T]) :- shorter2(L1, L2), sorted([L2,T]).
                                         ^^^^^^^^^^^^^^ starting here

我从右侧开始并将其解释为:

Provided, sorted([L2,T]) is true.

也许一些额外的评论:现在，您可能会感到非常不安。你可能会说:谁知道这个？也许那根本不是真的!但关键是，它只是有条件的。好吗？

and provided shorter(L1, L2) is true

---

then, we can conclude that sorted([L1, L2|T]) is true.

因此我们将长度为 2 的列表视为理所当然，并得出结论，长度为 2 或更大的列表也成立。

但是我们实际上在哪里声明长度为 2 的列表成立？除此规则外，没有其他地方。因此:这没有说明。因此，长度为 2 或更长的列表将永远不会被排序。