Подтвердить что ты не робот

Удалить ведущие нули в списке в Prolog

У меня есть список с неизвестным числом нулей в начале его, например [0, 0, 0, 1, 2, 0, 3]. Мне нужно, чтобы этот список был лишен ведущих нулей, чтобы он выглядел как [1, 2, 0, 3].

Вот что у меня есть:

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

Результат которого просто True. Чтение трассы показывает, что она работает до тех пор, пока она не будет иметь список без начальных нулей, но тогда ответ не будет распространять резервную копию стека. Я новичок в Prolog, поэтому не могу понять, как это сделать.

4b9b3361

ОТВЕТЫ

Ответ 1

Вот решение, которое работает во всех направлениях:

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]).

Ответ 2

С библиотека (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

Ответ 3

Вот решение, которое не генерирует никаких точек выбора. это используя замораживание /2, таким образом, который не предвидится diff/2. Но используя freeze/2 здесь вполне уместно, поскольку одно правило для замораживания /2 выглядит следующим образом:

Правило большого пальца для замораживания /2: Используйте freeze/2, где предикат будет генерировать необоснованные решения и множество точек выбора. Надежда заключается в том, что последующая цель будет определять решение больше, и freeze/2 будет разбужен. К сожалению, не работает с CLP (FD) или dif/2, так как замораживание /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 (библиотека (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].

В приведенной выше реализации ввода /2 обрабатывается только первый аргумент. Для одновременного использования нескольких аргументов предикат, когда можно использовать /2. Но для простоты это не показано здесь.

Кроме того, при использовании приостановленных целей в конце может потребоваться надпись, как предикат, поскольку приостановленные цели не могут обнаружить несогласованность между ними.

Ответ 4

Вот решение, которое действительно работает для всех возможных входов и не оставляет ненужных точек выбора:

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

Проблема в вашем коде заключается в том, что второй параметр, ваш вывод, указан как _, поэтому ваш предикат является истинным для любого вывода. То, что вы хотите, является предикатом, который является истинным тогда и только тогда, когда это вход минус ведущие нули.

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

! в первой строке не является обязательным. Он обрезает дерево поиска, поэтому Prolog не рассматривает вторую строку (которая не удалась), если первая строка соответствует.

Ответ 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 - это простой неглубокий тест для исключения. Используйте is_list/1, если вы хотите быть педантичным в отношении вещей.

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

Отредактировано для заметок: is_list/1 перемещает весь список, чтобы убедиться, что он является тестированием, - это правильно построенный список, то есть член ./2, правая часть которого сама является либо другим термином ./2, либо atom [] (который обозначает пустой список). Если список длинный, это может быть дорогостоящей операцией.

Итак, что-то вроде [a,b,c] является правильным списком и на самом деле является этим термином: .(a,.(b,.(c,[]))). Что-то вроде [a,b|32] не является правильным списком: это термин .(a,.(b,32)).