删除 Prolog 列表中的前导零

Question

我有一个列表，开头有未知数量的零，例如 [0, 0, 0, 1, 2, 0, 3]。我需要这个列表去掉前导零，这样它看起来像 [1, 2, 0 , 3].

这是我的：

lead([Head | _], _) :- Head =\= 0.
lead([0 | Tail], _) :- 
  lead(Tail, Tail).

它的输出就是 True。读取跟踪显示它是运行直到它有一个没有前导零的列表，但答案不会传播回堆栈。我是 Prolog 的新手，所以我不知道如何做到这一点。

Answer 1

您的代码中的问题是第二个参数，即您的输出，被指定为 _，因此您的谓词对于任何输出都为真。您想要的是一个谓词，当且仅当它是输入减去前导零时才为真。

lead([], []).
lead([0 | Tail], Tail2) :- !, lead(Tail, Tail2).
lead([Head | Tail], [Head | Tail]) :- Head =\= 0.

第一行的!是可选的。它会修剪搜索树，因此如果第一行匹配，Prolog 不会考虑第二行（这会失败）。

Answer 2

这是一个适用于所有方向的解决方案：

lead([],[]).
lead([H|T],[H|T]) :-
    dif(H,0).
lead([0|T],T2) :-
    lead(T,T2).

一些查询：

?- lead([0,0,0,1,2,0,3], L).
L = [1, 2, 0, 3] ;
false.


?- lead(L, []).
L = [] ;
L = [0] ;
L = [0, 0] ;
L = [0, 0, 0] ;
...


?- lead(L0, L).
L0 = L, L = [] ;
L0 = L, L = [_G489|_G490],
dif(_G489, 0) ;
L0 = [0],
L = [] ;
L0 = [0, _G495|_G496],
L = [_G495|_G496],
dif(_G495, 0) ;
L0 = [0, 0],
L = [] ;
L0 = [0, 0, _G501|_G502],
L = [_G501|_G502],
dif(_G501, 0) ;
L0 = [0, 0, 0],
L = [] ;
...

EDIT 这个谓词实际上不适用于例如lead(L0, [0,1,2]).

Answer 3

这是一个不产生任何选择点的解决方案。它的 freeze/2 的使用方式与 dif/2 不同。但是使用 freeze/2 在这里非常合适，因为 freeze/2 的一个经验法则如下：

Rule of Thumb for freeze/2: Use freeze/2 where the predicate would generate uninstantiated solutions and a lot of choice points. The hope is that a subsequent goal will specify the solution more, and the freeze/2 will be woken up. Unfortunately doesn't work with CLP(FD) or dif/2, since freeze/2 does not react to refinements implied by CLP(FD) or dif/2, only unification will wake it up.

代码是这样的：

lead(X, Y) :- var(X), !, freeze(X, lead(X,Y)).
lead([X|Y], Z) :- var(X), !, freeze(X, lead([X|Y],Z)).
lead([0|X], Y) :- !, lead(X, Y).
lead(X, X).

这里有一些示例运行（SWI-Prolog without some import, Jekejeke Prolog use Minlog Extension 和 ?- use_module（库（term/suspend）））：

?- lead([0,0,0,1,2,3], X).
X = [1, 2, 3].

?- lead([0,0|X], Y).
freeze(X, lead(X, Y)).

?- lead([0,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
Y = [1, 2, 3].

?- lead([Z,0|X], Y), X = [0,1,2,3].
X = [0, 1, 2, 3],
freeze(Z, lead([Z, 0, 0, 1, 2, 3], Y)).

?- lead([Z,0|X], Y), X = [0,1,2,3], Z = 0.
Z = 0,
X = [0, 1, 2, 3],
Y = [1, 2, 3].

在上面的 lead/2 实现中，只处理了第一个参数。要同时处理多个参数，可以使用谓词 when/2。但为简单起见，此处未显示。

此外，当使用暂停目标时，可能需要在末尾使用谓词之类的标签，因为暂停目标无法检测到它们之间的不一致。

Answer 4

与library(reif):

:- use_module(reif).

remove_leading_zeros([], []).
remove_leading_zeros([H|T], Rest) :-
        if_(    H = 0,
                remove_leading_zeros(T, Rest),
                Rest = [H|T]).

然后：

?- remove_leading_zeros([0,0,0,1,2,0,3], R).
R = [1, 2, 0, 3].

?- remove_leading_zeros([2,0,3], R).
R = [2, 0, 3].

?- remove_leading_zeros(L, R).
L = R, R = [] ;
L = [0],
R = [] ;
L = [0, 0],
R = [] ;
L = [0, 0, 0],
R = [] . % and so on

Answer 5

这是一个实际适用于所有可能的输入并且不会留下不必要的选择点的解决方案：

lead(L0, L) :-
    (   nonvar(L),
        L = [H|_] ->
        dif(H,0)
        ;
        true
    ),
    lead_(L0, L).

lead_([], []).
lead_([H|T], L) :-
    if_(H \= 0,
        L = [H|T],
        lead_(T,L)).

nonvar(L) 的初始检查是我能够想出的唯一解决方案，可以防止出现问题，例如lead(L0, [0,1,2,3])，同时在所有其他情况下保留谓词的行为。

这使用 if_/3，library(reif)

的一部分

if_(If_1, Then_0, Else_0) :-
    call(If_1, T),
    (  T == true -> Then_0
    ;  T == false -> Else_0
    ;  nonvar(T) -> throw(error(type_error(boolean,T),
                                type_error(call(If_1,T),2,boolean,T)))
    ;  throw(error(instantiation_error,instantiation_error(call(If_1,T),2)))
    ).

这也使用了 (\=)/3，这是我通过简单修改 library(reif) 中的 (=)/3 得到的。

\=(X, Y, T) :-
    (   X \= Y -> T = true
    ;   X == Y -> T = false
    ;   T = true, dif(X, Y)
    ;   T = false,
        X = Y
    ).

一些查询

?- lead([0,0,0,1,2,0,3],L).              % No choice point
L = [1, 2, 0, 3].


?- lead([1,2,0,3],L).
L = [1, 2, 0, 3].


?- lead([0,0,0,0],L).
L = [].


?- lead([],L).
L = [].


?- lead(L0,[0,1,2,0,3]).                 % Correctly fails
false.


?- lead(L0,[1,2,0,3]).
L0 = [1, 2, 0, 3] ;
L0 = [0, 1, 2, 0, 3] ;
L0 = [0, 0, 1, 2, 0, 3] ;
…


?- lead(L0,L).                           % Exhaustively enumerates all cases:  
L0 = L, L = [] ;                         %   - LO empty
L0 = L, L = [_G2611|_G2612],             %   - L0 contains no leading 0
dif(_G2611, 0) ;
L0 = [0],                                %   - L0 = [0]
L = [] ;
L0 = [0, _G2629|_G2630],                 %   - L0 contains one leading 0
L = [_G2629|_G2630],
dif(_G2629, 0) ;
L0 = [0, 0],                             %   - L0 = [0, 0]
L = [] ;
L0 = [0, 0, _G2647|_G2648],              %   - L0 contains two leading 0s
L = [_G2647|_G2648],
dif(_G2647, 0) ;
…                                        %   etc.

Answer 6

以下是我的措辞。首先，建立约束：X 或 Y 必须绑定到一个列表。其他任何方法都失败了。

如果X是绑定的，我们不关心Y：它可以是绑定的也可以是非绑定的。我们只是从 X 中去除所有前导零并将结果与 Y 统一。这条路径有一个可能的解决方案。
如果 X 未绑定而 Y 已绑定，我们将转入生成模式。这条路有无数种可能的解决方案。

代码：

strip_leading_zeros(X,Y) :- listish(X), !, rmv0( X , Y ) .
strip_leading_zeros(X,Y) :- listish(Y), !, add0( Y , X ) .

rmv0( []     , [] ) .
rmv0( [D|Ds] , R  ) :- D \= 0 -> R = [D|Ds] ; rmv0(Ds,R) .

add0( X , X ) .
add0( X , Y ) :- add0([0|X],Y ) .

listish/1 是对 listish-ness 的简单浅层测试。如果你想对事物迂腐，请使用is_list/1。

listish( L     ) :- var(L), !, fail.
listish( []    ) .
listish( [_|_] ) .

编辑说明：is_list/1 遍历 整个列表 以确保它正在测试的是一个正确构造的列表，即 ./2 项，其 right-hand child 本身是另一个 ./2 项或原子 []（表示空列表）。如果列表很长，这可能是一个昂贵的操作。

所以，像 [a,b,c] 这样的东西是一个正确的列表，实际上是这个词：.(a,.(b,.(c,[])))。像 [a,b|32] 这样的东西不是一个合适的列表：它是术语 .(a,.(b,32)).

删除 Prolog 列表中的前导零

Remove leading zeros in list in Prolog

list

prolog

prolog-dif

一些查询