2

I am writing a lisp function, that will determine if a word is a palindrome without using the 'reverse' function. I am fairly new to lisp and I am still trying to grasp the concept. The function is returning NIL every time I test a palindrome, any ideas why?

My function I have came up with. 

(defun palindromep (list)
    (cond
        ((null list)t)
        (t
            (and (equal (first list) (first (rest list)))
                (palindromep (butlast (rest list)))))))

Code revision 

(defun palindromep (list)
    (cond
        ((null list)t)
        (t
            (and (equal (first list) (first(last list)))
                (palindromep (butlast(rest list)))))))
Improve this question

1 Answer 1

Reset to default
1

How I see it it seems to work an a special set of palindromes where there are even number of elements of the same kind.

You'll need to return t for one element list. ie. (null (cdr list)).

The check you have checks if the two first elements are the same instead if the first and the last elements are the same.

EDIT

The best way to do this with recursion and without using reverse that I can think of is this way:

(defun palindromep (list)
  (labels ((aux (history tortoise hare)
             (cond ((null hare) (equal tortoise history))
                   ((null (cdr hare)) (equal (cdr tortoise) history))
                   (t (aux (cons (car tortoise) history)
                           (cdr tortoise)
                           (cddr hare))))))
    (aux '() list list)))

How it works is by having an extra cursor hare that iterates twice the distance as the tortoise and at the same time the seen element is accumulated in history. Since cons makes lists from end to beginning the history is all the seen elements in reverse and thus should match the end when you have reached the middle. When either cdr or cddr of hare is null you are at the middle and can determine palindrome by an easy comparison.

EDIT 2

If you move the helper out it's easier to trace and see what is happening:

(defun aux (history tortoise hare)
  (cond ((null hare) (equal tortoise history))
        ((null (cdr hare)) (equal (cdr tortoise) history))
        (t (aux (cons (car tortoise) history)
                (cdr tortoise)
                (cddr hare)))))

(defun palindromep (list)
  ;; just calls helper
  (aux '() list list))

;; trace the helper
(trace aux)
(trace equal) ; you might need to follow instructions to unlock

(palindromep '(1 2 3 3 2 1))
  0: (AUX NIL (1 2 3 3 2 1) (1 2 3 3 2 1))
    1: (AUX (1) (2 3 3 2 1) (3 3 2 1))
      2: (AUX (2 1) (3 3 2 1) (2 1))
        3: (AUX (3 2 1) (3 2 1) NIL)
          4: (EQUAL (3 2 1) (3 2 1))
          4: EQUAL returned T
        3: AUX returned T
      2: AUX returned T
    1: AUX returned T
  0: AUX returned T
==> T

(palindromep '(1 2 3 4 5 6))
  0: (AUX NIL (1 2 3 4 5 6) (1 2 3 4 5 6))
    1: (AUX (1) (2 3 4 5 6) (3 4 5 6))
      2: (AUX (2 1) (3 4 5 6) (5 6))
        3: (AUX (3 2 1) (4 5 6) NIL)
          4: (EQUAL (4 5 6) (3 2 1))
          4: EQUAL returned NIL
        3: AUX returned NIL
      2: AUX returned NIL
    1: AUX returned NIL
  0: AUX returned NIL
==> NIL
Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

I revised my code and now it is telling me every thing i enter is a palindrome, any suggestions?
@RileyThomas Thats because the argument to the recursion was correct, but not anymore. THe recursion is no longer done only when the first element macthes but always going until you hit the base case, the empty list. Also the test for one element list should have been together with the test for empty list. (or a b) or as separate terms in the cond. How it is now it's done always in the default case and not as a tail expression.
the revision I made seems to work now. Any suggestion on how I could rewrite the last line of my function so that it still does the same thing?
@RileyThomas It seems like the default case is ok. You need to check for (or (null list) (null (cdr list))) instead of just (null list) and it will work for odd element palindromes as well. Since you only have two terms if would work just as well with if
ok I will include that, is there another way I could say (palindromep (butlast(rest list)) ?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.