CODEWITHSUNDEEP
listlispcommon-lispclisp
Riley Thomas
Riley Thomas

Reputation: 63

Why is my lisp function returning 'NIL'

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

Upvotes: 2

Views: 891

Answers (1)

Sylwester
Sylwester

Reputation: 48745

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

Upvotes: 1

Related Questions