Deleting the middle element of a list

Question

I want to write a Prolog program to delete the middle element from an odd-numbered list into another list.

For example, If we give : delete_mid([1,2,3,4,5],L) then it will produce : L = [1,2,4,5] as answer.

Answer 1

I am surprised and a bit saddened that neither answer so far takes the most obvious approach; surely you've heard about it in school (and I suspect it might be what OP is expected to do).

It is however a bit difficult to explain or do at once, so first, here is a predicate to find the middle element:

list_mid([H|T], Mid) :-     list_mid_1(T, T, H, Mid).  list_mid_1([], _, Mid, Mid). list_mid_1([_,_|Fast], [S|Slow], _, Mid) :-     list_mid_1(Fast, Slow, S, Mid). 

I hope the names are obvious.

?- list_mid([], Mid). false.  ?- list_mid([x], Mid). Mid = x.  ?- list_mid([a,x,b], Mid). Mid = x.  ?- list_mid([a,a,x,b,b], Mid). Mid = x.  ?- list_mid([a,a,x,b], Mid). false. 

Seems to work. Now, I can try and add the part where it keeps what it throws away at the moment.

---

I was busy so this took a while. In the meantime, the answer by Raubsauger is exactly what I had in mind. I did not see it and instead wrote this:

delete_mid([H|T], L) :-     delete_mid_1(T, T, H, L).  delete_mid_1([], Rest, _, Rest). delete_mid_1([_,_|Fast], [H|Slow], Prev, [Prev|Back]) :-     delete_mid_1(Fast, Slow, H, Back). 

It is not as neat as the solution by Raubsauger but it seems it is otherwise the same solution. It terminates for the test cases by @false.

---

I thought the list_middle/2 predicate was enough; I am again surprised and a bit saddened that only Raubsauger saw it (or already knew that about it).

---

Und täglich grüßt das Murmeltier

Answer 2

And now I want to join too (answer no. 8 to this question).

delete_mid(Ori, Del):-     delete_mid(Ori, Ori, Del).  delete_mid([_], [_|Slow], Slow). delete_mid([_,_|Fast], [H|Slow], [H|Ret]):-         delete_mid(Fast, Slow, Ret).  ?- delete_mid([1, 2, 3, 4, 5], Del). Del = [1, 2, 4, 5] ; false.  ?- delete_mid([1, 2, 3, 4], Del). false.  ?- delete_mid(L, []). L = [_1500] ; false.  ?- dif(A,B), delete_mid([A|_], [B|_]). false. 

---

To the idea: I saw TA_interns answer about getting the middle element (list_mid) and thought:
This is genius. But wait ... this can be improved.

---

To explain the algorithm a bit further: the predicate can be used to generate a list which is similar to the (odd numbered) input list without middle element. Or it can test for two lists if this property holds.

The "genius" part is that there is no need to calculate the length or have counters because it actually uses a copy of the input list as counter. The principle is explained here and here.

Lines 1 & 2 create two references to the same list. The counter list is called fast, the element list is called slow. Why? Because in each recursion step you strip two elements from the fast list ([_,_|Fast]) but only one from the element list ([H|Slow]). When there is exactly one element in the fast list left ([_]) you hit the middle element from the slow list. So remove it and put the rest on the return track. While going forwards with the recursion put all the elements (H) which you removed from the slow list as head of the return list, and the recursion fills in the rest.

Et voilà you got an exact copy of the element list, just the middle element is missing.