Lisp Cons 셀의 정의는 무엇입니까?

Question

Common Lisp Cons Cell의 정의는 정확히 무엇입니까? 단점 셀은 표준 연결된 목록 항목과 다른 점은 무엇입니까? 결국, 단락 셀과 링크 된 목록 항목에는 값과 다음 셀 또는 항목에 대한 포인터가 있습니다 ... 또는이 이해가 잘못 되었습니까?

Answer 1

일반적으로 단락 셀은 무엇이든 가리킬 수있는 두 개의 포인터를 가지고 있습니다. 물론 일반적인 사용법은 왼쪽 값으로 "값"을 가리키고 "오른쪽"값으로 다른 Cons 셀 (또는 없음)을 가리키는 것입니다.

Answer 2

cons 셀은 연결된리스트 노드보다 이진 트리 노드에 더 가깝습니다. car와 cdr은 nil, atoms 또는 다른 cons 셀 일 수있는 두 개의 자식을 반환합니다.

Answer 3

Lisp에서 단점 셀은 한 쌍의 값을 보유합니다. 조건부 셀이 변수 c에 있으면 (car c)이 첫 번째 값을 반환하고 (cdr c)이 두 번째 값을 반환합니다.

규칙에 따라 목록은 셀의 car에 노드 값이 들어 있고 cdr에는 다음 노드에 대한 참조가 들어있는 조건부 셀 또는 목록의 끝을 나타내는 nil (빈 목록)으로 구성됩니다. 기본 함수가 목록을 반환하거나 수락하면이 형식이 목록이 표시됩니다.

따라서, 목록 l 들어 (car l) 첫번째 요소 (제 반대 셀의 값)과 (cdr l) 복귀리스트의 테일 (목록의 다음 반대 세포)를 제공한다.

Answer 4

다른 답변은 정확하지만 한 가지는 분명하지 않다고 생각합니다. 기존의 C++ 링크리스트의 구현에서

, 두 필드 ( val 및 next는 말) 가을 입력합니다. next은 목록의 다른 노드를 가리키는 것으로 정의되며 null은 종결자가됩니다. 을 가리킬 수는 없지만 다른 노드는 next입니다.

Lisps는 동적으로 입력되므로 상영 셀의 필드 중 하나는 입니다. (원자 또는 참조) 일 수 있습니다. 당신은 cons 셀 (모든 Lisp리스트는 : nil 터미네이터를 가진 cons 셀 체인)을 사용하여 링크 된리스트를 구현할 수 있습니다. 그러나 각 셀에 좌표 셀, 좌표 쌍, 트리를 사용하여 임의의 값을 넣을 수도 있습니다 노드 등

이러한 것들을 결합 할 수도 있습니다. 예컨대, xy의 목록 좌표

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

단점 셀이 엄격하므로, 링크리스트 노드보다 더 일반적이며; 말하자면 "적용된 쌍"에 더 가깝습니다. 모든 표준 목록 처리 함수 (map, dolist 등)는 이이라고 가정하고 값을 car에 넣고 다른 목록을 cdr에 넣는 단순한 함수입니다.

이 모든 것을 의미한다 - 당신이 원한다면 - 당신이 값을 가리키는 다음 단점 세포를 가리키는 car 및 cdr으로, 뒤쪽으로 나열을 를 정의 할 수 있습니다! 링크드리스트 노드를 사용하려면 클래스 또는 데이터 구조를 재정 의하여 유형을 변경해야합니다.

Answer 5

cons 셀은 cons, car 및 cdr으로 구성된 계약서의 1/3이며, 나머지는 언급 한대로 쌍으로 동작해야합니다.

"reference", "pointer"등의 단어를이 정의에서 제외하는 이유는 이것이 구현 세부 사항임을 인식하기 위해서입니다. 당신은, 당신은 아벨로, 허공 밖으로 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))) 

이 정의는 정의와 기능의 리스프의 세계 안에 완전히 살고, 심지어 여부를 고려 멈추지 않는다 객체는 값 또는 참조로 저장됩니다. 그러나 이것들은 원시 객체에 대한 드롭 인 대체 (mutability 또는 다른 특수 용도를 고려하지 않음) 역할을 할 수 있습니다.