I’m beginning to teach myself Haskell, because we all have to. I started doing the 99 Haskell problems and came across a beautifully cunning solution to problem 6, “Find out whether a list is a palindrome.” Let’s first look at the classic solution, which is maximally declarative. I use Prolog here to formulate it:
palindrome(X) :-
reverse(X,X).
It reverses the list, then checks if the result is the same as the original (that’s the definition of a palindrome). It checks that by going through both lists and comparing elements at corresponding positions.
What’s ugly about this is that this is at least twice as many comparisons as needed. Since we know one list is the reverse of the other, it suffices to compare the first half of one to the last half of the other. (In lists of odd length, the center element does not need to be compared at all, since it is always identical to itself.)
Alternatively, we could just traverse the list to check, carrying along a reversed version of what we have traversed so far, stop in the middle and then compare the reversed first half to the remainder (i.e. to the last half). The problem is: where to stop? We don’t know the length of the list until we have traversed the whole of it, hence we also don’t know what half its length is.
Enter the intriguing solution that was given on the Haskell Wiki, humbly titled “Here’s one that does half as many compares”, and that gave me a very nice lightbulb moment when I had gotten my head around it. Here’s my Prolog translation:
palindrome(List) :-
palindrome(List,[],List).
palindrome([First|Rest],Rev,[_,_|Rest2]) :-
palindrome(Rest,[First|Rev],Rest2).
palindrome([_|Rev],Rev,[_]).
palindrome(Rev,Rev,[]).
The trick is to carry along a second copy of the original list, popping two elements from it every time we pop one from the main copy. This way, when we reach the end of the second copy, we know we have reached the center of the first. There’s two recursion-ending clauses, one for odd-length and one for even-length lists. Ingenious!
