Определенная логическая программа

Цель состоит в том, чтобы реализовать предикат noDupl/2,

Первым аргументом этого предиката является список для анализа, а вторым аргументом является список чисел, которые не являются дубликатами.

Я не мог понять код ниже, и когда я скомпилировал его, он выдал сообщение об ошибке, что contained является неопределенной процедурой, однако в качестве подсказки написано, что мы можем использовать в качестве предопределенного предиката contained а также notContained, Я думаю, что мне нужно определить contained а также notContained,

noDupl(XS, Res):-
   help( XS, [],Res).

help([],_,[]).
help([X|XS],Seen,[X|Res]):-
   notContained(X,XS),
   notContained(X,Seen), 
   help(XS, [X|Seen], Res).
help([X|XS],Seen,Res):-
   contained(X,Seen),
   help(XS, Seen, Res).
help([X|XS],Seen,Res):-
   contained(X,XS),
   help(XS, [X|Seen], Res).

Может кто-нибудь, пожалуйста, объясните мне проблему.

Источник

3 ответа

Решение

Недостающие определения могут быть:

contained(X,[X|_]).
contained(X,[E|Es]) :-
   dif(X, E),
   contained(X, Es).

notContained(_X, []).
notContained(X, [E|Es]) :-
   dif(X, E),
   notContained(X, Es).

(Мне нравится называть эти отношения скорее memberd/2 а также non_member/2.)

Определение, которое вы дали, расширяет отношение дополнительным аргументом для элементов, рассмотренных до сих пор.

Чтобы понять значение каждого предложения, прочитайте каждое справа налево в направлении стрелки (:- является ASCII-фиксацией 1970-х годов ←). Давайте возьмем первое правило:

При условии, что X не является элементом XS, а также
при условии, что X не является элементом Seen, а также
при условии, что help(X, [X|Seen], Res) правда,

тогда также help([X|XS],Seen,[X|Res]) правда.

Другими словами, если X нет ни в списке посещенных элементов Seen ни в элементах, которые еще предстоит посетить XS, то он не обладает дубликатом.

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

Вот случай, когда такая избыточность показывает:

?- noDupl([a,a,a],U).
U = [] ;
U = [] ;
false.

В идеале система должна дать однозначный ответ:

?- noDupl([a,a,a], U).
U = [].

Лично мне не очень нравится разбивать вещи на слишком много дел. По сути, у нас может быть два: это дубликат, а его нет.

Можно предоставить определение, которое является правильным и все еще полностью определенным для случаев, когда возможен детерминизм, например, когда первый аргумент является "достаточно конкретизированным" (который включает основной список). Давайте посмотрим, есть ли ответы в этом направлении.

Источник

Можно ли сделать это чисто и эффективно? Да, используя tpartition/4 а также (=)/3 вот так:

dups_gone([]    ,[]).
dups_gone([X|Xs],Zs0) :-
   tpartition(=(X),Xs,Ts,Fs),
   if_(Ts=[], Zs0=[X|Zs], Zs0=Zs),
   dups_gone(Fs,Zs).

Некоторые примеры наземных запросов (все из которых выполняются детерминистически):

?- dups_gone([a,a,a],Xs).
Xs = [].

?- dups_gone([a,b,c],Xs).
Xs = [a, b, c].

?- dups_gone([a,b,c,b],Xs).
Xs = [a, c].

?- dups_gone([a,b,c,b,a],Xs).
Xs = [c].

?- dups_gone([a,b,c,b,a,a,a],Xs).
Xs = [c].

?- dups_gone([a,b,c,b,a,a,a,c],Xs).
Xs = [].

Это также работает с более общими запросами. Рассматривать:

?- length(Xs,N), dups_gone(Xs,Zs).
  N = 0, Xs = [],            Zs = []
; N = 1, Xs = [_A],          Zs = [_A]
; N = 2, Xs = [_A,_A],       Zs = []
; N = 2, Xs = [_A,_B],       Zs = [_A,_B],    dif(_A,_B)
; N = 3, Xs = [_A,_A,_A],    Zs = []
; N = 3, Xs = [_A,_A,_B],    Zs = [_B],       dif(_A,_B)
; N = 3, Xs = [_A,_B,_A],    Zs = [_B],       dif(_A,_B)
; N = 3, Xs = [_B,_A,_A],    Zs = [_B],       dif(_A,_B), dif(_A,_B)
; N = 3, Xs = [_A,_B,_C],    Zs = [_A,_B,_C], dif(_A,_B), dif(_A,_C), dif(_B,_C)
; N = 4, Xs = [_A,_A,_A,_A], Zs = [] 
...
Источник

Я аннотировал ваш код для вас:

noDupl( XS , Res ) :- % Res is the [unique] set of element from the bag XS
  help( XS, [],Res)    % if invoking the helper succeeds.
  .                    %

help( []     , _    , []      ) .  % the empty list is unique.
help( [X|XS] , Seen , [X|Res] ) :- % A non-empty list is unique, if...
   notContained(X,XS),             % - its head (X) is not contained in its tail (XS), and
   notContained(X,Seen),           % - X has not already been seen, and
   help(XS, [X|Seen], Res).        % - the remainder of the list is unique.
help( [X|XS] , Seen , Res ) :-     % otherwise...
   contained(X,Seen) ,             % - if X has been seen,
   help(XS, Seen, Res).            % - we discard it and recurse down on the tail.
help([X|XS],Seen,Res):-            % otherwise...
   contained(X,XS),                % - if X is in the tail of the source list, 
   help(XS, [X|Seen], Res).        % - we discard it (but add it to 'seen').

Ваш contained/2 и предикаты notContained/2` могут быть определены так:

contained( X , [X|_]  ) :- ! .
contained( X , [Y|Ys] ) :- X \= Y , contained( X , Ys ) .

not_contained( _ , [] ) .
not_contained( X , [Y|Ys] ) :- X \= Y , not_contained(X,Ys) .

Возможно, я что-то упускаю в вашем коде, но в нем очень много избыточности. Вы можете просто написать что-то вроде этого (используя встроенные модули member/2 а также reverse/2):

no_dupes( List , Unique ) :- no_dupes( Bag , [] , Set ) .

no_dupes( [] , V , S ) .      % if we've exhausted the bag, the list of visited items is our set (in reverse order of the source)
  reverse(V,S)                % - reverset it 
  .                           % - to put our set in source order
no_dupes( [X|Xs] , V , S ) :- % otherwise ...
  ( member(X,V) ->            % - if X is already in the set, 
    V1 = V                    % -   then we discard X
  ; V1 = [X|V]                % -   else we add X to the set 
  ) ,                         % And...
  no_dupes( Xs , V1 , S )     % we recurse down on the remainder
  .                           % Easy!
Источник
Другие вопросы по тегам