“car: contract violation expected: pair?” while inserting into a tree

13,003

I think your code is right, and the problem is the test case.

Make tree expects a value and two (potentially empty) lists.

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

gives

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

Which I think is what you want for your test case.

The error is caused because the program is expecting a list in the second and third positions of the tree, and tries to decompose 4, leading to the error you're seeing. The specific error is caused when the less-than branch calls `(right t)` on `'(3 4 5)`, and passes the resulting `4` into insert-list:

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

The equals clause is the one that throws the error when it calls `(value 4)`, which gets you to the error you're seeing:

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

In case it helps you understand better, these are the test cases that I looked at to come to the conclusion that the code was right:

``````(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 () ())))))
``````
Share:
13,003
Author by

Updated on June 04, 2022

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.

This is my code:

``````(define (make-tree value left right) (list value left right))
(define (value tree) (car 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)))))))
``````

I keep getting the error:

``````car: contract violation
expected: pair?
given: 4
``````

Why do I keep getting this error?