lisp - 方案中子列表的回文

Question

我有一个工作回文，它通过拿汽车并将其与反向汽车进行比较来返回带有原子的单个列表的真/假。然后它用 cdr (reverse (cdr list)) 丢弃第一个和最后一个。

我想让它与子列表中的原子一起工作，这样 '(a b) c (b a)) 就会返回 true。

我试着让它先检查 car 是否是一个列表，如果是，则比较 caar 和 reverse caar 直到它为 null 然后继续。
我收到“对象 #f 不适用”。

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

我也试过这样做，这样它就不会被嵌套，但我想不出来。任何提示或提示表示赞赏。谢谢!

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

Answer 1

这是您的代码，缩进正确:

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

请注意第三个子句为什么没有在应该结束的时候结束？或者您可能在检查 (equal? (caar lst) (caar (reverse lst))) 之前尝试检查几个条件。

当您调用 (pdrome '((a b) c (b a))) 时，它会到达 (LIST? (car lst)) 为真的地步，因此它会评估该子句中的其余代码。即:

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

让我们看第一个:((null? (car lst))())。如何评估？这是一个包含两个元素的列表，因此计算第一个元素:(null? (car lst))。计算结果为 #F。然后，我们有 (#F ())。 #F 处于函数位置(作为代码评估的列表中的第一件事)，但不是函数。所以我们得到错误 Object #f is not applicable。

基本上，cond的每个条款看起来像这样:

(condition form1 form2 ...)

可以有任意数量的形式，包括零。

那么让我们看看你的单句

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

条件是:

(LIST? (car lst))

这是表格。一共有三个:

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

如果条件为真(即 (car lst) 本身就是一个列表)，那么你想做什么？

我将退后一步，像手动操作一样布置算法。

直到我们没有列表了，把第一件事，最后一件事剪掉，看看第一件和最后一件是不是一样。如果这些东西本身就是列表，则反转最后一个。然后在列表的中间(即没有第一个或最后一个元素的列表)继续这样做，直到我们得到一个空列表，或者一个只有一个东西的列表。

现在让我们写一些代码:

(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  

请注意，此代码与书面算法略有不同。当它到达一个包含一个元素的列表时(比如说，它被称为 (palindrome '(a))，它会得到第一个元素 'a，最后一个元素 'a，确保它们相等，然后调用(get-middle '(a))，也就是'()。然后(palindrome '()) 是 #f，所以我们很好。