Finding the k'th occurence of a given element

Question

I just started in Prolog and have the problem:

(a) Given a list L, an object X, and a positive integer K, it returns the position of the K-th occurrence of X in L if X appears at least K times in L otherwise 0.

The goal pos([a,b,c,b],b,2,Z) should succeed with the answer Z = 4.

So far I have:

pos1([],H,K,F).
pos1([H],H,1,F).
pos1([H|T],H,K,F):- NewK is K - 1, pos1(T,H,NewK,F), F is F + 1.
pos1([H|T],X,K,F):- pos1(T,X,K,F).

But I can't figure out why I'm getting:

ERROR: is/2: Arguments are not sufficiently instantiated

Any help would be much appreciated!

What command are you using to load "straight from the file"? — lurker, Nov 18 '13 at 23:18
So this is Windows? When I load your code into SWI Prolog I don't get that error at all. I get `ERROR: is/2: Arguments are not sufficiently instantiated`. Are you sure it's really consulting your file when you click on it? — lurker, Nov 18 '13 at 23:21
You get the right error because you have `F is F + 1` and `F` is never instantiated. Anything on the right hand side of an `is` must be fully instantiated. In addition, you cannot re-assign a value to a variable in prolog once it's bound. — lurker, Nov 18 '13 at 23:25
by maintaining another argument to a predicate, and unifying it with the final value of `F`. Like is done for `L2` in my answer. — Will Ness, Nov 19 '13 at 00:04

score 1 · Answer 1 · edited May 23 '17 at 11:44

1

Use clpfd!

:- use_module(library(clpfd)).

We define pos/4 based on (#>)/2, (#=)/2, if_/3, dif/3, and (#<)/3:

pos(Xs,E,K,P) :-
   K #> 0,
   pos_aux(Xs,E,K,1,P).

pos_aux([X|Xs],E,K,P0,P) :-
   P0+1 #= P1,
   if_(dif(X,E),
       pos_aux(Xs,E,K,P1,P),
       if_(K #< 2,
           P0 = P,
           (K0+1 #= K,
            pos_aux(Xs,E,K0,P1,P)))).

Sample query as given by the OP:

?- X = b, N = 2, pos([a,b,c,b],X,N,P).
X = b, N = 2, P = 4.                     % succeeds deterministically

How about the following more general query?

?- pos([a,b,c,b],X,N,P).
  X = a, N = 1, P = 1
; X = b, N = 1, P = 2
; X = b, N = 2, P = 4                    % (exactly like in above query)
; X = c, N = 1, P = 3
; false.

edited May 23 '17 at 11:44

Community

1
1

answered Aug 19 '15 at 11:31

repeat

18,496
4
54
166

check out corner case. does `P=0` even make sense in "not found often enough" cases? – repeat Aug 19 '15 at 12:20
nice! (p.s.: one last `is/2` unintentionally remained in `pos_aux/5`!) – mat Aug 19 '15 at 17:36
@mat. Actually I'm somewhat on the fence regarding the corner case... Does it even make a lot of sense? What's your take on this? – repeat Aug 19 '15 at 18:27
1

For didactic reasons alone, I would always favour the more declarative predicate when in doubt. I would also always suggest using `dif/2` instead of `(\==)/2` etc., even in cases where the result is the same: This is simply to advertise the more general solutions. – mat Aug 19 '15 at 19:04
@mat. Thx! It's for the Greater Good! – repeat Aug 19 '15 at 19:46

Will Ness · Answer 2 · 2013-11-19T00:05:39.717

Let's take a high-level approach to it, trading the efficiency of the resulting code for the ease of development:

pos(L,X,K,P):-
   numerate(L,X,LN,1),  %// [A1,A2,A3...] -> [A1-1,A2-2,A3-3...], where Ai = X.
   ( drop1(K,LN,[X-P|_]) -> true ; P=0 ).

Now we just implement the two new predicates. drop1(K,L,L2) drops K-1 elements from L, so we're left with L2:

drop1(K,L2,L2):- K<2, !.
drop1(K,[_|T],L2):- K1 is K-1, drop1(K1,T,L2).

numerate(L,X,LN,I) adds an I-based index to each element of L, but keeps only Xs:

numerate([],_,[],_).
numerate([A|B],X,R,I):- I1 is I+1, ( A=X -> R=[A-I|C] ; R=C ), numerate(B,X,C,I1).

Testing:

5 ?- numerate([1,b,2,b],b,R,1).
R = [b-2, b-4].

6 ?- pos([1,b,2,b],b,2,P).
P = 4.

7 ?- pos([1,b,2,b],b,3,P).
P = 0.

score 0 · Answer 3 · answered Nov 19 '13 at 07:12

I've corrected your code, without changing the logic, that seems already simple enough. Just added a 'top level' handler, passing to actual worker pos1/4 and testing if worked, else returning 0 - a debatable way in Prolog, imo is better to allow to fail, I hope you will appreciate how adopting this (see comments) simplified your code...

pos(L,X,K,F):- pos1(L,X,K,F) -> true ; F=0.

% pos1([],H,K,F). useless: let it fail
% pos1([H],H,1,F). useless: already handled immediatly bottom
pos1([H|T],H,K,P):- K==1 -> P=1 ; NewK is K - 1, pos1(T,H,NewK,F), P is F + 1.
pos1([_|T],X,K,P):- pos1(T,X,K,F),P is F+1.

I hope you're allowed to use the if/then/else construct. Anyway, yields

7 ?- pos([a,b,c,b],b,2,Z).
Z = 4.

8 ?- pos([a,b,c,b],b,3,Z).
Z = 0.

score 0 · Answer 4 · answered Nov 19 '13 at 22:16

Something like this. An outer predicate (this one enforces the specified constraints) that invokes an inner worker predicate:

kth( L , X , K , P ) :-
  is_list( L ) ,            % constraint: L must be a list
  nonvar(X) ,               % constriant: X must be an object
  integer(K) , K > 0        % constraint: K must be a positive integer
  kth( Ls , X , K , 1 , P ) % invoke the worker predicate with its accumulator seeded to 1
  .                         % easy!

is_list/2 ensures you've got a list:

is_list(X) :- var(X) , !, fail .
is_list([]).
is_list([_|_]).

The predicate that does all the work is this one:

kth( []     , _ , _ , _ , 0 ) .      % if we hit the end of the list, P is 0.
kth( [X|Ls] , X , K , K , K ) :- ! . % if we find the Kth desired element, succeed (and cut: we won't find another Kth element)
kth( [_|Ls] , X , K , N , P ) :-     % otherwise
  N < K ,                            % - if we haven't got to K yet ...
  N1 is N+1 ,                        % - increment our accumulator , and
  kth(Ls,X,K,N1,P)                   % - recurse down.
  .                                  % easy!

Though the notion of returning 0 instead of failure is Not the Prolog Way, if you ask me.

Finding the k'th occurence of a given element

4 Answers4