Count empty list in Prolog list of list

问题:

Learning Prolog still,

I made the predicate empties(L,R) that accepts a list of groups in L (i.e.: [ [ 2 ] ,[ 1 ] ,[ ] ] ) and the R indicates the number of empty groups within the group, so for this particular case it should go

empties([[2],[1],[]],1)

it gives 'yes' for this particular case, which seems to make sense.

if i ask:

empties([[],[2],[2],[]],X).

it will answer X = 2, which again makes sense, but when i replace the X with a 0, it gives a yes too, and i can't get a grasp on why. It seems to be asking "at least X" and not exactly the number of occurences.

This is the code:

isit([]).
empties([],0).
empties([X|L] , R):-
        isit(X),
        empties(L,K),
        R is K+1.

empties([X|L] , K):-
        empties(L,K).

Thank you for your precious help.

回答1:

What you want is a set of rules that define the number of empty list elements. Ideally, these should (a) give you all of the correct answers, (b) not give you incorrect answers, and (c) hopefully not overlap in giving you answers (provide the same answer multiple times).

You have three clauses for your empties/2 predicate, which we'll examine.

empties([],0).

This one says

The empty list has no empty list elements.

That is logically correct.

empties([X|L] , R):-
    isit(X),
    empties(L,K),
    R is K+1.

This can be rewritten/simplified:

empties([[]|L], R) :-
    empties(L, K),
    R is K + 1.

This says that

The number of empty list elements in the list [[] | L] is R if the number of empty list elements in the list L is K, and R is K + 1.

That also is logically correct.

empties([X|L] , K):-
    empties(L,K).

This rule says that

The number of empty list elements in the list [X|L] {no matter what X is!} is K if the number of empty list elements in the list L is K.

This is certainly not logically correct, and this is why your query, empties([[],[2],[2],[]],0). succeeds. If X = [], this rule still succeeds. This third clause, in conjunction with your first clause of empties([], 0), will allow any query of the form empties(L, 0), where L is a list, to succeed. In this case, you must enforce that X is not empty, to make the rule mean:

The number of empty list elements in the list [X|L] is K if X is not empty, and the number of empty list elements in the list L is K.

So your third rule must ensure that X is not the empty list for it to be satisfied properly. This can be done this way:

empties([X|L] , K) :-
    X \= [],
    empties(L,K).

Or, you can do it more elegantly this way:

empties([[_|_]|L], K) :-
    empties(L, K).

[_|_] is an anonymous list of one or more elements.

回答2:

Here is another approach using findall/3 predicate:

empties(L,N):-findall(X, (member(X,L),X = []) ,L1),length(L1,N).

What te above solution does is that it finds all X, which are member of L and are empty lists and adds it to L1, then it returns the length of L1.

Examples:

?- empties([[],[2],[2],[]],X).
X = 2.

?- empties([],X).
X = 0.

?- empties([[]],X).
X = 1.

?- empties([[],[_]],X).
X = 1.

?- empties([[],[2],[2],[]],2).
true.

回答3:

You understand how to take a list apart:

[X|L]

You understand how to use recursion:

empties([X|L] , R):-
    ...
    empties(L,K),

You understand a base case with recursion:

empties([],0).

You understand how to do arithmetic with Prolog:

R is K+1

You are using guards whether you know it or not:

empties([],0)    % [] is the guard 

So you have the basic mechanics necessary to solve this problem but putting the pieces together to work with Prolog eludes you for this problem.

Solution

The key to the below solution uses two guard statements that complement each other, meaning only one or the other can be chosen. Think of them like an if statement in that they choose one or the other predicates. Once you understand how the guards work in Prolog don't think of them as if statements when doing Prolog because you will then start to think procedurally instead of logically which will not be good; they are capable of so much more.

H == []
H \= []

Also it threads the count variable R through the predicates.

empties([], R, R).

empties([H|T], R0, R) :-
    H == [],
    R1 is R0 + 1,
    empties(T, R1, R).

empties([H|T], R0, R) :-
    H \= [],
    empties(T, R0, R).

empties(L,R) :-
    empties(L,0,R).

Output

?- empties([],X).
X = 0.

?- empties([[]],X).
X = 1 ;
false.

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

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

?- empties([[],[]],X).
X = 2 ;
false.

?- empties([[a],[],[b]],X).
X = 1 ;
false.

?- empties([[],[a],[b]],X).
X = 1 ;
false.

?- empties([[a],[b],[]],X).
X = 1 ;
false.

?- empties([[],[],[]],X).
X = 3 ;
false.