Что такое определение Lisp Cons Cell?

Что такое определение Common Lisp Cons Cell? Чем отличается ячейка Cons от стандартного связанного элемента списка? В конце концов, и ячейка cons, и связанный элемент списка имеют значение и указатель на следующую ячейку или элемент ... или это понимание неверно?

 mihi22 авг. 2009 г., 23:31
каждый список (кромеnil) является cons-ячейкой, но не каждая cons-ячейка является списком (если ееcdr это не список)
 λ Jonas Gorauskas23 авг. 2009 г., 01:26
Я просто хотел уточнить, что я сравниваю выше между Common Lisp List и его Cons-ячейками и обычным Lisnked List и его Предметами, реализованными на языке C, C ++ или Java.

Ответы на вопрос(5)

Решение Вопроса

Клетки минусов в общем содержат два указателя, которые могут указывать на что угодно. Общее использование конечно, чтобы указать на "значение" с левой, а с другой против клетки (или ноль) с "право" один.

 Rainer Joswig23 авг. 2009 г., 09:24
не будет указателей на цифры, я имею в виду
 Rainer Joswig23 авг. 2009 г., 09:23
Ячейки cons также могут содержать значения напрямую, без указателей. Ячейка Ac cons, сделанная из (cons 1 2), будет иметь указатели на числа, но может хранить их напрямую (то же самое для некоторых других мелких предметов, таких как персонажи).

Я думаю, что другие ответы здесь, хотя и точны, неоткровенно об одном.

В традиционной реализации связанного списка C ++ два поля (val а такжеnextскажем)набран.next определяется как указывающий на другой узел в списке, сnull быть терминатором. Вы можете'не указывает ни на чтоно другой узел с.next

Лиспы имеют динамическую типизацию, поэтому любое из полей в ячейке «против» может бытьчто-нибудь (либо атом, либо ссылка). Вы можете реализовать связанный список с клетками cons (которые 'Весь список Lisp: цепочка минусов сnil терминатор), но вы также можете поместить произвольные значения в каждое поле, используя ячейку cons в качестве пары координат, узла дерева и т. д.

Вы даже можете объединить их; например, списокx y координаты:

;; (cons foo (cons bar nil)) == (list foo bar)    
(cons
  (cons 5 4)
  (cons (cons 9 10) nil))
=>
((5 . 4) (9 . 10))

Таким образом, cons-ячейка строго более общая, чем узел связанного списка; Это'ближе к "прикладная пара ", так сказать. Все стандартные функции обработки списка (,mapdolistи т. д.) являются просто функциями, которыепредполагать вы'переворачивать ценности вcar и еще один список в.cdr

Все это означает, что - если хочешь - вы могли бы определить спискиназад, сcar указывая на следующую клетку минусов иcdr указывая на значение! Чтобы сделать это с помощью связанного узла списка, выЯ должен был переопределить класс или структуру данных, чтобы изменить типы.

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

Причина пропуска словссылка", "указатель"и т. д. из этого определения следует признать, что это детали реализации. Если бы вы хотели, вы могли бы построитьcons из воздуха, как это делали Абельсон и Суссман:

(define (cons a b) (lambda (x) (x a b)))
(define (car x) (x (lambda (a b) a)))
(define (cdr x) (x (lambda (a b) b)))

Это определение полностью живет в Лиспемир определений и функций, а не• даже остановиться, чтобы рассмотреть, хранятся ли объекты как значения или ссылки; все же они могут служить заменой примитивных объектов (без учета изменчивости или других специальных целей).

В Лиспе cons-ячейка содержит пару значений. Если клетка минуса находится в переменнойc, затем(car c) возвращает первое значение и(cdr c) возвращает второе.

По соглашению, список состоит из минусов, гдеcar ячейки содержит значение узла иcdr содержит ссылку на следующий узел или nil (пустой список), чтобы указать конец списка. Когда примитивные функции возвращают или принимают списки, это формат, в котором представлен список.

Поэтому для спискаl(car l) дает первый элемент (значение в первой ячейке cons) и(cdr l) возвращает хвост списка (следующая cons-ячейка в списке) .A

Минус-ячейка находится ближе к узлу двоичного дерева, чем к узлу связанного списка. car и cdr возвращают двух дочерних элементов, которые могут быть nil, атомами или другими cons-ячейками.

 Chuck22 авг. 2009 г., 23:18
Чтобы подчеркнуть различие здесь, естьНе требуется, чтобы второй элемент был другой конс-ячейкой.('tofu . 1) является допустимым минусом.

Ваш ответ на вопрос