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

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.

This is my code:

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

I keep getting the error:

car: contract violation
  expected: pair?
  given: 4

Why do I keep getting this error?

Solution

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