Prolog: Matching One or More Anonymous Variables

Question

[_, [ X , _ ],_] will match a list like [d, [X,a], s]. Is there a way to match it to any pattern where there is one or more anonymous variables? ie. [[X,a],s] and [[d,a],[p,z], [X,b]] would match?

I am trying to write a program to count the elements in a list ie. [a,a,a,b,a,b] => [[a,4],[b,2]] but I am stuck:

listcount(L, N) :-  listcountA(LS, [], N).
listcountA([X|Tail], [? [X, B], ?], N) :- B is B+1, listcountA(Tail, [? [X,B] ?], N).
listcountA([X|Tail], AL, N) :- listcountA(Tail, [[X,0]|AL], N).

Thanks.

Answer 1

A variable match a term, and the anonimus variable is not exception. A list is just syntax sugar for a binary relation, between head and tail. So a variable can match the list, the head, or the tail, but not an unspecified sequence.

Some note I hope will help you:

listcount(L, N) :- listcountA(LS, [], N).

In Prolog, predicates are identified by name and num.of.arguments, so called functor and arity. So usually 'service' predicates with added arguments keep the same name.

listcountA([X|Tail], [? [X, B], ?], N) :- B is B+1, listcountA(Tail, [? [X,B] ?], N).

B is B+1 will never succeed, you must use a new variable. And there is no way to match inside a list, using a 'wildcard', as you seem to do. Instead write a predicate to find and update the counter.

A final note: usually pairs of elements are denoted using a binary relation, conveniently some (arbitrary) operator. For instance, most used is the dash.

So I would write

listcount(L, Counters) :-
    listcount(L, [], Counters).

listcount([X | Tail], Counted, Counters) :-
    update(X, Counted, Updated),
    !, listcount(Tail, Updated, Counters).
listcount([], Counters, Counters).

update(X, [X - C | R], [X - S | R]) :-
    S is C + 1.
update(X, [H | T], [H | R]) :-
    update(X, T, R).
update(X, [], [X - 1]).  % X just inserted

update/3 can be simplified using some library predicate, 'moving inside' the recursion. For instance, using select/3:

listcount([X | Tail], Counted, Counters) :-
    ( select(X - C, Counted, Without)
    ->  S is C + 1
    ;   S = 1, Without = Counted
    ),
    listcount(Tail, [X - S | Without], Counters).
listcount([], Counters, Counters).

Answer 2

I'll preface this post by saying that if you like this answer, consider awarding the correct answer to @chac as this answer is based on theirs.

Here is a version which also uses an accumulator and handles variables in the input list, giving you the output term structure you asked for directly:

listcount(L, C) :-
    listcount(L, [], C).
listcount([], PL, PL).
listcount([X|Xs], Acc, L) :-
    select([X0,C], Acc, RAcc), 
    X == X0, !,
    NewC is C + 1,
    listcount(Xs, [[X0, NewC]|RAcc], L).
listcount([X|Xs], Acc, L) :-
    listcount(Xs, [[X, 1]|Acc], L).

Note that listcount/2 defers to the accumulator-based version, listcount/3 which maintains the counts in the accumulator, and does not assume an input ordering or ground input list (named/labelled variables will work fine).

Answer 3

[_, [X, _], _] will match only lists which have 3 elements, 1st and 3rd can be atoms or lists, second element must be list of length 2, but i suppore you know that. It won't match to 2 element list, its better to use head to tail recursion in order to find element and insert it into result list. Heres a predicate sketch, wich i bet wont work if copy paste ;)

% find_and_inc(+element_to_search, +list_to_search, ?result_list)
find_and_inc(E, [], [[E, 1]]);
find_and_inc(E, [[E,C]|T1], [[E,C1]|T2]) :- C1 is C+1;
find_and_inc(E, [[K,C]|T1], [[K,C]|T2]) :- find_and_inc(E, T1, T2).