Существует ли элемент в списке списков?

Ответ 1

Проблема в том, что [[H|T1]|T2] соответствует только первому списку, имеющему хотя бы один элемент. Действительно: [[],[1,4],[2,5]], например, не объединяется с [[H|T1]|T2].

Итак, вы можете решить проблему, добавив предложение:

memberlist(X,[[]|T2]) :-
    memberlist(X,T2).

получаем:

memberlist(X,[[X|_]|_]).
memberlist(X,[[H|T1]|T2]) :-
    memberlist(X,[T1|T2]).
memberlist(X,[[]|T2]) :-
    memberlist(X,T2).

в первом разделе также используются символы подчеркивания, чтобы указать, что мы "не заинтересованы" в этих переменных. Это распространено для программ Prolog (вероятно, интерпретатор предупреждал, что T1 и T2 упоминались только один раз).

Поэтому, если первый список исчерпан, мы просто переходим к следующему списку.

Ваш предикат делает много "упаковки" и "распаковки". Кроме того, мы можем использовать встроенный member/2. Поэтому мы можем переписать его:

memberlist(X,[H|_]) :-
    member(X,H).
memberlist(X,[_|T2]) :-
  memberlist(X,T2).

Ответ 2

memberlists(X, Xss) :-
   member(Xs, Xss),
   member(X, Xs).

Подобно member/2, это дает много избыточных ответов, таких как:

?- memberlists(X, [[a,a],[a],[a]]).
   X = a
;  X = a  % redundant
;  X = a  % redundant
;  X = a. % redundant

В качестве альтернативы вы можете использовать memberd/2 вместо member/2.

memberlists2(X, Xss) :-
   memberd(Xs, Xss),
   memberd(X, Xs).

?- memberlists2(X, [[a,a],[a],[a]]).
   X = a
;  X = a   % redundant
;  false.

Это намного лучше, но все же не удаляет все избыточные ответы.

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

Ответ 3

Как насчет этого?

list([])     --> [].
list([L|Ls]) --> [L], list(Ls).

concatenation([]) --> [].
concatenation([List|Lists]) -->
   list(List),
   concatenation(Lists).

memberd(X, [X|_Xs]).
memberd(X, [Y|Xs]) :-
   dif(X,Y),
   memberd(X, Xs).

memberlists(X, Lists):-
   phrase(concatenation(Lists),List),
   memberd(X,List).

Ответ 4

Вот более компактная версия очень приятного второго решения от пользователя @user27815 (s (0) для обоих решений). На самом деле нет необходимости использовать reification в предикате member_lists/2, как это делается в member_lists_t/3. Фактически использование memberd_t/3 в качестве первого аргумента if_/3 достаточно для завершения после нахождения первого решения, Следовательно, отношение может быть выражено как единое правило с одной целью:

member_lists(X,[H|T]) :-
  if_(memberd_t(X,H),true,member_lists(X,T)).

Запрос

   ?- member_lists(X,[[a,a],[a]]).
X = a ? ;
no

создает только одно решение. Запрос

   ?- member_lists(X,[[X|_]|_]).

true

заканчивается детерминистически.

Ответ 5

С if_/3:

memberd_t(_,[],false).
memberd_t(X,[Y|Ys],Truth) :-
 if_(X=Y, Truth=true, memberd_t(X,Ys,Truth)).

member_lists_t(_,[],false).
member_lists_t(X,[H|T],Truth):-
 if_(memberd_t(X,H),Truth=true,member_lists_t(X,T,Truth)).

member_lists(X,Lists):-
 member_lists_t(X,Lists,true).

Ответ 6

Вот мой подход с использованием sort/2 и flat/2, которые выравнивают список только на один уровень:

memberlists(X, Xss) :- Xss = [_|_], 
                       flat(Xss, FL), 
                       sort(FL, OutL), 
                       memberd(X, OutL).

memberd(X, [X|_Xs]).
memberd(X, [Y|Xs]) :-
   dif(X,Y),
   memberd(X, Xs).                       

flat([],[]).
flat([H|T],R) :- H = [_|_], flat(T,T1), append(H,T1,R).

Testcases:

 ?- memberlists(X,[[a,A]]), A = a.
X = A, A = a ;
false.

?- memberlists(X,[[a]|Xs]), Xs = [_|_].
Xs = [[X]] ;
X = a,
Xs = [[_G13004]],
dif(a, _G13004) ;
Xs = [[X, _G12784]] .

?- memberlists(X,[[a,a],[Y],[b]]).
X = Y ;
X = a,
dif(a, Y) ;
X = b,
dif(b, Y) ;
false.

?- memberlists(X,[[a,a],[a],[a]]).
X = a ;
false.

?- memberlists(X,[[[a,a],[a],[a]]]).
X = [a] ;
X = [a, a] ;
false.

?- memberlists(X,[L]).
L = [X] ;
L = [X, _G12710] ;
L = [_G12923, X],
dif(X, _G12923) ;
L = [X, _G12710, _G12716] ;
L = [_G12935, X, _G12941],
dif(X, _G12935) . (and goes on...)

?- memberlists(X,L).
L = [[X]]
L = [[X, _G12704]] ;
L = [[_G12920, X]],
dif(X, _G12920) ;
L = [[X, _G12704, _G12710]] ;
L = [[_G12932, X, _G12938]],
dif(X, _G12932) ;
L = [[_G13018, _G13021, X]],
dif(X, _G13021),
dif(X, _G13018) ;
L = [[X, _G12704, _G12710, _G12716]] . (and goes on...)

Ответ 7

Ответ на исходный вопрос выглядит следующим образом:

memberlist(X, [X| _]) :- !.
memberlist(X, [[A|B]|_]) :-
    memberlist(X,[A|B]), !.
memberlist(X, [_ | Rest]) :-
    memberlist(X, Rest).

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

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

Код для сглаживания из cs.uni-potsdam.de:

flatten(List, Flat) :-
    flatten(List, Flat, []).

flatten([], Res, Res) :- !.
flatten([Head|Tail], Res, Cont) :-
        !,
        flatten(Head, Res, Cont1),
        flatten(Tail, Cont1, Cont).
flatten(Term, [Term|Cont], Cont).

Код для поворота списка для установки (из http://www.cs.oswego.edu/~odendahl/coursework/notes/prolog/synopsis/)

member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).

make_set([],[]).
make_set(X,Y) :- setof(Z,member(Z,X),Y).

Итак, окончательная часть:

setofmembers(NestedLists, Set) :-
    flatten(NestedLists,Flat),
    make_set(Flat,Set).

memberlist2(X,Lists) :-
    setofmembers(Lists,Set),
    member(X,Set).

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