在序言中到达列表末尾

问题描述 投票：0回答：10

有人问我这个问题：

定义一个谓词 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])
这样的东西吗？

list recursion prolog
10个回答
5
投票

（假设这是作业，我犹豫要不要给出一个完整的解决方案）。

查看您的代码，尝试找出它如何统一

?- ordered([1]).
在心里运行这个查询（或使用 trace/0），一步一步地看它做了什么，以及它是如何计算结果的。

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

2
投票

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

ordered([]) :-!.
ordered([_]):-!.
ordered([A,B|T]) :-
    A =< B,
    !,
    ordered([B|T]).
2
投票

如果您正在使用 SICStus Prolog， 我之前的回答 不会起作用，因为 SICStus Prolog 中的 clpfd 库 不提供库谓词 

chain/3
包含在 SWI-Prolog 的 clpfd 库.

:- 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

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

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.
1
投票

你说得很对：根据你的代码，列表只有两种可能的方式

ordered
：

  1. 空无一物
  2. 前两项顺序正确，其余列表为
    ordered

这些肯定都是正确的陈述，但是列表呢

[3]
？这不也是
ordered
吗？显然，只有一个元素的列表是有序的，但您没有规定可以表达这一点：它既不适合您的基本情况，也不适合您的递归情况。

单元素列表是隐藏在这里的另一个您尚未解决的案例。由于这独立于您已经定义的两个规则，您可能需要考虑一种方法来分别解决这种特殊情况。

1
投票

有效地使用第一个参数索引：

ordered([]).
ordered([H|T]) :-
    ordered_(T, H).

ordered_([], _).
ordered_([H|T], P) :-
    P @=< H,
    ordered_(T, H).

swi-prolog 中的结果：

?- ordered([1,2,3,4,5]).
true.

?- ordered([a,b,c,d,g]).
true.

?- ordered([b,c,a,d]).
false.

这不会留下不需要的选择点，使用 standard order（因此不仅适用于整数），而且速度很快。性能对比：

乔布：

?- garbage_collect, numlist(1, 1_000_000, L), time(ordered(L)).
% 3,999,996 inferences, 0.872 CPU in 0.873 seconds (100% CPU, 4589226 Lips)

对比这个：

?- garbage_collect, numlist(1, 1_000_000, L), time(ordered(L)).
% 2,000,001 inferences, 0.046 CPU in 0.046 seconds (100% CPU, 43662698 Lips)
0
投票

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

这是正确的代码。

ordered([]).

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

ordered([M]).

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

我的问题的真正根源是没有在附加函数中包含 M 周围的 []。

答对有什么礼仪？你们都帮了大忙。

乔恩

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]).
0
投票

纯净版：

ordered_freeze(L) :-
    freeze(L, ordered_freeze_(L, [])).
    
ordered_freeze_([], _).
ordered_freeze_([H|T], Ps) :-
    % Apply when_gte to the previous list elements
    maplist(when_gte(H), Ps),
    freeze(T, ordered_freeze_(T, [H|Ps])).
    
% When comparable, is greater than or equal
when_gte(High, Low) :-
    when(?=(Low, High), Low @=< High).

swi-prolog 中的结果：

?- ordered_freeze(L), length(L, 4).
L = [_A, _B, _C, _D],
when(?=(_A, _B), _A@=<_B),
when(?=(_B, _C), _B@=<_C),
when(?=(_A, _C), _A@=<_C),
when(?=(_C, _D), _C@=<_D),
when(?=(_B, _D), _B@=<_D),
when(?=(_A, _D), _A@=<_D).

它会将所有列表元素与所有其他列表元素进行比较，只要它们可以确定地进行比较。

这会带来性能损失，但允许例如：

?- ordered_freeze(L), L = [1,X,3], X = 2.
L = [1, 2, 3],
X = 2.

?- ordered_freeze(L), L = [1,X,3], X = 99.
false.
0
投票

比我之前的答案要好得多

freeze
：

ascending_or_equal_freeze([]).
ascending_or_equal_freeze([H|T]) :-
    ascending_or_equal_freeze_start_(T, H).

ascending_or_equal_freeze_start_([], _).
ascending_or_equal_freeze_start_([H|T], P) :-
    % Need 2 elements, to start comparison
    ascending_or_equal_freeze_([P,H|T], []).

ascending_or_equal_freeze_([], _).
ascending_or_equal_freeze_([H|T], Before) :-
    ascending_or_equal_freeze_search_(Before, <,  H),
    ascending_or_equal_freeze_search_(T, >,  H),
    (   ground(H) ->
        % Can cut the list short, H is completely comparable
        Before1 = [H]
    ;   Before1 = [H|Before]
    ),
    freeze(T, ascending_or_equal_freeze_(T, Before1)).

ascending_or_equal_freeze_search_(L, Comp, P) :-
    ascending_or_equal_freeze_search_loop_(L, Comp, P, [], L).

ascending_or_equal_freeze_search_loop_(L, Comp, P, Visited, OrigL) :-
    (   \+ \+ L = []
    % End of list - resume search when P is instantiated further
    ->  ascending_or_equal_freeze_when_(OrigL, Comp, P)
    ;   L = [H|T],
        (   ?=(H, P)
        % Can compare with certainty
        ->  compare_or_equal(Comp, H, P, ActualComp),
            (   ActualComp = (=)
            % Elements in-between must be same
            ->  maplist(=(P), Visited)
            ;   true
            )
        ;   ascending_or_equal_freeze_search_loop_(T, Comp, P, [H|Visited], OrigL)
        )
    ).

ascending_or_equal_freeze_when_(L, Comp, P) :-
    (   \+ \+ L = []
    % Nothing to compare
    ->  true
    ;   term_variables(P, Vars),
        (   Vars == []
        % P is ground
        ->  true
        % Resume search when instantiated further
        ;   when_nonvar_any(Vars, ascending_or_equal_freeze_search_(L, Comp, P))
        )
    ).

compare_or_equal(Comp, X, Y, ActualComp) :-
    compare(C, X, Y),
    compare_or_equal_(C, Comp, ActualComp).

compare_or_equal_(=, _, =).
compare_or_equal_(<, <, <).
compare_or_equal_(>, >, >).

when_nonvar_any([], _).
when_nonvar_any([H|T], Action) :-
    nonvar_elem_cond([H|T], Cond),
    when(Cond, Action). 
    
nonvar_elem_cond([H|T], L) :-
    nonvar_elem_cond_(T, H, L).
    
nonvar_elem_cond_([], H, nonvar(H)).
nonvar_elem_cond_([H|T], P, nonvar(P);L) :-
    nonvar_elem_cond_(T, H, L).

swi-prolog 中的结果：

?- ascending_or_equal_freeze(L), L = [1,2,X,Y,5,6|T].
L = [1, 2, X, Y, 5, 6|T],
when(nonvar(X), ascending_or_equal_freeze_search_([2, 1], <, X)),
when(nonvar(X), ascending_or_equal_freeze_search_([Y, 5, 6|T], >, X)),
when(nonvar(Y), ascending_or_equal_freeze_search_([X, 2, 1], <, Y)),
when(nonvar(Y), ascending_or_equal_freeze_search_([5, 6|T], >, Y)),
freeze(T, ascending_or_equal_freeze_(T, [6])).

?- numlist(1, 4000, L), time(ascending_or_equal_freeze(L)).
% 63,997 inferences, 0.004 CPU in 0.004 seconds (98% CPU, 15798229 Lips)

% Automatically joins up logically-equal segments
?- L = [_, b, _, _, _, _, X, _], ascending_or_equal_freeze(L), X = b.
L = [_A, b, b, b, b, b, b, _B],
X = b,
when(nonvar(_A), ascending_or_equal_freeze_search_([b, b, b, b, b, b, _B], >, _A)),
when(nonvar(_B), ascending_or_equal_freeze_search_([b, b, b, b, b, b], <, _B)).
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.