제도에서 푸시와 팝을 쓰려면 어떻게해야합니까?

Question

지금은

(define (push x a-list) 
    (set! a-list (cons a-list x))) 

(define (pop a-list) 
    (let ((result (first a-list))) 
    (set! a-list (rest a-list)) 
    result)) 

을하지만이 결과를 얻을 :

Welcome to DrScheme, version 4.2 [3m]. 
Language: Module; memory limit: 256 megabytes. 
> (define my-list (list 1 2 3)) 
> (push 4 my-list) 
> my-list 
(1 2 3) 
> (pop my-list) 
1 
> my-list 
(1 2 3) 

내가 잘못하고있는 중이 야 무엇을? 엘리먼트가 끝에 추가되고 팝 (pop)되도록 엘리먼트가 처음부터 삭제되도록 푸시 (push)를 작성하는 더 좋은 방법이 있습니까?

Answer 1

이것은 코드에서 돌연변이를 사용하는 것에 대한 요점입니다. 매크로의 점프 필요가 없습니다. 이제 스택 연산을 가정 할 것입니다. 전달할 수있는 간단한 값을 얻기 위해 목록 주위에 래퍼가 필요하고 나머지 코드는 그대로 유지됩니다 (글쎄, 사소한 변화로 인해 그것은 스택 작업을 제대로 수행합니다).PLT 제도에서이 정확히 위해 무엇 상자 :

이

(define (pop a-list) 
    (begin0 (first (unbox a-list)) 
    (set-box! a-list (rest (unbox a-list))))) 

큐으로 선회에 관해서는, 당신이 중 하나를 사용할 수 있습니다 : 당신이 begin0 대신 let의 사용할 수있는 또한

(define (push x a-list) 
    (set-box! a-list (cons x (unbox a-list)))) 

(define (pop a-list) 
    (let ((result (first (unbox a-list)))) 
    (set-box! a-list (rest (unbox a-list))) 
    result)) 

주 위의 방법은 Jonas가 작성한 마지막 버전을 제외하고는 매우 비효율적입니다. 예를 들어, 당신이 할 경우 SEV는 제안 무엇 :

(set-box! queue (append (unbox queue) (list x))) 

을 다음이 복사 전체 큐 - 당신의 큐에 항목을 추가하는 루프가 많이 생성, 각 추가에 모두 복사된다는 것을 의미합니다 GC를위한 쓰레기 (루프 안에있는 문자열 끝에 문자를 추가하는 것에 대해 생각해 보라). "unknown (google)"솔루션은 목록을 수정하고 끝에 포인터를 추가하므로 수집 할 가비지 생성을 피할 수 있지만 여전히 비효율적입니다.

Jonas가 작성한 해결책은 목록의 끝을 가리키는 포인터를 유지하는 일반적인 방법입니다. 그러나 PLT Scheme에서이 작업을 수행하려면 변경 가능한 쌍 (mcons, mcar, mcdr, set-mcar!, set-mcdr!)을 사용해야합니다. 버전 4.0이 나왔기 때문에 PLT의 일반적인 쌍은 변경되지 않습니다.

는

Answer 2

로컬에서 "대기열"만 수정 중이므로 정의의 범위를 벗어난 결과를 사용할 수 없습니다. 이는 계획에서 모든 것이 참조가 아닌 가치에 의해 전달되기 때문입니다. 그리고 Scheme 구조는 변경할 수 없습니다.

(define queue '()) ;; globally set 

(define (push item) 
    (set! queue (append queue (list item)))) 

(define (pop) 
    (if (null? queue) 
     '() 
     (let ((pop (car queue))) 
     (set! queue (cdr queue)) 
     pop))) 

;; some testing 
(push 1) 
queue 
(push 2) 
queue 
(push 3) 
queue 
(pop) 
queue 
(pop) 
queue 
(pop) 

문제는, 우리가 가변성을 원하는 것, 계획에, 그것의 데이터 조작이 어떤 부작용 규칙 그래서 진정한 큐

다음에 그 문제에 의존 우리에게는없는 것입니다. 그래서 우리는 그것을 시도하고 우회해야합니다. 모든 참조에 반대 이 계획에 값 통과하기 때문에

상황이 더 부작용, 지역의 남아와 변경되지 않습니다. 따라서 글로벌 큐를 생성하기로 결정했습니다. 이는 변경 사항을 구조체에 전역으로 적용하는 것입니다.

어떤 경우에도 큐 하나만 있으면, 구조체를 수정할 때마다 새로운 객체를 생성하므로 메모리 집약적 임에도 불구하고이 메서드는 정상적으로 작동합니다.

더 나은 결과를 얻으려면 매크로를 사용하여 큐의 생성을 자동화 할 수 있습니다.

Answer 3

1. 어휘 변수 a-list에 바운드되는 내용 만 설정하면됩니다. 이 변수는 함수가 종료 된 후에 더 이상 존재하지 않습니다.

2. cons은 새로운 cons 셀을 만듭니다. 단점 셀은 두 부분으로 구성되며 car 및 cdr이라고합니다. 리스트는 각 차가 어떤 값을 가지고있는 일련의 cons 셀이며 각 cdr은 각각의 다음 셀을 가리키고, 마지막 cdr은 nil을 가리킨다. (cons a-list x)을 쓸 때, 이것은 자동차에 a-list에 대한 참조와 함께 새로운 cons 셀을 만들고, cdr에 x을 추가합니다.

3. push 및 pop은 일반적으로 대칭 연산으로 이해됩니다. 스택으로 작동하는 목록에 무언가를 푸시하면 나중에이 목록을 팝업 할 때 다시 가져올 것으로 예상됩니다. 목록은 항상 처음부터 참조되므로, (cons x a-list)을 수행하여 목록을 푸시하고자합니다. (set! <lst> (cons <obj> <lst>))로 확장

4. IANAS (나는 음모 아니다),하지만 가장 쉬운 방법은 (define-syntax 사용) push에게 매크로를 만드는 것입니다 당신이 원하는 얻을 수 있다고 생각합니다. 그렇지 않은 경우 참조을 push 함수 목록으로 전달해야합니다. pop에 대해서도 마찬가지입니다.참조를 전달하는 것은 다른 목록으로 래핑하여 수행 할 수 있습니다.

Answer 4

Svante는 매크로를 사용하는 것이 관용적 인 방법입니다.

매크로가없는 방법이지만 아래쪽에서는 일반 목록을 대기열로 사용할 수 없습니다. 적어도 R5RS와 호환되며 올바른 라이브러리를 가져온 후에 R6RS에서 작동해야합니다.

(define (push x queue) 
    (let loop ((l (car queue))) 
    (if (null? (cdr l)) 
     (set-cdr! l (list x)) 
     (loop (cdr l))))) 

(define (pop queue) 
    (let ((tmp (car (car queue)))) 
    (set-car! queue (cdr (car queue))) 
    tmp)) 

(define make-queue (lambda args (list args))) 

(define q (make-queue 1 2 3)) 

(push 4 q) 
q 
; ((1 2 3 4)) 
(pop a) 
; ((2 3 4)) 
q 

Answer 5

나는 queue을 구현하려고한다고 가정합니다. 이것은 여러 가지 방법으로 수행 할 수 있지만 삽입 및 제거 작업을 일정 시간 O (1)에 수행하려면 앞면과 뒷쪽 대기열에 대한 참조를 유지해야합니다.

cons cell에이 참조를 보관할 수 있습니다. 예를 들어 폐쇄문으로 둘러 쌀 수도 있습니다.

용어 push 및 pop 아래 코드에서 스택을 처리 할 때 일반적으로 사용되는, 그래서 나는 enqueue과 dequeue에이 변경되었습니다.

 
(define (make-queue) 
    (let ((front '()) 
     (back '())) 
    (lambda (msg . obj) 
     (cond ((eq? msg 'empty?) (null? front)) 
      ((eq? msg 'enqueue!) 
      (if (null? front) 
       (begin 
        (set! front obj) 
        (set! back obj)) 
       (begin 
        (set-cdr! back obj) 
        (set! back obj)))) 
      ((eq? msg 'dequeue!) 
      (begin 
       (let ((val (car front))) 
       (set! front (cdr front)) 
       val))) 
      ((eq? msg 'queue->list) front))))) 

make-queue

는 변수 front back 및 상기 큐의 상태를 감싸는 과정을 반환한다. 이 프로시 저는 큐 데이터 구조의 프로 시저를 수행하는 다른 메시지를 승인합니다.

이 절차는 다음과 같이 사용할 수 있습니다

 
> (define q (make-queue)) 
> (q 'empty?) 
#t 
> (q 'enqueue! 4) 
> (q 'empty?) 
#f 
> (q 'enqueue! 9) 
> (q 'queue->list) 
(4 9) 
> (q 'dequeue!) 
4 
> (q 'queue->list) 
(9) 

이 거의 계획에서 프로그래밍 객체 지향한다! front과 back을 큐 클래스의 전용 멤버로, 메시지를 메소드로 생각할 수 있습니다.

호출 규칙

은 약간 뒤로이지만 더 좋은 API에서 큐를 포장하기 쉽습니다 :

 
(define (enqueue! queue x) 
    (queue 'enqueue! x)) 

(define (dequeue! queue) 
    (queue 'dequeue!)) 

(define (empty-queue? queue) 
    (queue 'empty?)) 

(define (queue->list queue) 
    (queue 'queue->list)) 

편집 :

Eli로 포인트를 밖으로, 쌍에서 기본적으로 immutable이다 PLT Scheme은 set-car! 및 set-cdr!이 없음을 의미합니다. 코드가 PLT 체계에서 작동하려면 mutable pairs을 대신 사용해야합니다. 표준 체계 (R4RS, R5RS 또는 R6RS)에서 코드는 수정되지 않고 작동해야합니다.

Answer 6

목록에서 작동 푸시 팝 매크로, 많은 Lisp 다운 언어에 있습니다 등 이맥스 리스프, 쉬 제도, 커먼 리스프, 닭 계획합니다 (miscmacros 달걀), 아크,

Welcome to Racket v6.1.1. 
> (define-syntax pop! 
    (syntax-rules() 
    [(pop! xs) 
    (begin0 (car xs) (set! xs (cdr xs)))])) 
> (define-syntax push! 
    (syntax-rules() 
    [(push! item xs) 
    (set! xs (cons item xs))])) 
> (define xs '(3 4 5 6)) 
> (define ys xs) 
> (pop! xs) 
3 
> (pop! xs) 
4 
> (push! 9000 xs) 
> xs 
'(9000 5 6) 
> ys ;; Note that this is unchanged. 
'(3 4 5 6) 

목록이 Racket에 불변 인 경우에도이 기능이 작동합니다. 포인터를 조정하면 항목이 목록에서 "팝"됩니다.