Program to find every list of X in Prolog

Question

I am starting on learning Prolog. This program tries to get all occurrences of a given element:

occurences(_, [], Res):- Res is [].
occurences(X, [X|T], Res):- 
    occurences(X,T,TMP),
    Res is [X,TMP].
occurences(X, [_|T], Res):- occurences(X,T,Res).

But here is the error:

?- occurences(a,[a,b,c,a],Res).
ERROR: is/2: Arithmetic: `[]/0' is not a function
^  Exception: (11) _G525 is [] ? creep
   Exception: (10) occurences(a, [], _G524) ? creep
   Exception: (9) occurences(a, [a], _G524) ? creep
   Exception: (8) occurences(a, [c, a], _G524) ? creep
   Exception: (7) occurences(a, [b, c, a], _G524) ? creep
   Exception: (6) occurences(a, [a, b, c, a], _G400) ? creep

score 5 · Accepted Answer · answered Dec 01 '12 at 20:27

5

In addition to what others wrote, consider using the dif/2 constraint:

occurrences(_, [], []).
occurrences(X, [X|Ls], [X|Rest]) :-
        occurrences(X, Ls, Rest).
occurrences(X, [L|Ls], Rest) :-
        dif(X, L),
        occurrences(X, Ls, Rest).

You can now use the predicate in all directions, for example:

?- occurrences(X, [a,a,b], Os).
X = a,
Os = [a, a] ;
X = b,
Os = [b] ;
Os = [],
dif(X, b),
dif(X, a),
dif(X, a) ;
false.

The last solution means that the list of occurrences is empty if X is different from both a and b.

answered Dec 01 '12 at 20:27

mat

40,498
3
51
78

+1: What is the best way to make this as determinate as possible while still retaining its declarative properties? – false Dec 01 '12 at 20:40
Please refer to [my question about this](http://stackoverflow.com/q/13664870/772868) – false Dec 01 '12 at 23:39

CapelliC · Answer 2 · 2012-12-01T23:52:28.470

you're already been advised by Rubens about your mistake. I'll just add a style note: often in Prolog it's preferred to directly code the pattern in head arguments:

occurences(_, [], []).
occurences(X, [X|T], [X|TMP]) :- 
    occurences(X,T,TMP), !.
occurences(X, [_|T], Res) :-
    occurences(X,T,Res).

I corrected the second clause 'output' from [X,TMP] to [X|TMP], and note the cut: without it the procedure yields more results than required:

?- occurences(a,[a,b,c,a],Res).
Res = [a, a] ;
Res = [a] ;
Res = [a] ;
Res = [] ;
false.

with the cut:

?- occurences(a,[a,b,c,a],Res).
Res = [a, a].

edit @false spoiled a nasty bug: here a correction, using the if/then/else construct

occurences(_, [], []).
occurences(X, [Y|T], Os) :-
    (   X = Y
    ->  Os = [X|R]
    ;   Os = R
    ),
    occurences(X,T,R).

Your program succeeds incorrectly for `occurences(a,[a,b,c,a],[a]).` So your program is not steadfast for the 3rd argument. It is a good example how **not** to set the cut. — false, Dec 01 '12 at 21:05

score 0 · Answer 3 · answered Dec 12 '12 at 03:34

0

Consider:

occurrences(_, [], []) :- !.
occurrences(X, [Y|L], R) :-
    X \== Y, !,
    occurrences(X, L, R).
occurrences(X, [Y|L], [Y|R]) :-
    occurrences(X, L, R).

Testing:

?- occurrences(a,[a,b,a,c],O).
O = [a, a].

?- occurrences(a,[a,X,a,c],O).
O = [a, a].

?- occurrences(a,[a,X,a,c],[a]).
false.

?- occurrences(a,[a,X,a,c],[a,a]).
true.

answered Dec 12 '12 at 03:34

Your definition lacks a mode declaration or whatever to state when it works and when it does not. E.g. for `occurences(E,Xs,Ys)` your definition is incomplete. – false Dec 12 '12 at 11:17
Wow, I wasn't aware OP required one! – Dec 12 '12 at 22:21
1

How else does one know when your definition is reliable and when not? – false Dec 12 '12 at 22:23

Program to find every list of X in Prolog

3 Answers3

Linked