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.

[Related](http://stackoverflow.com/q/23516616/772868). – false Mar 01 '16 at 15:37 — false, Mar 01 '16 at 15:37

lurker · Accepted Answer · 2016-03-01T13:20:08.390

13

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
| ?-

edited Mar 01 '16 at 13:20

answered Feb 27 '16 at 13:22

lurker

56,987
9
69
103

1

The variant with [tag:prolog-cut] is incomplete / unsound when used with certain modes. This pushes **a lot** of responsibility to the potential user! – repeat Feb 27 '16 at 14:22
2

@repeat 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. – lurker Feb 27 '16 at 14:25
1

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! – false Mar 01 '16 at 12:57
1

@false "cleaner" may not have been an apt adjective. I should probably have said "more concise" (edited). – lurker Mar 01 '16 at 13:19
1

@lurker: Please note the bounty to produce an even better version (preferably in a new answer). – false Mar 01 '16 at 15:08

score 7 · Answer 2 · answered Feb 27 '16 at 07:51

7

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.

answered Feb 27 '16 at 07:51

Christian Hujer

17,035
5
40
47

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? – quantumferret Feb 27 '16 at 07:54
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. – quantumferret Feb 27 '16 at 07:56
3

Nevertheless, @quantumferret 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. – false Mar 01 '16 at 13:04

repeat · Answer 3 · 2016-02-27T08:30:31.783

6

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.

edited Feb 27 '16 at 08:30

answered Feb 27 '16 at 08:23

repeat

18,496
4
54
166

1

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? – quantumferret Feb 27 '16 at 08:36
1

@quantumferret The goal `append(_, [E0,E1|_], Es)` is read like this: "The list `Es` has a suffix that starts with `E0` followed by `E1`." – repeat Feb 27 '16 at 09:02
1

@quantumferret Note that the "base case" you suggested is too specific. It should probably be like `adjacent(X, Y, [X,Y|_])`. – repeat Feb 27 '16 at 09:04
1

Ahh ok. Thank you, you've been tremendously helpful! – quantumferret Feb 27 '16 at 09:26

score 6 · Answer 4 · edited May 23 '17 at 10:34

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.

The new definition now is (in the long term) very inefficient: It inherently requires the creation of these two auxiliary structures `f/2`. — false, Mar 31 '16 at 13:56

false · Answer 5 · 2016-04-22T15:18:22.560

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)).

Prolog - Finding adjacent elements in a list

5 Answers5

Edit

Linked