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] ; ...