Проблема со списком в Lisp

Question

Я пытаюсь написать простую процедуру в Lisp, чтобы вставить элемент в двоичное дерево поиска.

Я представлял дерево в виде списка:

• первый элемент в дереве является корнем
• второй элемент является левой суб-дерево
• третий элемент является правильным суб- дерево

Это мой код:

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

Когда я вызываю процедуру следующим образом: (Insert 2 '(4 '(2 '() '()) '())), у меня проблема с «>», потому что второй аргумент не является реальным числом, но я не знаю почему.

Исключение:

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

Однако, когда я называю процедуру так: (Insert 2 (list 4 (list 2 '() '()) '())), она успешно работает.

Почему?

Я знаю, что '(1 '() '()) и (list 1 '() '()) равны, не так ли?

Answer 1

'(1 '()) эквивалентен (list 1 (list 'quote nil)). Я подозреваю, что если вы бросите «внутренние» кавычки, вы будете в порядке.

Таким образом, выражение, выражающее выражение, которое равно (list 1 '() '()), равно '(1()()).

Answer 2

Нет, quote и list не совпадают. Значение 'foo: (quote foo).

'(a b c) именно (quote (a b c)), то есть список буквального (оператор quote предотвращает список из оцениваемых). Он сопоставим с "a b c", который является строковым литералом или 5, который является номером буквами. Операции, которые изменяют литералы, имеют неопределенные эффекты, так как вы сразу узнаете, когда увидите какую-то глупость, например (setf 3 4).

(list a b c), с другой стороны, создает ("conses") новый список из значений a, b и c.

Я уверен, что если вы устраните свое замешательство в отношении quote и list, вы сможете исправить свой код.