Как мне сделать это больше logi c -y?

Question

Я пытался решить следующую проблему из упражнений главы 6 по LPN! :

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

set([2,2,foo,1,foo, [],[]],X).

должен дать результат

X = [2,foo,1,[]].

Я получил это:

set_([], [], []).
set_([H|Bag], [H|Set], Dups):-
  set_(Bag, Set, Dups),
  \+ member(H, Set),
  \+ member(H, Dups).
set_([H|Bag], Set, [H|Dups]):-
  set_(Bag, Set, Dups),
  member(H, Set).

set(Bag, Set, Rest):-
    reverse(BagR, Bag),
    set_(BagR, SetR, RestR),
    reverse(SetR, Set),
    reverse(RestR, Rest).

set(Bag, Set):- set(Bag, Set, _).

Но меня совсем не впечатлила потребность в этих 3 reverse/2. Может ли кто-нибудь помочь мне найти более элегантное решение этой проблемы?

Сначала я попытался сделать правильное рекурсивное решение, но он застрял, пытаясь доказать, что проблема может «go on». Например, если бы я набрал set_([1,2,1], L, R), он застрял бы, доказывая set(_, [1,2|_], [1|_]).. Если у вас есть отзывы о том, как этого избежать, дайте мне знать!

Edit 1 : В итоге я использовал foldl/4:

pushForward(X, [Set0, Rest], [Set, Rest]):-
  \+ member(X, Set0),
  append([Set0, [X]], Set).
pushForward(X, [Set, Rest0], [Set, Rest]):-
  member(X, Set),
  append([Rest0, [X]], Rest).

set(Bag, Set, Rest):- foldl(pushForward, Bag, [[],[]], [Set, Rest]).

set(Bag, Set):- set(Bag, Set, _).

Однако это не Я не вникаю в суть проблемы. Я хотел бы указать отношения модели и спросить, «что подходит для этих отверстий». Это решение делает противоположное - оно принимает некоторые значения и меняет их до тех пор, пока нам больше нечего делать - и это должно быть задачей Prolog, а не моей. ;)

Answer 1

Название не идеальное. Используя library(reif):

list_nub([], []).
list_nub([E|Es], [E|Gs]) :-
   tfilter(dif(E), Es, Fs),
   list_nub(Fs, Gs).

?- Xs = [_,_,_], Ys = [_,_], list_nub(Xs, Ys).
   Xs = [_A,_A,_B], Ys = [_A,_B], dif(_A,_B)
;  Xs = [_A,_B,_A], Ys = [_A,_B], dif(_A,_B)
;  Xs = [_A,_B,_B], Ys = [_A,_B], dif(_A,_B)
;  false.
?- Xs = [_,_,_], Ys = [_], list_nub(Xs, Ys).
   Xs = [_A,_A,_A], Ys = [_A]
;  false.
?- Xs = [_,_,_], Ys = [_,_,_], list_nub(Xs, Ys).
   Xs = [_A,_B,_C], Ys = [_A,_B,_C], dif(_A,_B), dif(_A,_C), dif(_B,_C).
?- dif(A,B), Xs = [A|_], Ys = [B|_], list_nub(Xs, Ys).
   false.

Answer 2

В Prolog всегда стоит искать самое простое решение, поэтому

• копируйте элементы из InList в Accumulator, только , если их еще нет, используя простой рекурсия.
• обратное преобразование полученного Accumulator в OutList.

В качестве микро-оптимизации вы можете использовать memberchk / 2 вместо member / 2, чтобы проверить, следует ли отбросить элемент.

Поскольку вы изучаете язык, я не буду показывать полное решение.