Используйте cut в Prolog для определения функции Once_member / 2 - PullRequest
Новая
       54

Используйте cut в Prolog для определения функции Once_member / 2

8 голосов
/ 27 ноября 2011

Отказ от ответственности: Это неофициальная и не оцененная курсовая работа, которую я должен выполнять в свое время. Я сам попробовал, потерпел неудачу и теперь ищу какое-то руководство.

Я пытаюсь реализовать версию функции member / 2, которая будет возвращать членов для списка только один раз.

Например: 

| ?- member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
X = 1 ? ;

Мне бы хотелось, чтобы каждый номер печатался только один раз. 

| ?- once_member(X, [1,2,3,1]).
X = 1 ? ;
X = 2 ? ;
X = 3 ? ;
no

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

Пока мне удалось получить: 

once_member(E, [E | L]) :- !.
once_member(E, [_, L]) :-
    once_member(E, L).

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

Я просмотрел свои заметки о курсе, а также: http://www.cs.ubbcluj.ro/~csatol/log_funk/prolog/slides/5-cuts.pdf и Программирование на прологе (Google Книги)

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

Нам также сказали сделать еще один метод, который использует отрицание '\ +' из-за ошибки, но, надеюсь, это может быть проще, если резать для меня сучко?

Ответы [ 4 ]

2 голосов
/ 03 апреля 2015

Удалить лишние ответы и оставайтесь чистыми!

Мы определяем memberd/2 на основе if_/3 и (=)/3: 

memberd(X, [E|Es]) :-
   if_(X = E, true, memberd(X, Es)).

В частности, для мета-предикатов иногда может пригодиться другой порядок аргументов: 

list_memberd(Es, X) :-
   memberd(X, Es).

Пример запроса: 

?- memberd(X, [1,2,3,1]).
X = 1 ;
X = 2 ;
X = 3 ;
false.
1 голос
/ 28 ноября 2011 
once_member(X, Xs) :-
   sort(Xs, Ys),
   member(X, Ys).

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

?- X = 1, once_member(X, [A,B]).
X = A, A = 1 ;
X = B, B = 1.

?- X = 1, once_member(X, [A,A]).
X = A, A = 1.
1 голос
/ 27 ноября 2011

Решение с cut ... сначала это звучит довольно хлопотно.

Если предположить, что будет создан первый аргумент, решение тривиально: 

once_member(X,L):-
    member(X,L),!.

, но это не такПоведение, которое вы хотите, если первый аргумент не был создан.
Если мы знаем домен элементов списков (например, числа от 1 до 42), мы можем создать первый аргумент: 

once_member(X,L):-
    between(1,42,X),
    member_(X,L).

member_(X,L):-
    member(X,L),!.

но на данный момент это очень неэффективно

, я начал верить, что это невозможно сделать только с помощью разреза (при условии, что мы не используем + или list_to_set / 2
ох, подождите! <вставьте смайлик идеиздесь>

Если бы мы могли реализовать предикат (например, list_to_set / 2 swi-prolog), который бы взял список и создал список, в котором удалены все дублирующиеся элементы, мы могли бы простоиспользуйте обычный member / 2 и не получите повторяющихся результатов. Попробуйте, я думаю, что вы сможете написать это сами.

-------- Спойлеры ------------ 

    one_member(X,L):-
        list_to_set(L,S),
        member(X,S).

    list_to_set([],[]).
    list_to_set([H|T],[H|S]):-
        remove_all(H,T,TT),
        list_to_set(TT,S).

%remove_all(X,L,S): S is L if we remove all instances of X
    remove_all(_,[],[]).
    remove_all(X,[X|T],TT):-
        remove_all(X,T,TT),!.
    remove_all(X,[H|T],[H|TT]):-
        remove_all(X,T,TT).

Как вы видите, мы должны использовать вырез в remove_all / 3, поскольку в противном случае третье предложение может быть сопоставлено с remove_all(X,[X|_],_), поскольку мы не указываем, что H отличается от X. Я считаю, что решение с notтривиальный.

Кстати, решение with не может быть охарактеризовано как более декларативное, чем решение с cut;вырез, который мы использовали, обычно называется красным разрезом, поскольку он изменяет поведение программы.И есть другие проблемы;обратите внимание, что даже с разрезом remove_all(1,[1,2],[1,2]) будет успешным.

С другой стороны, неэффективно дважды проверять условие.Поэтому оптимальным было бы использование структуры if-then-else (но я предполагаю, что вам также не разрешено использовать ее; ее реализация может быть выполнена с разрезом).

С другой стороны,есть другая, более легкая реализация с not: вам нужно не только проверить, является ли X членом списка, но также и то, встречались ли вы ранее;поэтому вам понадобится аккумулятор:

------------- Спойлеры -------------------- 

once_member(X,L):-
    once_member(X,L,[]).
once_member(X,[X|_T],A):-
    \+once_member(X,A).
once_member(X,[H|T],A):-
    once_member(X,T,[H|A]).
0 голосов
/ 27 ноября 2011

Вот подход, который использует сокращение в определении Once_member / 2 вместе с классическим предикатом member / 2 : 

once_member(X,[H|T]) :-
    member(H,T),
    !,
    once_member(X,T).
once_member(H,[H|_]).
once_member(X,[_|T]) :-
    once_member(X,T).

Применительно к примеру выше: 

?- once_member(X,[1,2,3,1]).

X = 2 ;

X = 3 ;

X = 1 ;
no

Примечание: Несмотря на нечетное определение из трех предложений, Once_member / 2 подходит для оптимизации последнего вызова / хвостовой рекурсии из-за размещения разреза перед его первым сам-вызов.

...