constant-space palindromes

Write a predicate that accepts a list and uses constant space to return true iff the list is a palindrome.

 $ cat lipa.rkt 
 #lang racket 
  
 (define (list-palindrome?-linked l) 
  
   ; Return true iff the given list is a palindrome. 
  
   ; This algorithm uses constant space but quadratic time (repeated,  
   ; diminishing list traversals). 
  
   (define (search start end value) 
  
     ; Return a pointer to the last node in the (sub)list [start end) iff the  
     ; last node contains the given value; otherwise return the empty list. 
      
     (let loop ((start start)) 
       (let ((next-start (cdr start))) 
         (if (eq? next-start end) 
             (if (eq? (car start) value) 
                 start 
                 '()) 
             (loop next-start))))) 
  
   (let loop ((start l) (end '())) 
     (cond 
       ((eq? start end) 
        #t) 
        
       ((eq? (cdr start) end) 
        #t) 
        
       (#t 
        (let* ((next-start (cdr start)) 
               (e (search (cdr start) end (car start)))) 
          (if (null? e) 
            #f 
            (loop next-start e))))))) 
  
  
 ; Passing around pointers is a bit obscure (i.e., I got it wrong the first 
 ; time).  Using indices makes the algorithm more straightforward. 
  
  
 (define (list-palindrome?-indexed l) 
  
   ; Return true iff the given list is a palindrome. 
  
   ; Assuming a non-ridiculous list-ref implementation, this algorithm also 
   ; uses constant space and quadratic time. 
  
   (let loop ((l l) (end-index (- (length l) 1))) 
     (cond 
       ((< end-index 1) 
         #t) 
       ((eq? (list-ref (cdr l) (- end-index 1)) (car l)) 
        (loop (cdr l) (- end-index 2))) 
       (#t 
        #f)))) 
          
  
 (require rackunit "utl.rkt") 
  
 (define (testing-1 f) 
   (for-each (lambda (p) (check-equal? (f (car p)) (cadr p))) 
             '((() #t) 
               ((1) #t) 
               ((1 1) #t) 
               ((1 2) #f) 
               ((1 2 1) #t) 
               ((1 1 2) #f)))) 
  
 (testing-1 list-palindrome?-linked) 
 (testing-1 list-palindrome?-indexed) 
  
 (define (testing-2 N) 
   (let* ((n (quotient N 2)) 
             (l (append (build-list n (lambda (i) 1)) 
                        (build-list (- N n) (lambda (i) 2)))) 
             (t (lambda (l) 
                  (check-equal? (list-palindrome?-linked l) 
                                (list-palindrome?-indexed l))))) 
     (call-with-list-permutations l t))) 
  
 (testing-2 5) 
 (testing-2 6) 
 (testing-2 7) 
 (testing-2 8) 
  
 $ racket lipa.rkt 
  
 $