Prolog - get middle element of List

0
votes

I would like to get the middle element of a list in Prolog.

The predicates middle([1,2,3],M) and middle([1,2,3,4],M) should both return 2 as a result. And I am allowed to use the predicate deleteLast.

I know that there are similar posts that solve that question but I have not found one that just uses deleteLast.

Even the syntax is not correct - however this is my solution so far: 

middle([], _).
middle([X|XTail|Y], E) :-
   1 is mod(list_length([X|XTail|Y], 2)),
   middle([XTail], E).
middle([X|XTail|Y], E) :-
   0 is mod(list_length([X|XTail|Y], 2)),
   middle([X|XTail], E).
middle([X], X).

Question: Is that partly correct or am I completely on the wrong path ?

4
listprolog
mod(list_length([...])) doesn't do what you think. list_length/2 is not an arithmetic expression function. It's a predicate. Also, [X|XTail|Y] means what? - lurker
Why don't you walk through the list recursively, drop the head and use deleteLast/2 each time, until you get down to one or two elements? You don't need list_length/2 to determine if the length is 1 or 2. You can just match your list to [X] or [X, _]. Once you're down to one of those, the answer is X. - lurker
People who come up with such exercises are the reason why students end up thinking Prolog is a useless language. - user1812457
@Boris that is so spot on (s(X)) - lurker
@lurker :-) Many years ago I went to a "programming" extracurricular and the teacher tried to show us how to do a bubble sort. I went home convinced that programming is stupid and it took me about 6 years before I attempted it again. Most teachers don't understand or deserve the power they are given. - user1812457

4 Answers

3
votes

Sorry, the attempted solution you have is completely on the wrong path.

  • It doesn't use deleteLast/2 as you stated you require
  • You are using list_length/2 as if it were an arithmetic function, which it is not. It's a predicate.
  • You have a term with invalid syntax and unknown semantics, [X|XTail|Y]

In Prolog, you just need to think about it in terms of the rules. Here's an approach using deleteLast/2:

middle([X], X).     % `X` is the middle of the single element list `[X]`
middle([X,_], X).   % `X` is the middle of the two-element list `[X,_]`

% X is the middle of the list `[H|T]` if X is the middle of the list TWithoutLast
%   where TWithoutLast is T with its last element removed
%
middle([H|T], X) :-
    deleteLast(T, TWithoutLast),
    middle(TWithoutLast, X).

I assume deleteLast/2 is well-behaved and just fails if T is empty.

You can also do this with same_length/2 and append/3, but, alas, doesn't use deleteLast/2:

middle(L, M) :-
    same_length(L1, L2),
    append(L1, [M|L2], L).
middle(L, M) :-
    same_length(L1, L2),
    append(L1, [M,_|L2], L).
1
votes

So much unnecessary work, and unnecessary code. length/2 is very efficient, and a true relation. Its second argument is guaranteed to be a non-negative integer. So:

middle(List, Middle) :-
    List = [_|_],           % at least one element
    length(List, Len),
    divmod(Len, 2, Q, R),   % if not available do in two separate steps
    N is Q + R,
    nth1(N, List, Middle).

And you are about ready:

?- middle(L, M), numbervars(L).
L = [A],
M = A ;
L = [A, B],
M = A ;
L = [A, B, C],
M = B ;
L = [A, B, C, D],
M = B ;
L = [A, B, C, D, E],
M = C ;
L = [A, B, C, D, E, F],
M = C .

I understand that this doesn't solve your problem (the answer by @lurker does) but it answers your question. :-(

0
votes

Here is my attempt:

middle(L,M):- append(L1,L2,L),length(L1,N),length(L2,N), reverse(L1,[M|_]).
middle(L,M):- append(L1,L2,L),length(L1,N),length(L2,N1), N is N1+1 ,
              reverse(L1,[M|_]).

Example: ?- middle([1,2,3],M).

M = 2 ;
false.

?- middle([1,2,3,4],M).
M = 2 ;
false.

In your implementation the problem is that by writing for example:

list_length([X|XTail|Y], 2)

The above does not give you as X the first element and as Y the last so I think it has some major problems...

As well pointed out by lurker you could write the above solution in one clause without using reverse/2:

middle(L, M) :- append(L1, [M|T], L), length(L1, N), length([M|T], N1), 
                (N1 is N + 1 ; N1 is N + 2).

Also to make the solution more relational (also see mat's comment below) you could use CLPFD library and replace is/2 with #= like:

middle(L, M) :- append(L1, [M|T], L), length(L1, N), length([M|T], N1), 
                (N1 #= N + 1 ; N1 #= N + 2).
0
votes

Another interesting solution is to consider this predicate for splitting a list in half:

half(List, Left, Right) :-
    half(List, List, Left, Right).
half(L, [], [], L).
half(L, [_], [], L).
half([H|T], [_,_|T2], [H|Left], Right) :-
    half(T, T2, Left, Right).

This predicate divides an even list into two equal halves, or an odd list into two pieces where the right half has one more element than the left. It does so by reducing the original list, via the second argument, by two elements, each recursive call, while at the same time reducing the original list by one element each recursive call via the first argument. When it recurses down to the second argument being zero or one elements in length, then the first argument represents the half that's left, which is the right-hand list.

Example results for half/3 are:

| ?- half([a,b,c], L, R).

L = [a]
R = [b,c] ? a

(1 ms) no
| ?- half([a,b,c,d], L, R).

L = [a,b]
R = [c,d] ? a

no
| ?-

We can't quite use this to easily find the middle element because, in the even case, we want the last element of the left hand list. If we could bias the right-hand list by an extra element, we could then pick off the head of the right-hand half as the "middle" element. We can accomplish this using the deleteLast/2 here:

middle([X], X).
middle(List, Middle) :-
    deleteLast(List, ListWithoutLast),
    half(ListWithoutLast, _, [Middle|_]).

The head of the right half list of the original list, with the last element deleted, is the "middle" element. We can also simply half/3 and combine it with middle/2 since we don't really need everything half/3 does (e.g., we don't need the left-hand list, or the tail of the right hand list):

middle([X], X).
middle(List, Middle) :-
    deleteLast(List, ListWithoutLast),
    middle(ListWithoutLast, ListWithoutLast, Middle).
middle([M|_], [], M).
middle([M|_], [_], M).
middle([_|T], [_,_|T2], Right) :-
    middle(T, T2, Right).

half/3deleteLast/2
modified_half(List, Left, Right) :-
    modified_half(List, List, Left, Right).
modified_half(L, [_], [], L).
modified_half(L, [_,_], [], L).
modified_half([H|T], [_,_,X|T2], [H|Left], Right) :-
    modified_half(T, [X|T2], Left, Right).

This will bias the right hand list to have an extra element at the "expense" of the left:

| ?- modified_half([a,b,c,d,e], L, R).

L = [a,b]
R = [c,d,e] ? a

no
| ?- modified_half([a,b,c,d,e,f], L, R).

L = [a,b]
R = [c,d,e,f] ? a

no
| ?-

Now we can see that the middle element, per the original definition, is just the head of the right hand list. We can create a new definition for middle/2 using the above. As we did before with half/3, we can ignore everything but the head in the right half, and we can eliminate the left half since we don't need it, and create a consolidated middle/2 predicate:

middle(List, Middle) :-
    middle(List, List, Middle).
middle([M|_], [_,_], M).
middle([M|_], [_], M).
middle([_|T], [_,_,X|T2], Middle) :-
    middle(T, [X|T2], Middle).

This reduces the original list down one element at a time (first argument) and two elements at a time (second argument) until the second argument is reduced to one or two elements. It then considers the head first argument to be the middle element:

This gives:

| ?- middle([a,b,c], M).

M = b ? ;

no
| ?- middle([a,b,c,d], M).

M = b ? ;

no
| ?- middle(L, M).

L = [M,_] ? ;

L = [M] ? ;

L = [_,M,_,_] ? ;

L = [_,M,_] ? ;

L = [_,_,M,_,_,_] ? ;

L = [_,_,M,_,_] ? ;

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