CODEWITHSUNDEEP
prolog
General_9
General_9

Reputation: 2319

Prolog Tail Recursive procedure to count uninstantiated variables in list

I am trying to write a Tail Recursive procedure to count the number of uninstantiated variables in a list. I am a little stuck, where am I going wrong.

My current query is below:

count([S,L],N) :- var(S), !, N+1.
count([L],N).

Upvotes: 1

Views: 2180

Answers (3)

gusbro
gusbro

Reputation: 22585

Note: this answer presents a solution that is recursive but not tail recursive. For a tail recursive solution you should use an accumulator as can be shown in other answers from this question.

As with any recursive procedure, you should add a proper base case. In this case, it should be a clause with an empty list that returns unifies 0 with the number of uninstantiated variables:

count([], 0).

Check the clause you've written. It takes as input a list of two elements instead of a list represented as a Head item and a tail list, and it really does nothing with N:

count([Head|Tail], M):- 
    var(Head), 
    !, 
    count(Tail, N), 
    M is N+1.

And finally, you should also add a clause to deal with the case when the first item of the list is not an uninstantiated variable:

count([_|Tail], N):- count(Tail, N).

Upvotes: 2

Jiri Kriz
Jiri Kriz

Reputation: 9292

Here is a tail recursion for counting variables in a list. It uses the technique of accumulators:

count(L, N) :- count(L, 0, N).     % L=list, N=count, 0=value of the sum accumulator S
count([], S, S) :- !.              % the innermost call, the accumulator S (2nd arg) "copied" to final result (3rd arg)
count([H| T], S, N):- var(H), !, S1 is S+1, count(T, S1, N). % increase accumulator if H is var
count([H| T], S, N):- count(T, S, N).    % keep accumulator if H is not var

No calls follow the last recursive calls in all clauses.

Upvotes: 2

Orbling
Orbling

Reputation: 20602

There is no recursion here, because in order to have recursion, you must define something in terms of itself - you'll notice an absence of the count/2 rule on the right hand side in your code.

% two paths, variable and non-variable
% and a base case to start the count
count([S|L], N) :- var(S), !, count(L, N0),  N is N0+1.
count([S|L], N) :- nonvar(S), !, count(L, N).
count([], 0).

Alternatively, this can be done simply with findall/3.

count_alt(L, N) :- findall(S, (member(S, L), var(S)), D), length(D, N).

Upvotes: 0

Related Questions