Prolog, X before Y in a List

Question

I am having trouble understanding prolog, I have to find if X is before Y in a list.

so I have a base case with an empty list

before(X, Y, [ ]).

Now I know that I want to check the index of X and the index of Y in List and if indexX < indexY I want to have a success.

Could someone explain a simple way to do this?

Answer 1

You can use append/3 to locate X and the remaining list after it, then locate Y.

before(X, Y, L):-
  append(_, [X|Tail], L),
  append(_, [Y|_], Tail).

Answer 2

Using a DCG, it would look like this (using a predicate named ... for notational/visual convenience):

before(X, Y) --> ..., [X], ..., [Y], ... .
... --> [].
... --> [_], ... .

| ?- phrase(before(X, Y), [a,b,c]).

X = a
Y = b ? ;

X = a
Y = c ? ;

X = b
Y = c ? ;

(1 ms) no

And you can wrap it in a predicate, if you wish:

before(X, Y, L) :- phrase(before(X, Y), L).

---

at least one caseXYX is seen before Y in the list

before(X, Y) --> anything_but(Y), [X], ..., [Y], ... .

anything_but(_) --> [].
anything_but(Y) --> [X], { dif(X, Y) }, anything_but(Y).

... --> [].
... --> [_], ... .

Which results in:

| ?-  phrase(before(X,Y), [b,a,b]).

X = b
Y = b ? a

X = a
Y = b

no

Answer 3

In Prolog, list processing is in most cases done without using indices: you use recursion, and you try to formulate it as a logical expression. If you don't want to use built-ins, you can write:

before(X,Y,[X|T]) :-
    !,
    contains(Y,T).
before(X,Y,[_|T]) :-
    before(X,Y,T).

contains(Y,[Y|_]) :-
    !.
contains(Y,[_|T]) :-
    contains(Y,T).

The code makes use of a defined contains/2 predicate that checks whether the list L contains Y. Now the before/2 predicate contains two clauses. The first clause specifies that the first element of the list is X, in that case, we only need to check whether the remainder of the list contains an Y. In case the first element of the list is not an X, the list is shifted one further, and by using recursion, we try to find a location where there is an X.

Note that this predicate requires that both X and Y are elements of the list. Furthermore there can be multiple X and Ys. So before(a,b,[b,a,a,b]) will succeed, simple because there is an a and a b such that the a is before the b.

EDIT

If you want to use the predicate in a reversed way (query fashion), you should omit the cuts:

before(X,Y,[X|T]) :-
    contains(Y,T).
before(X,Y,[_|T]) :-
    before(X,Y,T).

contains(Y,[Y|_]).
contains(Y,[_|T]) :-
    contains(Y,T).

Then you can query like:

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

Answer 4

Here's a simple solution that uses no built-in predicates whatsoever.

It helps if you re-cast the problem in somewhat more generic terms.

A common prolog idiom is a public predicate that invokes a worker predicate that does all the work. Often, the worker predicate will carry additional variable that maintain state. In this case, we don't need to maintain state, but it simplifies things if we make the actual solution more generic: instead of defining the problem in terms of X and Y, redefineit in terms of a list of arbitrary length, defining the order in which things must be found in the target list.

Then, it's simply a matter of recursing down both lists in parallel to determine if the precedence constraints are satisfied. The generic solution (which will work for a list containing an arbitrary number of constraints) has 3 cases:

• The constraint list is empty: Success!
• The head of the constraint list unifies with the head of the list being tested. That indicates that a constraint has been satisfied. Remove both the constraint and the item it just matched (the head of the list being tested) and recurse down.
• Finally, just remove the head of the list being tested and recurse down.

The solution looks like this:

x_before_y( X , Y, Zs ) :- satisfies_constraints( [X,Y] , Zs ) .

satisfies_constraints( []     , _      ) .
satisfies_constraints( [C|Cs] , [C|Xs] ) :- satisfies_constraints(Cs,Xs) .
satisfies_constraints( Cs     , [_|Xs] ) :- satisfies_constraints(Cs,Xs) .

On backtracking, this will find all possible solutions. If that's not desirable, a cut in the 2nd clause will eliminate the choice points:

satisfies_constraints( []     , _      ) .
satisfies_constraints( [C|Cs] , [C|Xs] ) :- !, satisfies_constraints(Cs,Xs) .
satisfies_constraints( Cs     , [_|Xs] ) :-    satisfies_constraints(Cs,Xs) .

As will introducing a test for non-unifiability in the 3rd clause:

satisfies_constraints( []     , _      ) .
satisfies_constraints( [C|Cs] , [C|Xs] ) :- satisfies_constraints(Cs,Xs) .
satisfies_constraints( [C|Cs] , [X|Xs] ) :-
  C \= X ,
  satisfies_constraints([C|Cs],Xs)
  .