4

今、私は持っています

(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)

私は何を間違っていますか？要素が最初から削除されるように要素が最後に追加され、ポップされるようにプッシュを書くより良い方法はありますか?

4

6 に答える 6

7

これは、コードでミューテーションを使用する場合のポイントです。そのためにマクロにジャンプする必要はありません。ここでは、スタック操作を想定します。渡して変更できる単純な値を取得するには、必要なのはリストのラッパーだけであり、コードの残りの部分は同じままです (まあ、スタック操作を適切に行います)。PLT スキームでは、これがまさにボックスの目的です。

(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))

begin0の代わりに使用できることにも注意してくださいlet。

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

それをキューに変えることに関しては、上記の方法のいずれかを使用できますが、ジョナスが書いた最後のバージョンを除いて、解決策は非常に非効率的です. たとえば、Sev が提案することを行う場合:

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

次に、これはキュー全体をコピーします-つまり、アイテムをキューに追加するループは、アイテムを追加するたびにすべてをコピーし、GC に大量のガベージを生成します (ループ内の文字列の末尾に文字を追加することを考えてください) ）。「unknown (google)」ソリューションは、リストを変更し、最後にポインターを追加するため、収集するガベージの生成を回避できますが、それでも非効率的です。

ジョナスが書いた解決策は、これを行うための一般的な方法です-リストの最後へのポインターを保持します。ただし、PLT スキームで実行する場合は、変更可能なペアを使用する必要があります: mcons、mcar、mcdr、。バージョン 4.0 が登場して以来、PLT の通常のペアは不変です。set-mcar!set-mcdr!

于 2009-06-26T10:34:28.853 に答える
5

  1. レキシカル変数にバインドされているものを設定しているだけですa-list。この変数は、関数が終了すると存在しなくなります。

  2. cons新しいコンスセルを作成します。コンスセルは と と呼ばれる 2 つの部分で構成されcarますcdr。リストは一連のコンス セルであり、各 car は何らかの値を保持し、各 cdr はそれぞれの次のセルを指し、最後の cdr は nil を指します。を記述すると、車内およびcdr 内(cons a-list x)に への参照を含む新しいコンス セルが作成されますが、これはおそらくあなたが望むものではありません。a-listx

  3. pushpop通常、対称操作として理解されます。何かをリスト (スタックとして機能) にプッシュすると、後でこのリストを直接ポップすると、それが返されることが期待されます。リストは常に先頭で参照されるため、 を実行してそこにプッシュし(cons x a-list)ます。

  4. IANAS (私はスキーマ作成者ではありません) ですが、必要なものを取得する最も簡単な方法は、 に展開されるpushマクロを ( を使用して) 作成することだと思います。それ以外の場合は、リストへの参照を関数に渡す必要があります。についても同様です。参照を渡すには、別のリストにラップします。define-syntax(set! <lst> (cons <obj> <lst>))pushpop

于 2009-06-25T00:50:42.567 に答える
3

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
于 2009-06-25T03:17:07.670 に答える
1

queueを実装しようとしていると思います。これにはいくつかの方法がありますが、挿入操作と削除操作の両方を一定時間 O(1) で実行する場合は、キューの前後への参照を保持する必要があります。

これらの参照をコンス セルに保持するか、私の例のようにクロージャでラップすることができます。

用語pushとpopは通常、スタックを扱うときに使用されるため、以下のコードではこれらをenqueueおよびに変更しました。dequeue

(define (make-queue)
  (let ((フロント '())
        （戻る '（）））
    (ラムダ (msg . obj)
      (cond ((eq? msg 'empty?) (null? フロント))
            ((eq? msg 'エンキュー!)
             (if (null? フロント)
                 （始める
                   (set! フロント obj)
                   (set! back obj))
                 （始める
                   (set-cdr! back obj)
                   (set! back obj))))
            ((eq? msg 'dequeue!)
             （始める
               (let ((val (車のフロント)))
                 (set! フロント (cdr フロント))
                 ヴァル）））
            ((eq? msg 'queue->list) フロント)))))

make-queuefront変数およびでキューの状態をラップするプロシージャを返しますback。このプロシージャは、キュー データ構造のプロシージャを実行するさまざまなメッセージを受け入れます。

この手順は次のように使用できます。

> (q (make-queue) を定義)
> (空?)
#t
> (q 'エンキュー! 4)
> (空?)
#f
> (q 'エンキュー! 9)
> (q 'queue->list)
(4 9)
> (q 'デキュー!)
4
> (q 'queue->list)
(9)

これはほぼSchemeでのオブジェクト指向プログラミングです！をキュー クラスのプライベート メンバーと見なし、メッセージをメソッドと見なすfrontことができます。back

呼び出し規則は少し古いですが、より優れた API でキューをラップするのは簡単です。

(define (enqueue! queue x)
   (キュー 'エンキュー! x))

(定義 (dequeue! キュー)
  (キュー 'デキュー!))

(定義 (empty-queue? キュー)
  (キュー「空?)」

(定義 (queue->list queue)
  (キュー 'キュー->リスト))

編集：

Eliが指摘するように、ペアはPLTスキームではデフォルトで不変です。つまり、set-car!andはありませんset-cdr!。コードが PLT スキームで機能するには、代わりに変更可能なペアを使用する必要があります 。標準スキーム (R4RS、R5RS、または R6RS) では、コードは変更されずに機能するはずです。

于 2009-06-26T04:28:07.283 に答える
0

そこで行っているのは、ローカルでのみ「キュー」を変更しているため、結果は定義のスコープ外では利用できません。これは、スキームではすべてが参照ではなく値によって渡されるためです。また、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)

この問題は、Scheme では、データとその操作が副作用なしの規則に従っていることに依存しています。

したがって、真のキューの場合、可変性が必要になりますが、これはありません。したがって、それを回避しようとする必要があります。

スキームではすべてが参照ではなく値によって渡されるため、ローカルのまま変更されず、副作用はありません。 したがって、何かを渡すのではなく、変更を構造体にグローバルに適用することで、これを回避する方法であるグローバル キューを作成することにしました。

いずれにせよ、必要なキューが 1 つだけの場合、この方法は問題なく機能しますが、構造を変更するたびに新しいオブジェクトを作成するため、メモリを大量に消費します。

より良い結果を得るために、マクロを使用してキューの作成を自動化できます。

于 2009-06-25T00:29:59.987 に答える