Problem with list in Lisp

I am trying to write a simple procedure in Lisp to insert an element into binary search tree.

I represented the tree as a list:

• the first element in the tree is the root
• the second element is the left sub-tree
• the third element is the right sub-tree

This is my code:

(define Insert
  (lambda (x T) 
    (if (null? T) 
        (list x '() '())
        (if (> x (car T)) 
            (list (car T)
                  (cadr T)
                  (Insert x (list (caddr T))))
            (list (car T)
                  (Insert x (cadr T))
                  (list (caddr T)))))))

When I call the procedure like this: (Insert 2 '(4 '(2 '() '() ) '())), I get a problem with ">" because the second arg开发者_Go百科ument isn't a real number, but I don't know why.

The exception:

>: expects type <real number> as 2nd argument, given: quote; other arguments were: 2

However, when I call the procedure like this: (Insert 2 ( list 4 (list 2 '() '() ) '())), it works successfully.

Why?

I know that '(1 '() '()) and (list 1 '() '()) are equals, aren't they?

No, quote and list are not the same at all. The meaning of 'foo is (quote foo).

'(a b c) is exactly (quote (a b c)), that is, a list literal (the quote operator prevents the list from being evaluated). It is comparable to "a b c", which is a string literal or 5, which is a number literal. Operations that modify literals have undefined effects, as you may recognize immediately when you see some nonsense like (setf 3 4).

(list a b c), on the other hand, creates ("conses") a new list from the values of a, b, and c.

I am sure that if you clear up your confusion about quote and list, you will be able to correct your code.

'(1 '()) is equivalent to (list 1 (list 'quote nil)). I suspect that if you drop the "internal" quote characters, you will be fine.

So, the quoted expression that generates an expression that is equal to (list 1 '() '()) is '(1 () ()).