car: contract violation expected: pair? given: () during remove in binary search tree

Question

I don't understand how I am getting a contract violation. It seems when I create a bst it doesnt make 2 empty lists it just has ().

This is my remove method:

;Returns the binary search tree representing bst after removing x where f and g are predicates as defined in bst-contains.
    (define (bst-remove bst f g x)
      ;if empty return empty
      (cond ((empty? bst) (bst-create-empty)))
      ;else if equal then check right if right is empty then pull from left
      (cond ((g (car bst) x) (cond ((empty? (caddr bst)) (cond ((empty? (cadr bst)) (bst-create-empty))
                                                               (else (car(cadr bst)))))
                                   ;if right isnt empty then remove from left
                                   (else(bst-create (bst-max-right (caddr bst)) (cadr bst) (bst-remove (caddr bst) f g (bst-max-right (caddr bst))))))) 
                             (else (bst-create (car bst) (bst-remove (cadr bst) f g x) (bst-remove (caddr bst) f g x)))))

My bst-create and bst-create-empty:

;Returns an empty binary search tree.
(define (bst-create-empty)
  '())

;Returns a binary search tree having the specified root value, with left-subtree left and right-subtree right.
(define (bst-create root left right)
  (list root left right))

The code I give it is

(bst-remove (bst-create 5 (bst-create 6 (bst-create-empty) (bst-create-empty)) (bst-create 4 (bst-create-empty) (bst-create-empty))) < = 6)

The error i get is car: contract violation expected: pair? given: ()

Answer 1

You have got Scheme and especially cond all wrong. If you in a body of a procedure have two statements like:

(define (test lst)
  first-expression
  tail-expression)

It is obvious that the tail-expression will follow the evaluation and discarding of any result of the first-expression. Also unless first-expression has side effects it is dead code. Your cond expressions (cond ((empty? bst) (bst-create-empty))) is dead code since no matter what the outcome is it will never be a part of the result since Scheme will evaluate the second cond unconditionally. It does (car bst) which throws the error.

The correct way to have multiple returns are by one expression:

(cond 
  (test1 consequent1)
  (test2 consequent2)
  (test3 consequent3)
  (else alternative))

Needless to say all the previous tests are negative so if test3 is true, then you know that test1 and test2 both had negative results. You also know that if consequent1 is evaluated no other terms or tests gets evaluated. It stops at the first prositive.

In you specific case the code could have looked like this:

(define (bst-remove bst f g x)
  (cond ((empty? bst)
         (bst-create-empty))
        ((not (g (car bst) x))
         (bst-create (car bst) (bst-remove (cadr bst) f g x) (bst-remove (caddr bst) f g x)))
        ((not (empty? (caddr bst)))
         (bst-create (bst-max-right (caddr bst)) (cadr bst) (bst-remove (caddr bst) f g (bst-max-right (caddr bst)))))
        ((empty? (cadr bst))
         (bst-create-empty))
        (else
         (caadr bst))))

Using nested if works too, but it makes harder to read code just like your nested cond. Notice that I negated some of the tests since they only have one alternative but several tests in its consequent. By negating I could have one consequent and continue testing for the other cases in the same cond.

Answer 2

You refer to your second cond as an else if in your comment, but it's not an else-if, it's just an if. That is, you check the second condition even if the first one was true, in which case the car part of the condition causes this error.

To fix this, you should make both conditions part of a single cond, in which case it will actually act like an else if.

Answer 3

It looks like you've misunderstood cond, or possibly Scheme in general.

The result of a function application is the value of the last expression in the function's body (the only reason for having more than one is if you're doing something that has a side effect), and cond expressions are evaluated in exactly the same way as other Scheme expressions.

So the expression (cond ((empty? bst) (bst-create-empty))) does not return an empty tree, it is evaluated and produces an empty tree, and that tree is discarded.
Then evaluation continues with the next cond, which is a bad idea when the tree is empty.

A further problem is that the function should produce a tree, but (car (cadr bst)) wouldn't.

If you define a few useful accessor functions:

(define bst-value car)
(define bst-left cadr)
(define bst-right caddr)

then these lines are more obviously wrong:

(cond ((empty? (bst-left bst)) (bst-create-empty))
       (else (bst-value (bst-left bst)))))

Fixing it, it becomes (reasonably) clear that the entire expression

(cond ((empty? (bst-left bst)) (bst-create-empty))
       (else (bst-left bst))))

is equivalent to

(bst-left bst)

Now you have

(cond ((empty? (bst-right bst)) (bst-left bst))
      ( else make a tree...

But there's a lack of symmetry here; surely, if the left subtree is empty, the result should be the entire right subtree in a similar way.

So,

(cond ((empty? (bst-right bst)) (bst-left bst))
       (empty? (bst-left bst)) (bst-right bst))
       ( else make a tree...

But now we can spot another problem: even in these cases, we need to recurse into the subtrees before we're done.

I'll digress here because too many accessor repetitions and conds makes code pretty unreadable.

Using a couple of lets (and getting rid of the unused f parameter), I ended up with this:

(define (bst-remove tree g x)
  (if (empty? tree)
      (bst-create-empty)
      ;; If the tree isn't empty, we need to recurse.
      ;; This work is identical for all the cases below, so
      ;; lift it up here.
      (let ([new-left  (bst-remove (bst-left tree) g x)]
            [new-right (bst-remove (bst-right tree) g x)])
        ;; Build an appropriate tree with the new subtrees.
        (if (g (bst-value tree) x)
            (cond [(empty? new-left) new-right] ;; If either new subtree is empty,
                  [(empty? new-right) new-left] ;;  use the other.
                  ;; The complicated case. Get the new node value from the
                  ;; right subtree and remove it from there before using it.
                  [else (let ([new-value (bst-max-right new-right)])
                           (bst-create new-value
                                       new-left
                                       (bst-remove new-right g new-value)))])
            ;; The straightforward case.
            (bst-create (bst-value tree) 
                         new-left 
                         new-right)))))