12

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

这是我所拥有的：

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

其输出只是 True。读取跟踪表明它正在运行，直到它有一个没有前导零的列表，但随后答案不会传播回堆栈。我对 Prolog 很陌生，所以我不知道如何让它做到这一点。

4

6 回答 6

11

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

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 = [] ;
...

编辑这个谓词实际上不适用于 eg lead(L0, [0,1,2])。

于 2016-10-01T08:29:40.370 回答
9

使用库（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
于 2016-10-03T15:45:00.093 回答
6

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

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)是我能够提出的唯一解决方案，它可以防止 eg 出现问题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)))
    ).

这也使用了，我通过对in(\=)/3的简单修改想出的。(=)/3library(reif)

\=(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.
于 2016-10-04T07:20:10.533 回答
5

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

freeze/2 的经验法则：使用 freeze/2 谓词将生成未实例化的解决方案和许多选择点。希望是后续目标将更多地指定解决方案，并唤醒 freeze/2。不幸的是，不适用于 CLP(FD) 或 dif/2，因为 freeze/2 不会对 CLP(FD) 或 dif/2 所暗示的改进做出反应，只有统一才会唤醒它。

因此，代码是：

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，Jekejeke Prolog 使用Minlog Extension和 ?-use_module(library(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。但为简单起见，此处未显示。

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

于 2016-10-02T21:49:10.627 回答
3

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

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

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

于 2016-09-30T19:59:31.673 回答
2

这就是我的措辞。首先，建立约束：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是一个简单的浅表测试。is_list/1如果您想对事物迂腐，请使用。

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

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

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

于 2016-10-05T00:50:47.970 回答