Проверка палиндрома с рекурсией в Лиспе

Question

Я разработал код для проверки ввода, чтобы увидеть, палиндром это или нет, но мне сложно понять, как напечатать вывод. Я хочу, чтобы вывод возвращал «t», если входной сигнал - палиндром, и «nil», если нет. Еще одна проблема, которую я хотел решить, заключалась в том, чтобы не использовать обратную функцию, поэтому мой код не так прост, как мог бы быть. Заранее спасибо.

(defun palindromep(l)
  (cond ((null l) nil (write nil))
        (t (append (list (car l)) (palindromep (cdr l)) (list (car l) )))))


        (palindromep '(a b b a))
        (terpri)
        (palindromep '(a b c b a))
        (terpri)
        (palindromep '(a b c))
        (terpri)
        (palindromep '(a (d e) (d e) a))
        (terpri)
        (palindromep '(a (d e) (e d) a))

Answer 1

К go вкл. При игре в код, так как ожидается t или nil, вы можете использовать только условные выражения or и nil до express (и использовать короткое замыкание or и nil выражений).

Также полезно иметь возможность определить ключевое слово :test, поскольку вы хотите контролировать критически важные тестовые действия. Чтобы иметь возможность использовать также внутренние списки, можно, например, использовать equalp или даже пользовательскую функцию сравнения.

(defun palindromep (l &key (test #'equalp))
  (or (null l) (and (funcall test (car l) (car (last l)))
                    (palindromep (butlast (cdr l)) :test test))))

Это оценивает

(palindromep '(a (d e) (d e) a))

как t, но

(palindromep '(a (d e) (e d) a))

как nil. Ну, это может быть философский вопрос, должно ли последнее быть t, а первое nil.

Чтобы изменить это поведение, мы могли бы написать пользовательскую функцию тестирования.

Как это:

(defun reverse* (l &optional (acc '()))
  (cond ((null l) acc)
        ((atom (car l)) (reverse* (cdr l) (cons (car l) acc)))
        (t (reverse* (cdr l) (cons (reverse* (car l) '()) acc)))))

(defun to-each-other-symmetric-p (a b)
  (cond ((and (atom a) (atom b)) (equalp a b))
        (t (equalp a (reverse* b)))))

Хорошо, я использую здесь какой-то reverse*.

Тогда, если кто-то делает:

(palindromep '(a (d e) (d e) a) :test #'to-each-other-symmetric-p) ;; NIL
;; and
(palindromep '(a (d e) (e d) a) :test #'to-each-other-symmetric-p) ;; T

Answer 2

Просто для завершения других ответов, я хотел бы отметить, что неиспользование reverse не только сильно усложнит ваш код, но и сделает его гораздо более неэффективным. Просто сравните приведенные выше ответы с classi c one:

(defun palindromep (l)
  (equal l (reverse l)))

reverse - это o (l), то есть требуется время, пропорциональное длине списка l, и то же самое происходит с equal , Так что эта функция будет работать в o (l). Вы не можете получить быстрее, чем это.

Answer 3

Во-первых, пустой список - это палиндром! Если мы перевернем его, мы получим тот же пустой список.

Во-вторых, функции Lisp не выводят свои значения результатов; они возвращают эти значения.

В интерактивном сеансе именно слушатель печатает результирующие значения, которые появляются из вычисляемого выражения. Само это выражение не должно ничего печатать.

Поэтому мы начинаем так:

(defun palindromep (l)
  (cond
    ((null l) t) ;; the empty list is a palindrome: yield true.

Обратите внимание, кстати, что если мы напишем это:

    ((null l) nil t) ;; the empty list is a palindrome: yield true.

это ничего не делает. Выражается дополнительное выражение nil, которое выдает nil, которое выбрасывается. Компилятор Lisp полностью устранит это.

Что если список вообще не является списком, а атомом, отличным от nil? Давайте просто 1049 с палиндромом. Однако необходимо уточнить требования:

    ((atom l) t)

Теперь мы знаем, что имеем дело с непустым списком. Если в нем ровно один предмет, то это палиндром:

    ((null (cdr l)) t)

Теперь мы знаем, что имеем дело со списком из двух или более предметов. Это палиндром, если первый и последний элементы совпадают, и если элементы между ними образуют палиндром.

    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))

Все это:

(defun palindromep (l)
  (cond
    ((null l) t)
    ((atom l) t)
    ((null (cdr l)) t)
    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))

Код игры в гольф: в конструкции cond, описанной ANSI CL, предложение может иметь только одну форму. Если эта форма дает истинное значение, то это значение возвращается. Таким образом, мы можем удалить t:

(defun palindromep (l)
  (cond
    ((null l))        ;; t removed
    ((atom l))        ;; likewise
    ((null (cdr l)))  ;; likewise
    (t (let* ((first (car l))
              (rest (cdr l))
              (tail (last l))
              (interior (ldiff rest tail)))
         (and (eql first (car tail)) (palindromep interior))))))

Документация о функциях ldiff и last может быть найдена здесь .

Дальнейшая игра в гольф : если у нас есть этот шаблон (cond (A) (B) ... (t Z)), мы можем просто заменить его на (or A B ... Z):

(defun palindromep (l)
  (or (null l)
      (atom l)
      (let* ((first (car l))
             (rest (cdr l))
             (tail (last l))
             (interior (ldiff rest tail)))
        (and (eql first (car tail)) (palindromep interior)))))

cond подобен обобщению or, которое может указывать альтернативное значение результата для каждого завершения истинный случай.