Prolog allMember function

Question

I am trying to write a function that takes in two lists and returns true if every element in the first list appears at least once in the second list. Example:

allMember(X, [a,b]).  
X = [] ;  
X = [a] ;  
X = [b] ;  
X = [a a] ;  
X = [a b] ;  
X = [b a] ;  
X = [b b] ;  
false.

The trouble is that after the final ; the program loops infinitely checking every possible list. How can I fix this?

allmember([], _).
allmember([F|R], L2) :- length([F|R], Len1),
                        length(L2, Len2),
                        Len1 =< Len2,
                        member(F, L2),
                        allmember(R, L2).

Answer 1

The way you have described the predicate, it is trivial:

my_subset([], _Set) :- !.
my_subset([X|Xs], Set) :-
    memberchk(X, Set),
    my_subset(Xs, Set).

This is also the implementation in the standard library of SWI-Prolog, for example.

Your code, however, says something else:

"all_member(L1, L2) is true if L1 is a combination of the elements of L2, with length up to (and including) the length of L2."

all_member(L1, L2) :-
    length(L2, Max_len),
    between(0, Max_len, Len),
    length(L1, Len),
    all_member_1(L1, L2).

all_member_1([], _).
all_member_1([X|Xs], L) :-
    member(X, L),
    all_member_1(Xs, L).

Here, you first get the maximum length (the total length of the second argument), then enumerate the lists of length 0 to that maximum length, and then apply member/2 to each element of each list.

The between/3 in all_member/2 gives you all valid lengths of the first list. The member/2 in all_member_1/2 gives you all possible combinations of elements from the second list.

If you know how exaclty you want to use the predicate, this might not be a good enough solution. Try for example the most general query, ?- all_member(L1, L2). You need to be more specific about this.

Answer 2

I fixed the problem with the following code:

find( L, L2, I) :- length(L2, Length2),   
                   range(0, Length2, PossI),
                   member(I, PossI),
                   find1(L, L2, I).

find1([F1|[]], [F1|_], 0).

find1([F1|R1], [F1|R2], 0) :- find(R1, R2, 0).                           

find1(L1, [_|R2], I) :- M is (I-1),
                       find(L1, R2, M).