Prolog - infinite loop

Question

I want to check if element is in the middle of list. I search middle element and next I check if is a member of list, but I get infinite loop.

My predicates:

remove_first([_,H1|T], [H1|T]).

remove_last([_],[]).
remove_last([H|T], [H|T2]) :- remove_last(T, T2).

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- 
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]).
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X).

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

is_middle(X, In) :-
    middle(In, Out),
    member(X, Out), !.

And when I call is_middle(1,[2,1,3]) then I get true. But when I call is_middle(1,[2,2,3]) then I don't get a result. Interpreter don't interrupt the processing.

Answer 1

In a situation as yours, you have two options. Either wade through walls of text of traces as you can see in another answer, or try to reduce first what you have to understand. I prefer the latter for I don't like to read much.

But your major problem is this. You said:

And when I call is_middle(1,[2,1,3]) then I get true.

Yes, Prolog found a solution, but it did not find it once but infinitely many times. Just hit SPACE or ; to see this:

?- is_middle(1,[2,1,3]).
true ;
true ;
true ;
true ;
true ;
true ...

So, already your first query was problematic. The best way to observe this, is to add false to this query:

?- is_middle(1,[2,1,3]), false.
** LOOPS **

Now, let's try to reduce the size of the query. We can narrow it down to:

?- is_middle(1,[1]), false.
** LOOPS **

With this we can now look at your program. Before anything else I'll remove the cut. It is misplaced anyway.

To understand what is actually happening, I will narrow down your program by inserting false into it. With these extra goals it is possible to eliminate a lot of unnecessary detail. And still, the remaining program called a failure-slice is of relevance to us, if it is still looping.

remove_first_and_last([X],[X]).
remove_first_and_last(In, Out) :- false,
    remove_first(In, Out1),
    remove_last(Out1, Out).

middle([X], [X]) :- false.
middle(In, X) :-
    remove_first_and_last(In, Out),
    middle(Out, X), false.

is_middle(X, In) :-
    middle(In, Out), false,
    member(X, Out).

Compare this to your original program! Much less reading. To fix the problem you have to fix something in the remaining fragment. I suggest to remove the fact remove_first_and_last([X],[X]). This fact suggests that something is removed, but for this very case, nothing is removed.

---

For a solution using a dcg directly:

is_middle(E, Es) :-
   phrase(middle(E), Es).

middle(E) --> [E].
middle(E) --> [_], middle(E), [_].

That is as short as it can get, but it has a tiny problem: It does not compute the answer determinately. You can see this by looking at the answer:

?- is_middle(1, [2,1,3]).
true ;
false.

This ; false is an indication that Prolog was not able to finish the computation determinately. In other words, some space is left. You might be tempted to use a cut. Resist!

---

If you are really into speed, take the fastest version:

is_middle(X, Xs) :-
   Xs = [_|Cs],
   middle_el(Cs, Xs, X).

middle_el([], [X|_], X).
middle_el([_,_|Cs], [_|Xs], X) :-
   middle_el(Cs, Xs, X).

---

In case you want @DanielLyons' interpretation which admits even-length lists to have two middle elements, see how easy it is to adopt above grammar definition. Simply add the following two rules:

middle(E) --> [E,_].
middle(E) --> [_,E].

Alternatively, combine all four rules into one:

middle(E) --> [E] | [E,_] | [_,E] | [_], middle(E), [_].

For the fastest solution, things are a bit more complex ...

is_middle_dl(X, Xs) :-
   Xs = [_|Cs],
   middle_el_dl(Cs, Xs, X).

middle_el_dl([], [X|_], X).
middle_el_dl([_|Cs], Xs, X) :-
   middle_el_dl2(Cs, Xs, X).

middle_el_dl2([], [A,B|_], X) :-
   ( X = A ; X = B ).
middle_el_dl2([_|Cs], [_|Xs], X) :-
   middle_el_dl(Cs, Xs, X).

To check it, I use SICStus since it gives more readable names to variables:

| ?- length(Xs, N), N mod 2 =:= 0, is_middle_dl(X, Xs).
Xs = [X,_A],
N = 2 ? ;
Xs = [_A,X],
N = 2 ? ;
Xs = [_A,X,_B,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C],
N = 4 ? ;
Xs = [_A,_B,X,_C,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E],
N = 6 ? ;
Xs = [_A,_B,_C,X,_D,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G],
N = 8 ? ;
Xs = [_A,_B,_C,_D,X,_E,_F,_G,_H,_I],
N = 10 ? ;
Xs = [_A,_B,_C,_D,_E,X,_F,_G,_H,_I],
N = 10 ? ...