# 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

; 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?-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)