Problem with list in Lisp

Question

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 argument 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?

Svante · Accepted Answer · 2011-01-07 14:33:02Z

2

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.

answered Jan 7, 2011 at 14:33

Svante

51.8k11 gold badges84 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vatine · Accepted Answer · 2011-01-07 13:18:26Z

1

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

answered Jan 7, 2011 at 13:18

Vatine

21.4k4 gold badges57 silver badges70 bronze badges

2 Comments

erjiang Over a year ago

Also, nil in Lisp is '() in Scheme.

Vatine Over a year ago

@erijang: Ah, I thought nil and () were the same, but nil and #f were different.

Collectives™ on Stack Overflow

Problem with list in Lisp

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related