12

I recently began programming in Prolog and am currently trying to create rules that find the element after a given element in a list. For example, I want find(2,X,[1,2,3,4]). to result in 3.

My attempt so far:

find(X,Y,[X,Y|Tail]):-
   !.
find(X,Y,[_|Tail]):-
   find(X,Y,Tail).
false
  • 10,264
  • 13
  • 101
  • 209
Hunterhod
  • 185
  • 1
  • 2
  • 11
  • 3
    Your code worked fine when I tried it. What's not working for you? – Enigmativity Sep 23 '11 at 06:45
  • 1
    Clarification 1: By deterministic I mean that no unnecessary choice point is left open. There are, indeed, still situations which require choice points like `find(X,Y,X)`. There should really be a notion for this. – false May 05 '15 at 13:50

3 Answers3

6

Let's use if_/3 and (=)/3 (a.k.a. equal_truth/3), as defined by @false in this answer!

So here comes the new, logically pure find/3:

find(E0,E1,[X|Xs]) :-
   member_next_prev_list(E0,E1,X,Xs).

member_next_prev_list(E0,E1,X0,[X1|Xs]) :-
   if_(X0=E0, X1=E1, member_next_prev_list(E0,E1,X1,Xs)).

Let's run the queries mentioned by the OP / by other answers / by some comments:

?- find(a,X,[a,a,b]).
X = a.                      % succeeds deterministically
?- find(a,X,[a,Y,b]).
X = Y.                      % succeeds deterministically
?- find(a,b,[a,a,b]).
false.                      % fails

?- find(a,X,[a,a,b,c]).
X = a.                      % succeeds deterministically
?- find(b,X,[a,a,b,c]).
X = c.                      % succeeds deterministically

Now to something a little more general:

?- find(X,Y,[a,a,b,c]).
X = a, Y = a ;
X = b, Y = c ;
false.

What about the most general query? As the code is pure, we get logically sound answers:

?- find(X,Y,List).
List = [            X,Y|_Z] ;
List = [_A,         X,Y|_Z], dif(_A,X) ;
List = [_A,_B,      X,Y|_Z], dif(_A,X), dif(_B,X) ;
List = [_A,_B,_C,   X,Y|_Z], dif(_A,X), dif(_B,X), dif(_C,X) ;
List = [_A,_B,_C,_D,X,Y|_Z], dif(_A,X), dif(_B,X), dif(_C,X), dif(_D,X) ...

Edit 2015-05-06

Here's a more concise variant, unimaginatively called findB/3:

findB(E0,E1,[X0,X1|Xs]) :-
   if_(X0=E0, X1=E1, findB(E0,E1,[X1|Xs])).

Like find/3, findB/3 is efficient in the sense of not leaving useless choicepoints behind, but it has higher memory use.

findC/3 tries to reduce the memory use by hoisting the common expression [X1|Xs]:

findC(E0,E1,[X0|XXs]) :-
   XXs = [X1|_],
   if_(X0=E0, X1=E1, findC(E0,E1,XXs)).
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
2

Here's a version w/o the cut:

find(X,Y,[X,Y|_]).
find(X,Y,[Z|Tail]) :- 
    X\=Z, find(X,Y,Tail).
Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
  • 1
    Counterexample: `find(a,b,[a,a,b])` should succeed, but your definition fails. – false May 05 '15 at 12:37
  • 1
    Correction: this counterexample is not OK. In the sense of the original question, it really should fail here ... – false May 05 '15 at 13:43
1

Here is a pure version:

find(X,Y, [X,Y|_]).
find(X,Y, [X0,Y0|Xs]) :-
   dif(X+X0,Y+Y0),
   find(X,Y, [Y0|Xs]).

I'd rather would like to have a deterministic version, and also a pure DCG version would be cool!

false
  • 10,264
  • 13
  • 101
  • 209