方案问题 - 如何检查是否存在配对列表

Question

所以我需要在方案上编写代码来检查是否存在对列表？关于从哪里开始有什么想法吗？

  (define (list-of-pairs? lst)
    (if (null? lst)
        #f
        (if (pair? (cdr lst))
            #t
            (list-of-pairs? (cddr lst)))))

如果这是正确的，我不知道从这里该去哪里

我知道这是错误的，因为我收到此错误

对列表？：数量不匹配； 预期的参数数量与给定的数量不匹配 预计：1 给定：4 论据...：

当我输入这个

(list-of pairs?
   (list
   (cons 1 (cons 2 empty))
   (cons 2 (cons null empty))
   (cons 3 (cons 4 (list 4 5 6))))

Answer 1

“我知道这是错误的，因为我收到此错误。”此错误与发布的代码无关。相反，OP 似乎在测试定义的过程中经历了一些拼写错误的结果。发布的测试至少包含两个拼写错误：

list-of pairs?

缺少连字符，整个表达式缺少右括号；这让我相信OP已将表达式输入到问题正文中，而不是复制粘贴。如果这是实际的测试表达式，则错误可能更多地类似于 list-of undefined;无法在定义之前引用标识符。

顺便说明一下，此代码包含标准方案中未定义的

empty

和

null

；看起来OP实际上是在写Racket，但这并没有实质性改变OP问题的答案。

发布的代码有问题

list-of-pairs?

的 OP 定义不正确。要了解原因，让我们看一些输入示例：

> (list-of-pairs? '())
#f
> (list-of-pairs? '(1))
cddr: contract violation
  expected: (cons/c any/c pair?)
  given: '(1)
 [,bt for context]
> (list-of-pairs? '(1 2))
#t

首先，当输入为空列表时，OP 的过程返回

#f

。通常我希望这种情况会产生

#t

，因为空列表是空的对列表，并且是您能想到的任何其他类型。就其本身而言，这并不会破坏交易，并且可以明智地编写该过程以在这种情况下返回

#f

。

接下来的两种情况会出现更严重的问题。当输入是包含单个整数的列表时，我希望该过程产生

#f

，但结果却是一个错误。为什么？列表

(1)

不为空，因此 OP 过程继续检查

cdr

中的

(1)

是否是一对；但是

cdr

的

(1)

是

()

，

(pair? '())

是

#f

，所以最后OP程序检查

cddr

的

(1)

是否是

list-of-pairs?

。但是，

(cddr '(1))

在Scheme（和Racket）中是未定义的。展开此调用显示：

(cddr '(1))

->

(cdr (cdr '(1)))

->

(cdr '())

-> 错误！

此外，当输入是整数列表时，OP 过程会意外返回

#t

。这是不对的，因为整数不是对，并且整数列表肯定不是对列表。这里发生了什么？当输入为

(1 2)

时，它不为空，并且

cdr

的

(1 2)

是

(2)

，这实际上是一对，因为 每个 列表都是一对！具体来说，每个列表都是由

car

部分和

cdr

部分组成的对。

这里的一个根本问题是 OP 过程根据问题的需要错误地将其列表输入分开。

一个解决方案

要递归地解决问题，您始终需要确定至少两件事：基本情况是什么，以及递归步骤是什么。基本案例是一个可以立即找到答案的简单案例。递归步骤以某种方式将输入情况减少到基本情况。通常，您需要以某种方式组合每个递归调用的结果。 有时，描述我们想要的内容是有帮助的（在这种情况下，描述

list-of-pairs?

的构成）：

list-of-pairs?

是一个空列表，或者第一个元素是一对的列表，其余元素是列表是

list-of-pairs?

。这里，基本情况是输入为空列表时。在这种情况下，假设结果应该是

#t

，也就是说，空列表是空的对列表。当输入是非空列表时，如何将其简化为基本情况？如果输入的

first

元素不是对，我们就完成了，因为输入不是对的列表。但是，如果第一个元素是一对，那么我们需要将这些知识与有关输入列表其余部分的知识结合起来。也就是说，如果输入的 car 是一对，并且输入的其余部分是

list-of-pairs?

，则输入是对的列表。这里，通过使用

list-of-pairs?

，递归调用

cdr

的列表已经减少到基本情况。这是解决方案：

(define (list-of-pairs? xs)
  (if (null? xs)
      #t
      (and (pair? (car xs))
           (list-of-pairs? (cdr xs)))))

这里输入的第一个元素的知识和列表其余部分的状态是使用 

and

运算符组合的。当（任何递归调用的）第一个元素不是一对时，将返回

#f

并与任何先前的

#t

值组合以产生

#f

。否则返回

#t

。如果希望空列表不应该是成对的列表，可以稍微考虑一下上面的内容，但我会将其作为练习留给读者。