Checking the reverse of a list is the same as the list unchanged?

Question

I am learning scheme and one of the things I have to do is recursion to figure out if the list is reflective, i.e. the list looks the same when it is reversed. I have to do it primitively so I can't use the reverse method for lists. I must also use recursion which is obvious. The problem is in scheme it's very hard to access the list or shorten the list using the very basic stuff that we have learned, since these are kinda of like linkedlists. I also want to do without using indexing. With that said I have a few ideas and was wondering If any of these sufficient and do you think I could actually do it better with the basics of scheme.

1. Reverse the list using recursion (my implementation) and compare the original and this rev. list.
2. Compare the first and last element by recursing on the rest of the list to find the last element and compare to first. Keeping track of how many times I have recursed and then do it one less for the second last element of the list, to compare to the second element of the list. (This is very complicated to do as I've tried it and wound up failing but I want to see you guys would've done the same)
3. Shorten the list to trim off the first and last element each time and compare. I'm not sure if this can be done using the basics of scheme.
4. Your suggestions or hints or anything. I'm very new to scheme. Thanks for reading. I know it's long.

Answer 1

I agree that #1 seems the way to go here. It's simple, and I can't imagine it failing. Maybe I don't have a strong enough imagination. :)

The other options you're considering seem awkward because we're talking about linked lists, which directly support sequential access but not random access. As you note, "indexing" into a linked list is verboten. It ends up marching dutifully down the list structure. Because of this, the other options are certainly doable, but they are expensive.

That expense isn't because we're in Scheme: it's because we're dealing with linked lists. Just to make sure it's clear: Scheme has vectors (arrays) which do support fast random-access. Testing palindrome-ness on a vector is as easy as you'd expect:

#lang racket
;; In Professional-level Racket

(define (palindrome? vec)
  (for/and ([i (in-range 0 (vector-length vec))]
            [j (in-range (sub1 (vector-length vec)) -1 -1)])
    (equal? (vector-ref vec i)
            (vector-ref vec j))))

;; Examples
(palindrome? (vector "b" "a" "n" "a" "n" "a"))
(palindrome? (vector "a" "b" "b" "a"))

so one point of the problem you're tackling, I think, is to show that the data structure you choose---the representation of the problem---can have a strong effect on the problem solution.

(Aside: #2 is certainly doable, though it goes against the grain of the single-linked list data structure. The approach to #3 requires a radical change to the representation: from a first glance, I think you'd need mutable, double-linked lists to do the solution any justice, since you need to be able march backward.)

Answer 2

Checking if a list is a palindrome without reversing it is one of the examples of a technique explained in "There and Back Again" by Danvy and Goldberg. They do it in (ceil (/ (length lst) 2)) recursive calls, but there's a simpler version that does it in (length lst) calls.

Here's the skeleton of the solution:

(define (pal? orig-lst)
  ;; pal* : list -> list/#f
  ;; If lst contains the first N elements of orig-lst in reverse order,
  ;; where N = (length lst), returns the Nth tail of orig-lst.
  ;; Otherwise, returns #f to indicate orig-lst cannot be a palindrome.
  (define (pal* lst)
    ....)

  .... (pal* orig-lst) ....)

This sounds like it might be homework, so I don't want to fill in all of the blanks.

Answer 3

To answer dyoo's question, you don't have to know that you're at the halfway point; you just have to make a certain comparison. If that comparison works, then a) the string must be reversible and b) you must be at the midway point.

So that more efficient solution is there, if you can just reach for it...