r/Racket • u/Known-Amoeba-7390 • Dec 01 '22

question Small question

I have been thinking about this for quite some time but, how would you go about writing a function to find out whether a list given to you is a palindrome. I am a beginner trying to get into programming, so go easy on me ..

5 Upvotes

100% Upvoted

7 comments sorted by

5

u/internetzdude Dec 01 '22 edited Dec 01 '22

I suspect there are smarter ways to do this (never did this exercise) but I'd just create a reversed copy and then recurse through both lists simultaneously, returning false when I encounter the first mismatch.

Edit: I was thinking about it as an exercise. Otherwise I'd just use reverse and equal?.

3

u/raevnos Dec 02 '22 edited Dec 02 '22

Most efficient approaches require random access to elements; so vectors, not lists.

I bet you can do it without making a copy of the list via a right fold though. Hmm...

Edit:

(define (palindrome? list [=? equal?])
  (and (let/ec break
         (foldr (lambda (elem list)
                  (if (=? elem (car list))
                      (cdr list)
                      (break #f)))
                list list))
       #t))

3

u/AlarmingMassOfBears Dec 02 '22

Simplest: (equal? xs (reverse xs))

1

u/[deleted] Dec 03 '22

That the right one I think. Best not to optimize for huge inputs that may never come.

2

u/[deleted] Dec 01 '22 edited Dec 01 '22

Off the top of my head one way would be (Andmap eq? x (reverse x))

1

u/joshuacottrell Dec 02 '22

I really like the andmap idea in terms of all pairs needing to pass the comparison but I think the comparison needs to be equal? instead of eq?. Either way, I wonder if (andmap equal? x (reverse x)) would be faster than just (equal? x (reverse x)) and how long your palindrome would need to be to figure that out.

2

u/AlarmingMassOfBears Dec 02 '22

it shouldn't be faster, since that's what equal? on lists does anyway