스키마 : 목록의 끝까지의 지속적인 액세스?

Question

C에서 단일 링크 된 목록의 첫 번째 요소와 마지막 요소를 가리키는 포인터를 사용하여 목록의 끝까지 일정 시간 액세스 할 수 있습니다. 따라서 한 목록을 다른 목록에 추가하는 작업은 일정 시간 내에 수행 될 수 있습니다.

제가 알고있는 한, scheme은 기본적으로이 기능 (즉, 목록의 끝까지의 지속적인 액세스)을 제공하지 않습니다. 명확히 말하면, 나는 "포인터"기능을 찾고 있지 않다. 나는 이것이 체계에서 비 관용적이며 (필자가 생각하기에) 불필요하다고 생각합니다.

누군가가 1) 일정 시간에 두 목록을 추가 할 수있는 방법을 제공하는 능력을 보여줄 수 있습니까? 아니면 2) 이것이 스킴이나 라켓에서 기본적으로 사용 가능하다는 것을 보증 할 수 있습니까 (예 : append는 실제로 내가 틀린 생각을 잘못하면 일정한 작동)?

편집 : 내가 더 분명하게해야합니다. inspectable 대기열을 만들려고합니다. 내가 할 수있는 목록을 갖고 싶다. 1) 상수 시간에 앞쪽으로 밀고, 2) 일정한 시간에 뒤에서 튀어 나오며, 3) 라켓의 foldr 또는 이와 유사한 것을 사용한다. (Lisp 오른쪽 접기).

Answer 1

표준 Lisp 목록에는 일정 시간을 추가 할 수 없습니다.

그러나 독자적인 목록 유형을 만들면 할 수 있습니다. 기본적으로 레코드 유형 (또는 단지 단락 셀)을 사용할 수 있습니다 --- 머리글과 꼬리의 포인터를 보유하는 "헤더"를 호출하여 누군가가 목록에 추가 할 때마다 업데이트합니다 .

그러나 그렇게하면 목록이 더 이상 구조적으로 유도되지 않습니다. 즉, 더 긴 목록은 관련된 "여분의"머리글 때문에 짧은 목록의 확장이 아닙니다. 따라서 각각의 반복에서 목록의 cdr을 반복하는 Lisp 알고리즘의 단순함의 상당 부분을 잃게됩니다.

즉, 쉽게 추가 할 수 없다는 점은 재귀 알고리즘을 훨씬 쉽게 작성할 수 있다는 단점이 있습니다. 기능적인 프로그래머는 이것이 순수한 기능적 의미로 추가하면 마지막 목록을 제외하고 모든 셀을 복사해야한다는 것을 의미하기 때문에 이것이 적절한 절충이라는 데 동의 할 것입니다. 따라서 더 이상 O (1)이 아닙니다.

---

ETA는 있지만 반대 행동, 영업 이익의 편집

당신은 큐를 만들 수 있습니다 반영하기 : 당신은 뒤에 요소를 추가하고, 앞에 요소를 검색 할 수 있습니다. 당신이 그걸로 기꺼이 작업한다면, 그러한 데이터 구조는 easy to implement in Scheme입니다. (그리고 네, 일정한 시간에 이러한 대기열을 추가하는 것은 쉽습니다.)

Racket도 비슷한 queue data structure이지만 Racket cons 셀은 불변이므로 cons 셀 대신 레코드 유형을 사용합니다. 접을 필요가있는 시간은 queue->list (O (n) 복잡도)을 사용하여 대기열을 목록으로 변환 할 수 있습니다.

Answer 2

목록이 아닌 양말 (deque)을 찾는 것처럼 들립니다. 양단 큐의 표준 관용법은리스트의 앞쪽 절반을 보통 순서로, 뒤쪽 절반을 역순으로 유지하여 양 큐의 양쪽 끝을 액세스하게합니다. 액세스하려는 목록의 절반이 비어 있으면 나머지 절반을 뒤집어 두 반쪽의 의미를 바꿉니다. 더 자세한 설명과 샘플 코드는 here을 참조하십시오.

Answer 3

FIFO 대기열이 필요합니다. user448810은 순전히 기능적인 FIFO 큐에 대한 표준 구현을 언급합니다.

"리스프 목록의 주요 장점"는 손실에 대한 귀하의 관심은 약간 압축 해제 할 필요가

: 당신은 리스프에서 사용자 정의 데이터 구조에 대한 콤비를 작성할 수

• 합니다. 큐 유형을 구현하면 접기, 맵핑, 필터 등을 쉽게 작성할 수 있습니다. 그러나, 반응식은 다중 서열 유형에서 작용할 수있는 다형성 서열 기능을 제공하는 영역이 부족하다. 데이터 구조를 목록으로 다시 변환하여 목록 함수의 풍부한 라이브러리를 사용하거나 (b) 사용자 정의 유형에 대해이 함수의 다양한 버전을 구현하는 경우가 있습니다.
• 단독 연결 목록은 엄청난 양의 계산에 유용하지만 모든 데이터 구조가 아니기 때문에 이것은 매우 유감스러운 일입니다.
• 그러나 더 나쁜 것은 목록이 모든 종류의 데이터를 나타낼 수 있고 사용할 수있는 "보편적 인 데이터 유형"인 것처럼 가장하는 Lisp 사람들이 많이 있다는 것입니다. 나는 살아있는 사람들을 위해 Lisp을 프로그래밍했고, 오 세상에 나는이 사람들이 생산하는 코드를 싫어한다. 나는 그것을 "Lisp 프로그래머 병"이라고 부르며, 해시 테이블이나 검색 트리를 사용하기 위해리스트를 사용하여 집합이나 사전을 표현하는 N^2를 많이 고쳐야한다. 그 함정에 빠지지 마십시오. 작업에 적합한 데이터 구조를 사용하십시오. Racket의 레코드 유형 및 모듈을 사용하여 항상 불투명 한 데이터 유형을 직접 만들 수 있습니다. 형식을 내 보냄으로써 불투명하게 만들지 만 레코드 형식의 필드 접근자는 사용할 수 없습니다. 대신 형식의 사용자 대처 작업을 내 보냅니다.