3

我有以下问题：

定义一个谓词sorted(LL)，当列表LL 包含按长度增加的顺序排序的其他列表时满足该谓词。例如：

?- 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]). 当列表列表中只剩下一个元素时，该调用将附加一个空列表[]，因此更短/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
4

2 回答 2

3

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

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

首先，它通常有助于最小化问题。也sorted([[],[3]])失败了，尽管我们希望它成功。sorted([[],[]])甚至循环。

了解不终止

循环？这通常更容易在纯 Prolog 程序中本地化。我将在程序中添加目标false和目标T = []。由此产生的程序片段（称为故障片）肯定会变得完全功能失调。但它将保留一个非常好的属性。For：如果这个新片段循环，那么原程序也会循环。这是仍然循环的程序：

?- 排序（[[]，[]]），假。

排序（[]）：-假。
排序（[_]）：-假。
排序（[L1，L2 | T]）：- T = []，L1 = []，L2 = []，
   更短（L1，L2），
   排序（[L2，T]）。

更短（[]，_）。
更短（[_|T1]，[_|T2]）：-假，
   更短（T1，T2）。

换句话说：

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

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

总结阅读

理解问题的另一种方法是从箭头指向的方向从右到左阅读递归规则。实际上，:-是为了象征 ←，嗯，1970 年代的风格（听这个法国 1972 年的夏季热播 ，直到你明白）。所以让我们试试这个。我会读到：

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

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

前提是，sorted([L2,T])是真的。

或许还有一些额外的评论：现在，你可能会很不安。你可能会说：谁知道呢？也许这根本不是真的！但关键是，这只是有条件的。好的？

并且提供shorter(L1, L2)的是真实的

那么，我们可以断定这sorted([L1, L2|T])是真的。

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

但是我们实际上在哪里声明长度为 2 的列表成立呢？除了这条规则，别无他法。因此：没有任何地方说明这一点。因此长度为 2 或更长的列表永远不会被排序。

于 2014-11-04T16:21:35.560 回答
2

您在谓词的最后一个子句中有两个拼写错误sorted/1，应该是：

sorted([L1,L2| T]) :- shorter(L1, L2), sorted([L2| T]).
于 2014-11-04T02:44:39.937 回答