Удалить ведущие нули в списке в Прологе

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

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

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

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

Источник

6 ответов

Решение

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

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

Источник

С библиотекой (Рейф):

:- 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
Источник

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

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.
Источник

Вот решение, которое не генерирует точек выбора. Используется 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 и?- 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 обрабатывается только первый аргумент. Для одновременной обработки нескольких аргументов можно использовать предикат, когда / 2. Но для простоты это не показано здесь.

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

Источник

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

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

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

Источник

Вот как бы я это сформулировал. Сначала установите ограничения: 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)),

Источник
Другие вопросы по тегам