members predicate in Prolog

I'd like to define a members predicate.

members(A, B) means that all members of the list A are members of list B. top(N) defines how long A can be.

This is my try:

top(5).

members([X], L):-
   member(X, L).
members([X| Xs], L):-
   member(X, L),
   members(Xs, L),
   length(Xs, M),
   top(N),
   M < N.

I'd like 开发者_StackOverflow社区to use it as follow:

members(L, [1,2,3]).

The problem with my implementation is that if I ; to get new answers, I'll finish with an ERROR: Out of local stack

?- members(I, [1,2,3]).
I = [1] ;
I = [2] ;
I = [3] ;
I = [1, 1] ;
I = [1, 2] ;
I = [1, 3] ;
I = [1, 1, 1] ;
I = [1, 1, 2] ;
I = [1, 1, 3] ;
I = [1, 1, 1, 1] ;
I = [1, 1, 1, 2] ;
I = [1, 1, 1, 3] ;
I = [1, 1, 1, 1, 1] ;
I = [1, 1, 1, 1, 2] ;
I = [1, 1, 1, 1, 3] ;
;ERROR: Out of local stack

How can I change my code to prevent this out of memory?

As already mentioned, your problem is that you do the length check after the recursive call, meaning that the recursion is unbounded. Unfortunately, just moving the length check above the recursive call like this...

members([X], L):-
   member(X, L).
members([X|Xs], L):-
    length(Xs, M),
    top(N), M < N,
    member(X, L),
    members(Xs, L).

...is not so good as we get this:

L = [3, 1, 2, 3, 3] ;
L = [3, 2, 2, 3, 3] ;
L = [3, 3, 2, 3, 3] ;
L = [3, 1, 3, 3, 3] ;
L = [3, 2, 3, 3, 3] ;
L = [3, 3, 3, 3, 3] ;
ERROR: Out of global stack

While this gets us the answer, it's not that useful as it can't be put inside a larger predicate since it breaks. It breaks because we have only pushed the problem further along. Here's why:

The problem is that you are constructing the list in a top-down manner. In other words, we define the list like this: List = [Head|Tail] where we stipulate some constraints on Head and state that Tail is made up of a list of elements defined by the same constraints and bounded by a base case. This means that while we are in the middle of the recursive call, we actually only have access to Head - we cannot access the contents of Tail as it is only constructed once the interpreter has gone all the way down and reached the base case (i.e. members([X], L) :-) and then has successively added each Tail to its Head until the final List is constructed.

It may look like we have access to the length, since the length/2 call is sitting there in the middle of the recursive predicate, however since the variable being passed into length/2 for the list is at this stage not bound to anything, Prolog waits until it has finished the recursive calls beneath this point before calculating the length. The problem of course is that the length check is what is bounding the recursion, so it will just continue until it runs out of memory.

While top-down recursion tends to be the default way of constructing Prolog predicates, as this example shows, sometimes we need access to the data structure we are creating. The solution is to use bottom-up recursion. This is implemented in Prolog by means of an accumulator predicate, which starts with an empty list and proceeds to build the list up one by one, by passing the accumulator list (which is a fully ground list) through the recursive predicate. Here's how I would write an accumulator predicate for this problem:

members(I,L) :-
    members_accumulator([],I,L).

members_accumulator(Tail,I,L) :-
    length(Tail, M),
    top(N),
    M < N,
    member(X, L),
    members_accumulator([X|Tail],I,L).
members_accumulator(I,I,_).

We need two predicates, as the first is a wrapper around the accumulator which passes the empty list to the accumulator predicate. The base case no longer has anything to do with the empty list - all it has to do is state that the final accumulator list is actually the final list that we're after (which has been threaded through the accumulator predicate just for this purpose). Also, in this case, the accumulator predicates need to be in this order otherwise there will be one choice point that evaluates as false right at the end.

Getting ones head around recursion in Prolog and when you need to use bottom-up recursion rather than top-down is a non-trivial feat. I didn't really have a solid grasp on it at all until I had a good read through The Art of Prolog. There should also be plenty of info about accumulators online.

Here is an alternate implementation which does'nt require calculating the length of the list. Here N is the length of list A. This solution gives all the answers without going out of stack.

members([X],L,1) :- member(X,L).
members([H|T],L,N) :- N>1 , member(H,L) , N1 is N-1, members(T,L,N1).

Example execution:

?- members(L,[1,2,3],5).
L = [1, 1, 1, 1, 1] ;
L = [1, 1, 1, 1, 2] ;
L = [1, 1, 1, 1, 3] ;
L = [1, 1, 1, 2, 1] ;
...
L = [3, 3, 3, 1, 2] ;
L = [3, 3, 3, 3, 1] ;
L = [3, 3, 3, 3, 2] ;
L = [3, 3, 3, 3, 3] ;
No

You do the check for the depth after the recursion. So the depth of the recursion is not limited, only the resulting lists are discarded as too long.

Use meta-predicate maplist/2, lambdas, and membership predicate memberd/2 and simply write:

:- use_module(library(lambda)).

members(As,Bs,N) :-
   length(Xs,N),
   append(As,_,Xs),
   maplist(Bs+\A^memberd(A,Bs), As).

Sample query with abbreviated answer sequence:

?- members(As,[1,2,3],5).
As = [         ] ;
As = [        1] ; As = [        2] ;           As = [        3] ;
As = [      1,1] ; As = [      1,2] ; /* ... */ As = [      3,3] ;
As = [    1,1,1] ; As = [    1,1,2] ; /* ... */ As = [    3,3,3] ;
As = [  1,1,1,1] ; As = [  1,1,1,2] ; /* ... */ As = [  3,3,3,3] ;
As = [1,1,1,1,1] ; As = [1,1,1,1,2] ; /* ... */ As = [3,3,3,3,3] ;
false.

Above query universally terminates. Let's look at the size of the solution set:

?- setof(As,members(As,[1,2,3],5),Ass), length(Ass,N_Solutions).
Ass         = [[],[1],[1,1],[1,1,1],[1,1,1|...],[1,1|...],[1|...],[...|...]|...],
N_Solutions = 364.

?- 364 =:= 1 + 3 + 3^2 + 3^3 + 3^4 + 3^5.
true.