Does an element exists in a list of lists?

问题:

I want to find if a given element exists in a list of lists. I am only getting true if the element exists somewhere is the first list of lists.

Any advice?

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

回答1:

The problem is that [[H|T1]|T2] only matches given the first list has at least one element. Indeed: [[],[1,4],[2,5]] for instance does not unify with [[H|T1]|T2].

So you can solve the problem by adding a clause:

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

thus we obtain:

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

the first clause also uses the underscores to specify that we are "not interested" in these variables. This is common for Prolog programs (probably the interpreter warned that T1 and T2 were mentioned only once).

So in case the first list is exhausted, we simply move to the next list.

Your predicate does a lot of "packing" and "unpacking". Furthermore we can make use of the member/2 builtin. So we can rewrite it:

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

回答2:

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

Similar to member/2, this produces many redundant answers like:

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

Alternatively, you might want to use memberd/2 in place of member/2.

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

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

This is much better, but still does not remove all redundant answers.

For a solution that removes all such redundancies a bounty has been set.

回答3:

What about this?

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:

Here is a more compact version of the very nice 2nd solution by @user27815 (s(0) for both solutions). There is actually no need to use reification in the predicate member_lists/2 as is done in member_lists_t/3. In fact using memberd_t/3 as first argument of if_/3 is sufficient for termination after finding the first solution. Hence the relation can be expressed as a single rule with a single goal like so:

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

The query

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

is only producing a single solution. The query

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

true

is terminating deterministically.

回答5:

With 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:

Here is my approach using sort/2 and flat/2 that flatten a list only one level:

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:

The answer to the original question is as follows:

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

This solution will only give one result when X is given a value in the query. With a little more work this can be changed to a tail recursive algorithm. But the question seems to expanded to look for a way to have this return the set of singleton elements that are members of all the embedded lists.

The solution is to flatten the lists into a single list and then turn the list into a set.

The code for flatten from cs.uni-potsdam.de is:

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).

The code for turning a list to set (from 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).

So the finally piece is:

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

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

Of course this is not totally satisfactory because it is not tail recursive and it not very efficient. But coming up with an efficient tail recursive solution would take me a couple hours and I have to mow the lawn.