<brlewis@my-dejanews.com> wrote:
+---------------
|   Christophe Darlot <darlot@lib.univ-fcomte.fr> wrote:
| > I'm looking for an efficient way of decidindg if a list is a
| > palindrom or not. ...  to avoid using the primitive reverse
| 
| Avoiding using the primitive reverse won't win you efficiency.
+---------------

Indeed. Assuming that "reverse" and "equal?" are both efficiently
coded as primitives which don't allocate memory, "(equal? x (reverse x))"
will be faster than any explicit traversal of the list "x", when run
in an environment in which user procedure calls have to allocate heap
memory (for, say, an argument list or a stack frame).

However, if your Scheme can do non-tail calls (including "let") *without*
allocating heap memory, the following slightly-sneaky code just might be
faster -- it's fully functional and it doesn't explicitly allocate (as
"reverse" does, or the other replies using "cons" and "list->vector" did):

	(define (palindrome? x)
	  (define (helper down up)
	    (if (null? down)
	      up
	      (let ((this (car down))
		    (that (helper (cdr down) up)))
		(and that
		     (equal? this (car that))
		     (cdr that)))))
	  (or (not (pair? x))
	      (null? (helper x x))))

Note: This yields #t on the empty list and *any* non-list (including #f)!
If you want some other behavior, just tweak the "or"...


-Rob

p.s. Extra credit: Add a call/cc to do an "early exit" on failure...

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA