Prolog Finding middle element in List

Question

I am trying to make use of prolog predicates and find middle element of a given list. My idea was to cut first and last element of list using recursion.Unfortunately I dont know how to handle recursion call properly.

delete_last(L, L1) :-  
 append(L1, [_], L).
delete_first(L,L1) :-
    append([_],L1,L).
check_len(L) :-
   length(L,LEN), \+ 1 is LEN.


delete_both([],_):-
    false.
delete_both([_,_],_) :-
    false.
delete_both([X],X):-
    true, write('MidElement').

delete_both(L,L2) :-
    delete_first(LT,L2), delete_last(L,LT),check_len(LT) 
    ->write('here should be recursive call only when length is more than one').

I would be grateful for any help.

Do you support lists of all sizes (even and odd)? If so, look at the related question "How to get the first, middle and last element of a list scheme and prolog?" (http://stackoverflow.com/questions/30112114/how-to-get-the-first-middle-and-last-element-of-a-list-scheme-and-prolog/30117040#30117040) and this answer in particular http://stackoverflow.com/a/30117040/4609915. HTH! — repeat, Mar 08 '16 at 23:08

score 3 · Answer 1 · 2016-03-08T19:20:45.767

It would save a lot of typing if you checked the length of the list, calculated the position of the middle element, and only then traversed the list to get the element at that position. With SWI-Prolog, this would be:

?- length(List, Len),
   divmod(Len, 2, N, 1),
   nth0(N, List, a).
List = [a],                                 Len = 1, N = 0 ;
List = [_G2371, a, _G2377],                 Len = 3, N = 1 ;
List = [_G2371, _G2374, a, _G2380, _G2383], Len = 5, N = 2 . % and so on

This solution makes sure the list has an odd length. You can see the documentation of divmod/4 if you need to define it yourself. Or, if the list does not have to have and odd, length, just use N is Len div 2. If for some reason you are not allowed to use nth0/3, it is still an easier predicate to implement than what you are trying to do.

lurker · Accepted Answer · 2016-03-08T11:43:33.670

You can tighten up what you have quite a bit as follows:

delete_last(L, L1) :-
    append(L1, [_], L).
delete_first([_|L], L).

% No need to check length of 1, since we only need to check
% if L = [X] in the caller, so we'll eliminate this predicate
%check_len(L) :-
%    length(L, 1).           % No need for an extra variable to check length is 1

% Clauses that yield false are not needed since clauses already fail if not true
% So you can just remove those
%
delete_both([X], X) :-
    write('MidElement').

% Here you need to fix the logic in your main clause
% You are deleting the first element of the list, then the last element
% from that result and checking if the length is 1.

delete_both(L, X) :-
    delete_first(L, L1),    % Remove first and last elements from L
    delete_last(L1, LT),
    (   LT = [X]            % Check for length of 1
    ->  true
    ;   delete_both(LT, X)  % otherwise, X is result of delete_both(LT, X)
    ).

With results:

| ?- delete_both([a,b,c,d,e], X).

X = c

yes
| ?- delete_both([a,b,c,d,e,f], X).

no

A DCG solution also works well here:

% X is the middle if it is flanked by two sequences of the same length
%
middle(X) --> seq(N), [X], seq(N).

seq(0) --> [].
seq(N) --> [_], { N #= N1 + 1 }, seq(N1).

middle(List, X) :- phrase(middle(X), List).

With results:

| ?- middle([a,b,c,d,e], X).

X = c ? ;

(1 ms) no
| ?- middle(L, a).

L = [a] ? ;

L = [_,a,_] ? ;

L = [_,_,a,_,_] ?
...

Another possible solution is to use SWI Prolog's append/2 predicate, which appends a list of lists (assuming you're using SWI):

middle(L, X) :-
    same_length(Left, Right),
    append([Left, [X], Right], L).

same_length([], []).
same_length([_|T1], [_|T2]) :- same_length(T1, T2).

In all of the above solutions, the predicate fails if the list has an even number of elements. Since that's what your original solution does, I assumed that's what is required. If there is a specific requirement for even lists, that needs to be stated clearly.

Prolog Finding middle element in List

2 Answers2

Linked