删除 Prolog 中列表中的前导零

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

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

这是我所拥有的：

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

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

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

编辑 这个谓词实际上不适用于例如

lead(L0, [0,1,2])
。

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
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)
的初始检查是我能够提出的唯一解决方案，可以防止出现问题，例如
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
，我是通过对
(=)/3
中的
library(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.
5
投票

这是一个不生成任何选择点的解决方案。它是 使用 freeze/2，其方式是 diff/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扩展和？-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。但为了简单起见，这里没有显示。

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

3
投票

代码中的问题是第二个参数（您的输出）被指定为 

_
，因此您的谓词对于任何输出都是 true。您想要的是一个谓词，当且仅当它是输入减去前导零时才为真。

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

第一行中的 

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

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))
。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.