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

Question

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

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

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

Это мой код:

(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

Нет, quote и list - это не одно и то же. Значение 'foo равно (quote foo).

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

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

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

Answer 2

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

Итак, выражение в кавычках, которое генерирует выражение, равное (list 1 '() '()), равно '(1 () ()).