CODEWITHSUNDEEP
lispscheme
user2946437
user2946437

Reputation: 23

Palindrome of sublists in scheme

I have a working palindrome that returns true/false for a single list with atoms by taking the car and comparing it to reverse car. It then throws away the first and last with cdr (reverse (cdr list)).

I'd like to make it work with atoms within sublists so that '(a b) c (b a)) would return true.

I'm trying to have it first check if car is a list and if so compare caar and reverse caar until it's null then continue on.
I'm getting "Object #f is not applicable".

(DEFINE (pdrome lst)
  (cond
    ; ((NOT (LIST? lst)) DISPLAY "USAGE: (palindrome [list])" )
    ((null? lst) #t)
     ((null? (cdr lst)) #t)

     ((LIST? (car lst))
       ((null? (car lst) ) () )
       ((null? (cdr lst) ) () )
    ((equal? (caar lst) (caar (reverse lst)))
    (pdrome (cdar (reverse(cdar lst))))))

     ((equal? (car lst) (car(reverse lst))) 
      (pdrome (cdr (reverse (cdr lst)))))

        (else #F) ) )

I also tried to do it this way so it wouldn't be nested but I can't figure this out. Any tips or hints appreciated. Thanks!

(LIST? car lst)  
palindrome (append (caar lst) (caar (reverse lst)))

Upvotes: 0

Views: 3264

Answers (2)

zck
zck

Reputation: 2762

Here's your code, indented properly:

(DEFINE (pdrome lst)
  (cond
   ((null? lst) #t)
   ((null? (cdr lst)) #t)
   ((LIST? (car lst))
    ((null? (car lst))())
    ((null? (cdr lst))())
    ((equal? (caar lst) (caar (reverse lst)))
     (pdrome (cdar (reverse(cdar lst))))))
   ((equal? (car lst) (car(reverse lst))) 
    (pdrome (cdr (reverse (cdr lst)))))
   (else #F)))

Note how the third clause doesn't end when it should? Or perhaps you're trying to check several conditions before checking (equal? (caar lst) (caar (reverse lst))).

When you call (pdrome '((a b) c (b a))), it gets to the point where (LIST? (car lst)) is true, so it then evaluates the rest of the code in that clause. That is:

    ((null? (car lst))())
    ((null? (cdr lst))())
    ((equal? (caar lst) (caar (reverse lst))

Let's look at the first one: ((null? (car lst))()). How does this get evaluated? It's a list with two elements in it, so evaluate the first: (null? (car lst)). That evaluates to #F. Then, we have (#F ()). #F is in functional position (the first thing in a list evaluated as code), but isn't a function. So we get the error Object #f is not applicable.

Basically, each clause of cond looks like this:

(condition form1 form2 ...)

There can be any number of forms, including zero.

So let's look at your single clause

((LIST? (car lst))
 ((null? (car lst))())
 ((null? (cdr lst))())
 ((equal? (caar lst) (caar (reverse lst)))
  (pdrome (cdar (reverse(cdar lst))))))

Here's the condition:

(LIST? (car lst))

And here are the forms. There are three of them:

 ((null? (car lst))())
 ((null? (cdr lst))())
 ((equal? (caar lst) (caar (reverse lst)))
  (pdrome (cdar (reverse(cdar lst))))))

If the condition is true (that is, (car lst) is itself a list), what do you then want to do?

I'm going to step back for a minute and lay out the algorithm as I would do it by hand.

Until we don't have a list anymore, cut off the first thing, the last thing, and see if the first is same as the last. If those things themselves are lists, reverse the last one. Then keep doing this on the middle of the list (that is, the list without the first or last elements) until we end up with either an empty list, or a list with just one thing in it.

Now let's write some code:

(define (palindrome lst)
  (if (null? lst)
      #t
      (let ((first-element (car lst))
            (last-element (car (reverse lst))))
        (and (equal? first-element
                     (if (list? last-element)
                         (reverse last-element)
                         last-element))
             (palindrome (get-middle lst))))))

(define (get-middle lst)
  (if (null? (cdr lst))
      '()
      (reverse (cdr (reverse (cdr lst))))))

> (palindrome '())
#t
> (palindrome '(a))
#t
> (palindrome '((a)))
#t
> (palindrome '((a) b))
#f
> (palindrome '((a) b (a)))
#t
> (palindrome '((a b) c (b a)))
#t

Note that this code differs slightly from the written algorithm. When it gets to a list with one element (say, it's called (palindrome '(a)), it'll get the first element 'a, the last element 'a, make sure they're equal, then call (get-middle '(a)), which is '(). And then (palindrome '()) is #f, so we're good.

Upvotes: 1

uselpa
uselpa

Reputation: 18917

The easiest way to do this is to use a deep-reverse procedure that will recursively reverse a list. 

(define (deep-reverse l) 
  (if (list? l) 
      (reverse (map deep-reverse l)) 
      l))

See how it compares to the build-in reverse:

-> (reverse '((a b) c (d e)))
'((d e) c (a b))
-> (deep-reverse '((a b) c (d e)))
'((e d) c (b a))

So a palindrome is simply a list that is equal? to its deep-reverse:

(define (pdrome? lst)
  (equal? lst (deep-reverse lst)))

Upvotes: 0

Related Questions