Пролог: проверьте, имеют ли два списка одинаковые элементы

Question

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

myremove(X, [X|T], T).   
myremove(X, [H|T], [H|R]) :-
   myremove(X, T, R).

 same_elements([], []).
 same_elements([H1|T1], L2) :-      
    myremove(H1, L2, Nl2),  
    same_elements(T1, Nl2).

Это работает за исключением того, что

?- same_elements([b,c,a], X).

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

mylength([], 0).
mylength([_|T], R) :-
   mylength(T, Nr),
   R is Nr+1.

mymember(X, [X|_]).
mymember(X, [_|T]) :-
   mymember(X, T).

same_elements([], []).
same_elements([H1|T1], L2) :- 
   mylength([H1|T1], X),
   mylength(L2, Y),
   Y = X,
   mymember(H1, L2),
   myremove(H1, L2, Nl2),
   same_elements(T1, Nl2).

Теперь оба

?- same_elements([b,c,a], X).
?- same_elements(X, [b,c,a]). 

вернуть все результаты, но потом они просто висят в конце. Есть лучший способ сделать это?

Answer 1

Краткий ответ: да.

Но, прежде чем углубляться в это, возникает более интересный вопрос: как вы нашли эти проблемы? Тебе, наверное, очень повезло найти их! Я старался:

? - same_elements ([a, b, c, d, e, f, g], Xs).
Xs = [a, b, c, d, e, f, g];
Xs = [a, b, c, d, e, g, f];
Xs = [a, b, c, d, f, e, g];
Xs = [a, b, c, d, g, e, f];...

... и был поражен только созданными решениями. Нет, у меня не хватило терпения пройти все ответы. Но есть более простой способ проверить конкретный запрос: просто удалите ответы и сконцентрируйтесь только на том, остановится ли запрос. С этой целью я добавляю цель false:

? - same_elements ([a, b, c, d, e, f, g], Xs), false.

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

Чтобы еще больше сузить причину прекращения, мы добавим false цели в вашу программу. Эта измененная программа называется фрагментом сбоя. Таким образом, мы пытаемся сузить часть, которая несет ответственность за не прекращение. Если нам удастся добавить false Цели такие, что программа по-прежнему не заканчивается, у нас будет отличная подсказка, как решить проблему. Например:

same_elements ([], []).
same_elements ([H1 | T1], L2): -
  mylength ([H1 | T1], X), false,
  длина (L2, Y),
  Y = X,
  мой член (H1, L2),
  myremove (H1, L2, Nl2),
  same_elements (T1, Nl2).

Так что это почти ваша программа, за исключением того, что есть цель false в этом. Цели позади false зачеркнуты, чтобы прояснить, что они не имеют значения.

Теперь запрос завершается:

? - same_elements ([a, b, c, d, e, f, g], Xs), false.
ложный.

Итак, мы уже удалили слишком много. Следующая попытка:

same_elements ([], []).
same_elements ([H1 | T1], L2): -
  mylength ([H1 | T1], X),
  mylength (L2, Y), false,
  Y = X,
  мой член (H1, L2),
  myremove (H1, L2, Nl2),
  same_elements (T1, Nl2).

Теперь запрос не заканчивается!

Это означает: не смотрите на остальные части вашей программы. Все, что там написано, не может отменить этот цикл!

Итак, теперь мы можем обдумать видимую часть: она не заканчивается ни для

?- same_elements([a,b,c,d,e,f,g],Xs).

ни для

?- same_elements(Xs,[a,b,c,d,e,f,g]).

И преступник - только эта очень маленькая часть программы.

Ваша идея состояла в том, чтобы убедиться, что оба списка имеют одинаковую длину.

Вместо использования предиката длины определите новый:

list_same_length ([], []).
list_same_length ([_ | Xs], [_ | Ys]): -
    list_same_length (Xs, Ys).

Это теперь заканчивается для "обоих направлений".

Answer 2

Попробуй это:

      same(X, X).
same([A| B], [C| D]):-
    A=C,
    same(B,D).

он вернет истину, если они такие же. в противном случае - ложь.