5

我被问到这个问题：

定义一个谓词ordered/1，它检查整数列表是否正确地按升序排列。例如，目标ordered([1,3,7,11])应该成功，目标也应该成功，ordered([1,3,3,7])而目标ordered([1,7,3,9])应该失败。

到目前为止，我有这个：

ordered([]).    
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

但它在每个列表上都失败了。

我推断它失败的原因是因为它到达列表中的末尾编号，然后尝试将该编号与空列表进行比较。显然这会失败，因为您无法将整数与空列表进行比较。即使您可以并且它返回0一个空列表，它仍然会返回 false，因为该数字将大于0，而不是小于。

我找不到解决方案...有什么想法吗？谢谢，乔恩。

编辑

所以，一些稍微修改的代码：

ordered([]).
ordered([N]):-
    N >= 0.
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

这现在适用于ordered([1])，但更大的列表仍然无法正确运行。

我应该ordered([N, M|Ns])在定义中包含类似的内容吗？

4

7 回答 7

5

（假设这是家庭作业，我不愿给出完整的解决方案）。

查看您的代码，尝试找出它将如何统一?- ordered([1]). 运行此查询（或使用 trace/0），并逐步了解它的作用以及它如何计算结果。

另外，在考虑 prolog 时，请尽量不要忘记“返回值”。Prolog 谓词不返回任何内容。

于 2009-08-26T12:34:28.333 回答
2

我认为您的解决方案也不是尾递归友好的。想想这样的事情会做：

ordered([]) :-!.
ordered([_]):-!.
ordered([A,B|T]) :-
    A =< B,
    !,
    ordered([B|T]).
于 2009-08-27T14:03:38.413 回答
2

如果您的 Prolog 系统支持，请检查它是否提供库谓词clpfd:chain/2。

:- use_module(library(clpfd)).

如果是这样，只需编写：

?- chain([1,3,7,11],#<).
true.

?- chain([1,3,3,7],#=<).
true.
?- chain([1,3,3,7],#<).
false.

?- chain([1,7,3,9],#<).
false.
于 2015-06-23T08:07:56.523 回答
2

如果您使用的是SICStus Prolog， 我之前的回答将不起作用，因为 SICStus Prolog 中的 clpfd 库 不提供 SWI-Prolog 的 clpfd librarychain/3中包含 的库谓词。

:- use_module(library(clpfd)).
:- assert(clpfd:full_answer).

不要恐慌！像这样简单地实现谓词ordered/1：

ordered([]).
ordered([X|Xs]) :- 
   ordered_prev(Xs,X).

ordered_prev([]     ,_ ).
ordered_prev([X1|Xs],X0) :- 
   X0 #=< X1,
   ordered_prev(Xs,X1).

让我们看看它在 SICStus Prolog 4.3.2 中的作用。这是最一般的查询：

?- ordered(Xs).
  Xs = []
; Xs = [_A]
; Xs = [_A,_B],    _A#=<_B,          _A in inf..sup, _B in inf..sup
; Xs = [_A,_B,_C], _A#=<_B, _B#=<_C, _A in inf..sup, _B in inf..sup, _C in inf..sup
... % an infinity of solutions follows: omitted for the sake of brevity.

以下是 OP 建议的查询：

?- ordered([1,3,7,11]).
yes                                  % succeeds deterministically
?- ordered([1,3,3,7]).
yes                                  % succeeds deterministically
?- ordered([1,7,3,9]).
no

请注意，由于第一个参数索引，上述示例中的两个后续查询都没有留下任何无用的选择点。

于 2015-06-27T23:36:11.183 回答
1

你是对的：根据你的代码，列表只有两种可能的方式ordered：

  1. 它是空的
  2. 前两项的顺序正确，列表的其余部分是ordered

这些当然都是正确的陈述，但是列表[3]呢？不ordered也是这样吗？显然，一个只有一个元素的列表是有序的，但您没有规定要表达这一点：它既不适合您的基本情况，也不适合您的递归情况。

单元素列表是您尚未解决的另一种隐藏在这里的情况。由于这与您已经定义的两条规则无关，因此您可能需要考虑一种方法来分别处理这种特殊情况。

于 2009-08-26T12:36:37.130 回答
0

好吧，最后，修复起来非常容易。

这是正确的代码。

ordered([]).

ordered([N, M|Ns]):-
 append([M], Ns, Tail),
 ordered(Tail),
 N =< M.

ordered([M]).

有序（[M]）。如上所述处理单元素列表。

我的问题的真正根源不在于 append 函数中 M 周围的 [] 。

关于授予正确答案的礼仪是什么？你们俩都帮了大忙。

乔恩

于 2009-08-26T14:48:00.910 回答
0

不要使用append/3.

edit1来满足@false。为了使其尾递归友好，它必须消除回溯。这是尾递归的，在@Xonix 上只有轻微的变化：

ordered([X|[]]):-!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).

edit2更进一步，消除少于两个元素的列表

ordered([X,Y|[]]):- X =< Y,!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).
于 2015-06-23T11:33:07.800 回答