LISP check if list is symmetrical without reverse

Question

Anyone have any ideas on how to do this... reverse is too slow, and I want to avoid using the function.

Basically I want to be able to return true if something like '(a b b a) comes up or '(a b c d c b a)

and false for something not symmetrical

Answer 1

Isn't this a good solution? Or you could search for other solutions by using "palindrome lisp" as keywords in your favorite search engine.

Answer 2

I'm not sure why using REVERSE is insufficiently efficient; have you actually profiled the solution? You just traverse the list once to do it; same as (say) finding the length of the list, and then you can traverse the two lists once to compare.

If you wanted to be a little fancier, you could simultaneously find the length of the list and reverse it using LOOP as so:

(defun fancier-palindrome-p (list)
  (let ((reversed '()) (length 0)) 
    (dolist (elt list)
      (incf length)
      (push elt reversed)) 
    (dotimes (i (floor length 2) t)
      (unless (eql (pop list) (pop reversed))
        (return nil)))))

This allows you to skip half the checks. I don't think this is worth the additional complexity. You can also use move down the list with a tortoise and hare to save half the consing at the cost of even more complexity.

 (defun ridiculous-palindrome-p (list)
   (let ((reversed-front '()))
     (loop  
       :for tortoise :on list 
       :for hare :on list :by #'cddr 
       :until (null (cdr hare)) 
         :do (push (car tortoise) reversed-front)
       :finally  
         (return  
          (if (null hare) ; length is even 
            (equal tortoise reversed-front)
            (equal (cdr tortoise)  
                   reversed-front))))))

Neither of these solutions strikes me as more compelling than

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

If this really is a bottleneck, perhaps you'd be better off using vectors as your sequence representation to take advantage of the fast random access, like so:

(defun vector-palindrome-p (vector)
  (let* ((n (length vector)) (j n))
    (dotimes (i (floor n 2) (return t))
      (unless (eql (aref vector i) 
                   (aref vector (decf j)))
      (return nil)))))