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

New version, now even more deterministic:

delete_mid(List, MiddleDeleted) :-
    List = [_ | Tail],
    gallop(Tail, MiddleDeleted, List, MiddleDeleted).

gallop([], [], [_Middle | Xs], Xs).
gallop([_,_ | Fast1], [_,_ | Fast2], [X | Xs], [X | Ys]) :-
    gallop(Fast1, Fast2, Xs, Ys).

What's new versus previous answers is that this runs down both lists at double speed, while also copying the prefix at the same time. It needs shallow indexing on at least the first two arguments to be deterministic, but SWI-Prolog does that:

?- delete_mid([1, 2, 3, 4, 5], MiddleDeleted).
MiddleDeleted = [1, 2, 4, 5].

?- delete_mid(Xs, []).
Xs = [_2008].

?- delete_mid(Xs, [a, b]).
Xs = [a, _2034, b].

?- dif(A, B), delete_mid([A | _], [B | _]).
false.

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.

Answer 3

Here is my prolog solution:

delMidNumber(K,L):-
     len(K,N),
     (N mod 2 =:= 1 ->  
      N1 is N//2,
      nth0(N1,K,E1),
      del(E1,K,L); write('List has even length'),!).

len([],0).
len([H|T],N):-
    len(T,N1),
    N is N1+1.

del(E,[E|T],T).
del(E,[H|T],[H|T1]):-
    del(E,T,T1).

The predicate delMidNumber takes two arguments 1-The List with odd numbers. 2- The New List that will be formed. The predicate first calculates the length of the list, it then checks if the length of the list is odd then it divides the length by 2. The result is then used in nth0 to give us the element on that index. We then simply use the the del predicate to delete that mid number element. If the length is even it writes the message that the length is even and then cuts (stops).

?-delMidNumber([1,3,2,4,5],L).
L = [1, 3, 4, 5]

?-delMidNumber([1,3,4,5],L).
List has even length

Answer 4

Making use of append/3:

del_mid([_], []).         % if input only has one element => output is []
del_mid([H|T], [H|X]) :- 
  append(M, [Litem], T),  % M = list without first and last (Litem) element
  del_mid(M, R),          % Apply on M; if M is only one item => R will be []
  append(R, [Litem], X).  % X = R + [last item] => which gets added as result's tail

Some examples:

?- del_mid([], X).
false.

?- del_mid([a], X).
X = [] ;
false.

?- del_mid([a,b], X).
false.

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

?- del_mid([a,b,c,d,e,f,g], X).
X = [a, b, c, e, f, g] ;
false.

Answer 5

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 6

I think you need the nth0/4 predicate. Just find the index of the middle element and then remove it using nth0/4.

delete_middle(Ls, Ls1) :-
    length(Ls, L),
    divmod(L, 2, Q, 1),   % constrain remainder to be 1: fails on even list
    nth0(Q, Ls, _, Ls1).

Generative Variant: The only problem was with divmod.

divmod1(Dividend, Divisor, Quotient, Remainder) :-
    (   var(Dividend)
    ->  Dividend is Divisor*Quotient+Remainder
    ;   divmod(Dividend, Divisor, Quotient, Remainder)
    ).

delete_middle(Ls, Ls1) :- % Reversed the clauses.
    nth0(Q, Ls, _, Ls1),
    divmod1(L, 2, Q, 1),
    length(Ls, L).

?- dif(A, B), delete_middle([A|_], [B|_]).
false.

?- delete_middle(X, []).
X = [_382] ;
false.

Answer 7

This solution keeps a counter to unify the tail with a proper length list after "taking out" the middle item:

without_middle(Ls, Ls1):-
  without_middle(Ls, 0, Ls1).
  
without_middle([_Mid|Tail], Len, Tail):-
  length(Tail, Len).
without_middle([Item|Tail], Len, [Item|NTail]):-
  succ(Len, Len1),
  without_middle(Tail, Len1, NTail).

---

This slight variation embeds the counting+length+unification of the second half more directly, yielding a better performance results for large lists:

without_middle(Ls, Ls1):-
  without_middle(Ls, [], Ls1).

without_middle([_Mid|Tail], Tail, Tail).
without_middle([Item|Tail], RTail, [Item|NTail]):-
   without_middle(Tail, [_|RTail], NTail).

Sample test cases:

?- without_middle([a,b,c,d,e,f,g], L).
L = [a, b, c, e, f, g] ;
false.

?- without_middle([a,b,c,d,e,f], L).
false.

?- without_middle(L, []).
L = [_552] ;
false.

?- dif(A,B), without_middle([A|_], [B|_]).
false.

Answer 8

Building upon the find the middle algorithm presented by TA_intern :

%! list_without_middle(SOURCEs,TARGETs)

list_without_middle(SOURCEs,TARGETs)
:-
list_middle(SOURCEs,_MIDDLE_,PREFIXs,SUFFIXs) ,
lists:append(PREFIXs,SUFFIXs,TARGETs)
.

%!  list_middle(LISTs,MIDDLE,PREFIXs,SUFFIXs)

list_middle([ITEM|LISTs],MIDDLE,PREFIXs,SUFFIXs)
:-
list_middle(LISTs,LISTs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.

%!  list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)

list_middle([],SLOWs,ITEM,ITEM,[],SLOWs) .

list_middle([_,_|FASTs],[ITEM|SLOWs],PREVIOUS_ITEM,MIDDLE,[PREVIOUS_ITEM|PREFIXs],SUFFIXs)
:-
list_middle(FASTs,SLOWs,ITEM,MIDDLE,PREFIXs,SUFFIXs)
.

?- list_without_middle([a,b,c],Ys).
Ys = [a, c].

?- list_without_middle([a,c],Ys).
false.

?- list_without_middle([a,b,c,d,e],Ys).
Ys = [a, b, d, e].

?- 

?- list_without_middle(Xs,Ys) .
Xs = [_924],
Ys = [] ;
Xs = [_924, _930, _936],
Ys = [_924, _936] ;
Xs = [_924, _930, _936, _948, _954],
Ys = [_924, _930, _948, _954] %.e.t.c.

?- list_middle([a,b,c],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = b,
PREFIXs = [a],
SUFFIXs = [c].

?- list_middle([a,c],MIDDLE,PREFIXs,SUFFIXs).
false.

?- list_middle([a,b,c,d,e],MIDDLE,PREFIXs,SUFFIXs).
MIDDLE = c,
PREFIXs = [a, b],
SUFFIXs = [d, e].

?- 

?- list_without_middle(Ls,[]) .
Ls = [_4364] ;
ERROR: Out of global stack
?- list_without_middle([a],Ys).
Ys = [].

?- dif(A,B) , list_without_middle([A|_],[B|_]) .
ERROR: Out of global stack
?- 

Answer 9

delete_middle([], [], _MiddleDeletedPrefix) -->
    [_Middle].
delete_middle([L | Left], [R | ReversedRight], [L | MiddleDeletedPrefix]) -->
    [L],
    delete_middle(Left, ReversedRight, MiddleDeletedPrefix),
    [R].

delete_middle(List, MiddleDeleted) :-
    phrase(delete_middle(Left, ReversedRight, MiddleDeleted), List),
    reverse(ReversedRight, Right),
    append(Left, Right, MiddleDeleted).

 

?- delete_middle([1, 2, 3, 4, 5], Xs).
Xs = [1, 2, 4, 5] ;
false.

?- delete_middle(Ls, []).
Ls = [_2542] ;
false.

?- dif(A,B), delete_middle([A|_],[B|_]).
false.

?- delete_middle(List, MiddleDeleted).
List = [_2368],
MiddleDeleted = [] ;
List = [_2368, _2392, _2374],
MiddleDeleted = [_2368, _2374] ;
List = [_2368, _2392, _2416, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2422, _2398, _2374] ;
List = [_2368, _2392, _2416, _2440, _2464, _2446, _2422, _2398, _2374],
MiddleDeleted = [_2368, _2392, _2416, _2440, _2446, _2422, _2398, _2374] .  % etc.

Answer 10

Not a straight forward nor a more optimal answer.

delete_middle1(Ls, Ls1) :- delete_middle1_(Ls, Ls, [], Ls1).
delete_middle1_([X | Cs], [_, _ | Ds], Acc, L) :-
    delete_middle1_(Cs, Ds, [X | Acc], L).
delete_middle1_([_ | Cs], [_], Acc, L) :-  revappend(Acc, Cs, L).

revappend([], L, L).
revappend([X | L1], L2, L3) :- revappend(L1, [X | L2], L3).

This method works well when dealing with linked-lists and pointers. When one pointer is at the end, the other will be near the middle. Then we can just delete the element.

Answer 11

The solution with nth0/4 is efficient but how about we solve this declaratively?

middle_less(InList,MiddlelessList,Middle) :-
   append([Prefix,[Middle],Suffix],InList),
   length(Prefix,Len),
   length(Suffix,Len),
   append(Prefix,Suffix,MiddlelessList).

Which is basically the problem statement in Prolog form.

It also works:

:- begin_tests(middleless).

test("empty list",fail) :- middle_less([],_,_).

test("1-element list",[true([MLL,M] == [[],a]),nondet]) :-
   middle_less([a],MLL,M).

test("2-element list",fail) :- 
   middle_less([a,b],_,_).

test("3-element list",[true([MLL,M] == [[a,c],b]),nondet]) :-
   middle_less([a,b,c],MLL,M).

:- end_tests(middleless).

And so:

?- run_tests.
% PL-Unit: middleless .... done
% All 4 tests passed
true.

But with a list of 1001 elements:

?- length(L,1001),time(middle_less(L,MLL,M)).
% 757,517 inferences, 0.110 CPU in 0.111 seconds (99% CPU, 6862844 Lips)

One day, the compiler with morph the spec of middle_less automagically into an efficent solution.