The sixth L-99 problem is to write a predicate that detects a list that is a palindrome: a sequence that can be read the same way forward or backward.

The simplest (and an efficient) solution is right there in the definition of a palindrome, but it’s easy to “follow your nose” through the construction of palindromes and end up writing something more complicated. The real lesson of the sixth L-99 problem is less about lists and more about “forests” and “trees”.

The problem description immediately restricts us to a list representation, and, although it isn’t specified, I’ll assume the list must be proper. LIST-PALINDROME-P should work as follows:

(list-palindrome-p 42) ; TYPE-ERROR: 42
(list-palindrome-p '(a b c d . e)) ; TYPE-ERROR: E
(list-palindrome-p '()) => T
(list-palindrome-p '(a b b a)) => T
(list-palindrome-p '(a b c b a)) => T
(list-palindrome-p '(a b c b a b)) => NIL

First, I’ll write a utility function to construct palindrome lists:

(defparameter *alphabet* "abcdefghijklmnopqrstuvwxyz")

(defparameter *alphabet-length* 26)

(defun random-character ()
  (elt *alphabet*
       (random *alphabet-length*)))

(defun make-palindrome (length)
  (let ((l '()))
    (multiple-value-bind (quotient remainder)
        (floor length 2)
      (dotimes (i quotient)
        (push (random-character) l))
      (let ((middle (if (plusp remainder)
                        (list (random-character))
                        '())))
        (append l middle (reverse l))))))

CL-USER> (make-palindrome 11)
=> (#\y #\i #\z #\d #\j #\y #\j #\d #\z #\i #\y)

While scratching that out, I was thinking about a point in the Wikipedia article on palindromes:

In addition, the set of palindromes may not be reliably tested by a deterministic pushdown automaton and is not LR(k)-parsable. When reading a palindrome from left-to-right, it is, in essence, impossible to locate the “middle” until the entire word has been read completely.

The middle… right! If I can find the middle of the list, I can traverse the list from both ends at once, comparing corresponding elements. If a pair of elements differs, the list is not a palindrome; otherwise, when the pointers meet or pass, I have a palindrome. Easy enough to write:

(defun list-palindrome-p (list)
  (do ((i 0 (1+ i))
       (j (1- (length list)) (1- j)))
      ((or (= i j) (< j i)) t)
    (unless (equal (nth i list)
                   (nth j list))
      (return nil))))

That will run in O(1) space and O(n^2) time. To measure the performance gain, if any, of the list-specific accessor NTH, I wrote a version using the more general ELT sequence accessor:

(defun seq-palindrome-p (seq)
  (do ((i 0 (1+ i))
       (j (1- (length seq)) (1- j)))
      ((or (= i j) (< j i)) t)
    (unless (equal (elt seq i)
                   (elt seq j))
      (return nil))))

To measure the performance hit of list element access, O(n) on average, I wrote a vector-based version using the SVREF vector accessor:

(defun vector-palindrome-p (vector)
  (do ((i 0 (1+ i))
       (j (1- (length vector)) (1- j)))
      ((or (= i j) (< j i)) t)
    (unless (equal (svref vector i)
                   (svref vector j))
      (return nil))))

Here are some benchmarks under SBCL 1.0.50 on my machine:

CL-USER> (compile 'list-palindrome-p)
=> LIST-PALINDROME-P

CL-USER> (compile 'seq-palindrome-p)
=> SEQ-PALINDROME-P

CL-USER> (compile 'vector-palindrome-p)
=> VECTOR-PALINDROME-P

CL-USER> (defparameter *palindrome* (make-palindrome 100001))
=> ...

CL-USER> (defparameter *vpalindrome* (coerce *palindrome* 'vector))
=> *VPALINDROME*

CL-USER> (defparameter *result* nil)
=> *RESULT*

CL-USER> (gc :all t)
=> NIL

CL-USER> (time (dotimes (i 1000 (setf *result* (list-palindrome-p *palindrome*)))))
Evaluation took:
  9.641 seconds of real time
  10.133459 seconds of total run time (10.133459 user, 0.000000 system)
  105.10% CPU
  19,234,325,700 processor cycles
  66,096 bytes consed
=> T

CL-USER> (gc :all t)
=> NIL

CL-USER> (time (dotimes (i 1000 (setf *result* (seq-palindrome-p *palindrome*)))))
Evaluation took:
  38.109 seconds of real time
  39.323022 seconds of total run time (39.323022 user, 0.000000 system)
  103.19% CPU
  76,026,725,220 processor cycles
  254,312 bytes consed
=> T

CL-USER> (gc :all t)
=> NIL

CL-USER> (time (dotimes (i 1000 (setf *result* (vector-palindrome-p *vpalindrome*)))))
Evaluation took:
  0.002 seconds of real time
  0.002000 seconds of total run time (0.002000 user, 0.000000 system)
  100.00% CPU
  3,609,922 processor cycles
  0 bytes consed
=> T

The list-specific accessor NTH is faster and conses less than ELT. Unsurprisingly, where repeated arbitrary element access is required, a vector is the better choice. VECTOR-PALINDROME-P runs in O(n) time and O(1) space.

However, I can write a list-based solution that is simpler and faster than LIST-PALINDROME-P. It trades space (O(n)) for speed (O(n)). As I noted above, a palindrome is a sequence that reads the same forward or backward:

(defun simple-list-palindrome-p (list)
  (equal list (reverse list)))

CL-USER> (gc :all t)
=> NIL

CL-USER> (time (dotimes (i 1000 (setf *result* (simple-list-palindrome-p *palindrome*)))))
Evaluation took:
  0.002 seconds of real time
  0.002000 seconds of total run time (0.002000 user, 0.000000 system)
  100.00% CPU
  4,399,568 processor cycles
  802,816 bytes consed

#l-99