Разные правила для аргументов против?

Question

Я новичок в языке Racket и столкнулся с проблемой.Сейчас я пытаюсь реализовать бинарное дерево поиска, используя cons (список).

Это простой BST, который я пытался сделать:

Для этого BST, если я преобразую это в список Racket, это может быть одной из возможностей: '(6, (4, (), ()), (7, (), ())

Чтобы создать этот формат списка, я использовал этот код:

(define x3 (cons 6 (cons (cons 4 (cons null (cons null null)))
                         (cons 7 (cons null (cons null null)))

И для этого кода результат ниже:

'(6 (4 () ()) 7 () ())

Как видите, это не то, что я хотелВторой дочерний узел 7 () () не находится в скобках, что означает, что он не существует в виде списка. Он действует как отдельные 3 элемента, а не как один список. Поэтому я немного изменил:

(define x2 (cons 6 (cons (cons (cons 4 (cons null (cons null null))) null)
                         (cons (cons 7 (cons null (cons null null))) null)
                   )
           )
)

И для этого 2-го кода результат будет следующим:

'(6 ((4 () ())) (7 () ()))

И это тоже не то, что я хотел. Первый дочерний узел ((4 () ())) теперь находится внутри и внутри списка. Итак, я сделал последнюю попытку, и код выглядит так:

(define x3 (cons 6 (cons (cons 4 (cons null (cons null null)))
                         (cons (cons 7 (cons null (cons null null))) null)
                   )
           )
)

И результат выглядит так:

'(6 (4 () ()) (7 () ()))

Теперь это работает! Вопрос в том, почему эти тонкиегс случится?Я вроде понял, что правило отличается между последним элементом списка и другим, когда используются cons, но в конце концов, разве это не один и тот же вид списка?

Answer 1

Прежде всего:

cons создает на самом деле ячейку, ячейку минуса.Вы можете добавлять, используя cons несколько сотен cons-ячеек друг к другу.

(cons 'a 'b) ;; (a . b)
(cons 'c (cons 'a 'b)) ;; (c . (a . b)) 

В обозначении lisp написано: '.('is' ', поэтому последний пример упрощается до:

(c a . b)

Что такое список? Такие cons-ячейки или цепочка cons-ячеек, где последним элементом является'. () '. В этом случае выразрешено делать его невидимым.

(cons 'c (cons 'a null)) ;; or 
(cons 'c (cons 'a 'null)) ;; or
(cons 'c (cons 'a '()))   ;; which are the same!
;; in common lisp even (cons 'c (cons 'a ())) in addition

Таким образом, упрощается до:

(c a) ;; actually (c . (a . null))

Эти правила упрощения синтаксиса и тот факт, что cons принимает только точные 2 аргумента, но вам нужно 3 слота длядвоичное дерево делает сложные конструкции более сложными, чем кажется на первый взгляд.

Ваш BST должен быть выражен в виде списков:

(list 6 (list 4 null null) (list 7 null null))

, который уже очень сложно выразитьтолько с ручными конусами ... (как объяснено на ассембамару)

Как вы видите, list - это абстракция над вложением конусов с самой внутренней конс-ячейкой, равной нулю, и более приспособленной кправила синтаксиса упрощения. Таким образом, гораздо более дружественный к мозгу.

Но более элегантно, вы должны использовать структуры (как объяснено здесь https://learningtogetolder.wordpress.com/2013/08/14/creating-a-binary-search-tree-in-racket/), определяя, что каждый узел ожидает значениеи левый и правый узел.Таким образом, строительные ошибки становятся невозможными.

Answer 2

При написании глубокого списка списков с использованием cons может быть очень легко потерять отслеживание того, где начинается внутренний список, или где он заканчивается, и т. Д. Поэтому, если вы пишете длинный список вручную,может быть проще просто использовать list:

(list 6 (list 4 null null) (list 7 null null))

В противном случае вы также можете легко создать свой список cons, написав его изнутри.Например, в вашем BST есть два конечных узла с одним корневым родительским узлом.Таким образом, вы можете начать с конечных узлов:

(define left   (cons 4 (cons null (cons null null))))
(define right  (cons 7 (cons null (cons null null))))

, тогда BST становится:

(cons 6
      (cons left
            (cons right null)))

, что эквивалентно:

(cons 6
      (cons (cons 4 (cons null (cons null null)))
            (cons (cons 7 (cons null (cons null null))) null)))