Действующий член проверяет список различий, но как?

Question

Я попытался ответить на другой вопрос (хотя и ошибочно), и это привело к вопросу о «списках различий» (или «списках различий», которое кажется более подходящим, если только «Эшеровская конструкция» не является предпочтительной)

У нас есть полностью заземленный список элементов obj(X,Y) (оба X и Y ground). Мы хотим сохранить только первое obj(X,_), где X еще не встречалось при просмотре списка спереди назад. Эти «первые элементы» должны появляться в порядке появления в результате.

Давайте уточним проблему с помощью тестовых случаев:

% Testing

:- begin_tests(collapse_dl).   

test(one)   :- collapse_dl([],[]).
test(two)   :- collapse_dl([obj(a,b)],
                           [obj(a,b)]).
test(three) :- collapse_dl([obj(a,b),obj(a,c)],
                           [obj(a,b)]).
test(four)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j)],
                           [obj(a,b),obj(b,j)]).
test(five)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j),obj(a,x),obj(b,y)],
                           [obj(a,b),obj(b,j)]).

:- end_tests(collapse_dl).

rt :- run_tests(collapse_dl).

Теперь это легко реализовать с помощью фильтрации, добавления к списку и reverse/2, но как насчет использования списков различий и список приложений ?

однако я не могу заставить работать предикат seen/2. Он проверяет, есть ли obj(A,_) в списке различий. Но каково правильное завершение для этого предиката?

% This is called

collapse_dl([],[]) :- !. 
collapse_dl([X|Xs],Out) :-
   Dlist = [X|Back]-Back,        % create a difflist for the result; X is surely in there (as not yet seen) 
   collapse_dl(Xs,Dlist,Out).    % call helper predicate  

% Helper predicate

collapse_dl([],Ldown,Lup):-               % end of recursion; bounce proper list back up
   Ldown = Lup-[].                        % the "back" of the difflist is unified with [], so "front" becomes a real list, and is also Lup                    

collapse_dl([obj(A,_)|Objs],Ldown,Out) :- 
   seen(obj(A,_),Ldown),                  % guard: already seen in Ldown?
   !,                                     % then commit
   collapse_dl(Objs,Ldown,Out).           % move down chain of induction

collapse_dl([obj(A,B)|Objs],Ldown,Out) :-
   \+seen(obj(A,_),Ldown),                % guard: not yet seen in Ldown?
   !,                                     % then commit
   Ldown = Front-Back,                    % decompose difference list   
   Back = [obj(A,B)|NewTail],             % NewTail is fresh! Append via difflist unification magic
   collapse_dl(Objs,Front-NewTail,Out).   % move down chain of induction; Front has been refined to a longer list

% Membership check in a difference list 

seen(obj(A,_),[obj(A,_)|_Objs]-[]) :- !.  % Yup, it's in there. Cut retry.
seen(Obj,[_|Objs]-[]) :- ...              % But now???

Обновление

С помощью фрагмента кода Пауло:

% Membership check in a difference list 

seen(Element, List-Back) :-
    List \== Back,
    List = [Element|_].    
seen(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    seen(Element, Tail-Back).

Итак, эквивалентность терминов , или неэквивалентность в этом случае, является решением!

Теперь мы пройдем весь тест.

Answer 1

memberchk/2 должен это сделать. Используя подход из здесь ,

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    memberchk( obj(K,X), B ),
    ( X = V -> true ; true ),
    collapse_dl( A, B ).
collapse_dl( [], B ) :-
    length( B, _), !.

Выполнение того, что (функциональный) Пролог делает лучше всего, создание открытого списка в нисходящем порядке.

Проходы тесты, включенные в вопрос.

---

Приложение: С распечатками

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    format("Enter : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
          % Necessarily find  (find or insert)  obj(K, X) (thanks to the 
          %  uninstantiated X) in list B which has an "unobserved" tail:
    memberchk( obj(K,X), B ),
          % Unify X with V if you can; ignore failure if you can't!
    ( X = V -> true ; true ),
    format("Mid   : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
    collapse_dl( A, B ),
    format("Return: ~w relatedto ~w\n", [[obj(K,V) | A], B]).

collapse_dl( [], B ) :-
    format("Termination: From unobserved-tail-list ~w ",[B]),
    length(B, _), 
    format("to ~w (and don't come back!)\n",[B]),
    !.

Из-за добавленных распечаток этот код больше не является рекурсивным. Оригинал есть, и поэтому не имеет «возврата» в своем следе: он просто идет вперед и сразу перестает работать, когда список ввода проходит до конца.

Подробнее о различии см., Например, здесь .

---

Этот метод "открытого списка" представляет собой не список различий, но оба они очень тесно связаны. И нам на самом деле не нужен явный хвост где-либо здесь, кроме окончательного замораживания. Таким образом, мы просто делаем вызов O (n) length вместо явного O (1) Tail = [], который мы будем делать со списками различий, без bigg ie.

Большее влияние оказывает выбор списка вместо, например, дерева структуры данных. Деревья тоже могут быть открытыми, просто нужно использовать var/1 здесь и там. Следующим шагом является структура дерева. Нисходящее дерево с открытыми листьями не может быть повернуто (так как все вызовы ссылаются на один и тот же верхний узел), поэтому его глубина будет зависеть от упорядоченности входа. Для поддержания хорошего баланса деревья должны время от времени вращаться, а значит, и закрываться; и мы возвращаемся к традиционному коду передачи состояния, где каждый вызов получает два аргумента дерева - один до обновления, а другой после него:

    upd(T1, T2), next(T2, T3), more(T3, T4), ... 

вещи. Он должен быть использован в реальном коде. Есть некоторые библиотеки, которые делают это.

Этот код ответа является упрощенным c, чтобы быть простым и иллюстративным.

Answer 2

Try (взято из Logtalk difflist объект библиотеки):

member(Element, List-Back) :-
    List \== Back,
    List = [Element|_].
member(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    member(Element, Tail-Back).