Bisecting a List

How would you chop a linked list in half? A trivial approach would be to just get the length of the list and then walk the list building a first-half copy by tracking the indexes until you get to half that length.

Thinking about it, I realized you could use the tortoise-and-hare approach from Floyd's cycle detector to find the middle of the list: walk the list item-by-item and every-other-item at the same time; when the every-other-item list is exhausted, you've found the middle:

% bisect(+List, -First, -Last) is semidet.
% bisect(-List, -First, -Last) is multi.
%   First and Last are equal-length sublists of List such that
%   append(First, Last, List) is true and 
%   length(First, N), length(Last, N) is true.
bisect(L, First, Last) :- bisect(L, L, First, Last).

bisect(Xs, [], [], Xs).
bisect([X|Xs], [_,_|Ys], First, Last) :-
    First = [X|NextFirst],
    bisect(Xs, Ys, NextFirst, Last).

The other trick here is passing the tail of the list to the recursive call, sort of like an inexpensive difference list trick to give us O(N) appending to a linked list.

I'm pleased to note that this just fails for free on non-even length lists. No stupid solutions where one list is longer than the other.

?- bisect([1,2,3,4], X, Y).
X = [1, 2],
Y = [3, 4].

?- bisect([1,2,3,4,5], X, Y).
false.

?- bisect([1,2,3,4,5,6], X, Y).
X = [1, 2, 3],
Y = [4, 5, 6].

?- bisect(Z, X, Y).
Z = X, X = Y, Y = [] ;
Z = [_24123766, _24123772],
X = [_24123766],
Y = [_24123772] ;
Z = [_24123766, _24123772, _24123784, _24123790],
X = [_24123766, _24123772],
Y = [_24123784, _24123790] ;
...