lisp - “car: contract violation expected: pair?” 插入树时

Question

Write a procedure called insert-list which takes a list of numbers L and a tree T, and returns the tree that results by inserting all numbers from L into T.

这是我的代码:

(define (make-tree value left right) (list value left right))
(define (value tree) (car tree))
(define (left tree) (cadr tree))
(define (right tree) (caddr tree))

(define (insert-list L T)
  (cond ((null? L) T)
        ((null? T) (insert-list (cdr L) (make-tree (car L) '() '())))
        ((= (car L) (value T)) (insert-list (cdr L) T))
        ((< (car L) (value T)) (insert-list (cdr L) (make-tree (value T)(insert-list L (left T)) (right T))))
        ((> (car L) (value T)) (insert-list (cdr L) (make-tree (value T) (left T)  (insert-list L (right T)))))))

我不断收到错误:

car: contract violation
  expected: pair?
  given: 4

为什么我总是收到这个错误？

Answer 1

我认为你的代码是对的，问题是测试用例。

Make tree 需要一个值和两个(可能为空的)列表。

(insert-list '(3 4 5) '())

给予

(3 () (4 () (5 () ())))

我认为这就是您想要的测试用例。

错误是因为程序在树的第二个和第三个位置期待一个列表，并试图分解 4，导致你看到的错误。具体错误是小于分支在'(3 4 5)上调用(right t)，并传递结果4插入列表:

(insert-list (list 1 2 3 4) 4)

equals 子句是在调用 (value 4) 时抛出错误的子句，它会导致您看到您看到的错误:

> (car 4)
. . car: contract violation
  expected: pair?
  given: 4

为了帮助您更好地理解，这些是我查看的测试用例，以得出代码正确的结论:

(require test-engine/racket-tests)
; Check tree generation
(check-expect (make-tree '() '() '()) '('() '() '()))
(check-expect (make-tree 3 '() '()) (list 3 '() '()))

; Null list case
(check-expect (insert-list '() '(1 '() '())) '(1 '() '()))
; Null tree case
(check-expect (insert-list (list 1) '()) '(1 '() '()))
; left case
(check-expect (insert-list '(2) (make-tree 3 '() '())) '(3 '(2) '())) 
; right case
(check-expect (insert-list '(4) (make-tree 3 '() '())) '(3 '() '(4)))
; nested left case
(check-expect (insert-list '(2 1) '(3 '() '())) '(3 '(2 '(1) ()) ()))
; nested right case
(check-expect (insert-list '(4 5) '(3 '() '())) '(4 '() '(5 '() '())))

(check-expect (insert-list (list 3 1 2 3 4 5) (make-tree 1 '() '())) 
    (1 () (3 (1 () (2 () (3 () (4 () (5 () ()))))) (4 () (5 () ())))))