Prolog - Finding adjacent elements in a list

Question

I'm trying to define a predicate adjacent(X, Y, Zs) that is true if X and Y are adjacent in a list. My code is currently this:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
  adjacent(X,Y, Tail).

It works for the basic case of adjacent(c, d, [a, b, c, d, e]), but due to the base case, every other case returns true as well, and I'm stuck on that.

The other problem is that if X is not equal to the first part of the list's head, then it skips past both X and Y and goes to the next 'X'; e.g., if c isn't equal to a, then it skips past both a and b and checks if c is equal to c. This is problematic when, for example, the list is

[a, c, d, e]

because it ends up never checking c (I believe).

I'm pretty lost on how to reconcile the two issues and turn my logical understanding of what needs to occur into code.

EDIT: Thanks to Christian Hujer's answer, my base case mistake has been corrected, so now I'm just stuck on the second issue.

Levileviable

Related. – Persse

Answer 1

In the original solution attempt:

adjacent(_, _, []).
adjacent(X, Y, [X, Y|Tail]) :-
    adjacent(X,Y, Tail).

As @ChristianHujer points out, the first clause should not be there because it isn't true. The empty list should have no adjacent elements.

The second clause is also problematic. It shows that X and Y are adjacent in the list, but then recurses and doesn't just succeed. A proper clause should be:

adjacent(X, Y, [X,Y|_]).

Which says that X and Y are adjacent in the list if they're the first two elements in the list, regardless of what the tail is. This also forms a proper base case. Then your general, recursive clause should take care of the rest of the cases:

adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

This says that X and Y are adjacent in [_|Tail] if they're adjacent in Tail. This takes care of the second problem you were encountering.

Thus, the whole solution would be:

adjacent(X, Y, [X,Y|_]).
adjacent(X, Y, [_|Tail]) :-
    adjacent(X, Y, Tail).

This will succeed as many times as X and Y appear together, in that order, in the list.

---

This is also naturally solvable with a DCG (although @repeat's append/3 based solution is more concise):

adjacent(X, Y) --> ..., [X, Y], ... .
... --> [] | [_], ... .

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

---

| ?- adjacent(b, c, [a,b,c,d]).

true ? a

(1 ms) no
| ?- 

Madagascar

The variant with prolog-cut is incomplete / unsound when used with certain modes. This pushes a lot of responsibility to the potential user! – Cesar

@Cesar yes, thanks for pointing that out about the cut. I just removed that case since it was a little outside the scope of what the OP was asking for. – Madagascar

What makes you believe that repeat's solution is cleaner? It succeeds for adjacent(a,b,[a,b|non_list]) where we have clearly a non-list! – Persse

@Persse "cleaner" may not have been an apt adjective. I should probably have said "more concise" (edited). – Madagascar

@lurker: Please note the bounty to produce an even better version (preferably in a new answer). – Persse

Answer 2

I think your base case is wrong. In your situation, you want recursion to terminate with a false predicate, not with a true predicate. And it's logical: In an empty list, there are no adjacent elements. Never.

Asthmatic

Oh duh, so the base case for a true result would be if X and Y are the only two elements in the list, correct? – Levileviable

So the base case bit is fixed, now I'm just trying to figure out how to keep it from skipping past an element if the first isn't equal to X, which is something I'm a bit stumped about. – Levileviable

Nevertheless, @Levileviable had some point in using [] in his attempt: To ensure that the 3rd argument is a list, we somehow need []. Otherwise unexpected solutions like adjacent(a,b,[a,b|non_list]) are possible. – Persse

Answer 3

In this answer we try to keep it simple—by building on append/3:

adjacent(E0, E1, Es) :-
    append(_, [E0,E1|_], Es).

Sample query:

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

Cesar

This is awesome but I'm a little unclear on how to read the append statement, and also a little hesitant to use a built-in predicate, because this is for a homework assignment. Also, if I used something like this, I would still keep the base case of adjacent(X, Y, [X,Y]) right? – Levileviable

@Levileviable The goal append(_, [E0,E1|_], Es) is read like this: "The list Es has a suffix that starts with E0 followed by E1." – Cesar

@Levileviable Note that the "base case" you suggested is too specific. It should probably be like adjacent(X, Y, [X,Y|_]). – Cesar

Ahh ok. Thank you, you've been tremendously helpful! – Levileviable

Answer 4

The auxiliary predicate adjacent_/5 always "lags behind" by exactly two (list items):

adjacent(X0, X1, [E0,E1|Es]) :-
   adjacent_(Es, E0, E1, X0, X1).

adjacent_([],      E0, E1, E0, E1).
adjacent_([E2|Es], E0, E1, X0, X1) :-
   if_(E0+E1 = X0+X1,
       true,
       adjacent_(Es, E1, E2, X0, X1)).

Using SWI-Prolog we run:

?- set_prolog_flag(double_quotes, chars).
true.

?- adjacent(a, b, "abab").
true.

?- adjacent(b, c, "abcd").
true. 

?- adjacent(X, Y, "abcd").
   X = a, Y = b
;  X = b, Y = c
;  X = c, Y = d.

Edit

The corrected definition of adjacent_/5 gives right answers for the following queries, too:

?- adjacent(X, X, [A,B,C]).
   X = A, A = B
;  X = B, B = C, dif(f(C,C),f(A,A)).

?- adjacent(a, X, "aab").
   X = a
;  X = b.

?- adjacent(a, b, "aab").
true.

Cesar

adjacent(a,b,"aab"). fails – Persse

The new definition now is (in the long term) very inefficient: It inherently requires the creation of these two auxiliary structures f/2. – Persse

Answer 5

Here is a definition that I believe is in the long term preferable to @repeat's solution:

adjacent(X0, X1, [E0,E1|Es]) :-
   adjacent_(Es, E0, E1, X0, X1).

adjacent_([],      E0, E1, E0, E1).
adjacent_([E2|Es], E0, E1, X0, X1) :-
   if_(( E0 = X0, E1 = X1 ),
       true,
       adjacent_(Es, E1, E2, X0, X1)).

Using a reified and:

','(A_1, B_1, T) :-
   if_(A_1, call(B_1, T), T = false).

;(A_1, B_1, T) :-
   if_(A_1, T = true, call(B_1, T)).

Persse