Come scrivo Push e Pop in Scheme?

Question

In questo momento l'ho fatto

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

Ma ottengo questo risultato:

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)

Che cosa sto facendo di sbagliato?Esiste un modo migliore per scrivere push in modo che l'elemento venga aggiunto alla fine e pop in modo che l'elemento venga eliminato dal primo?

Answer 1

Questo è un punto sull'uso della mutazione nel codice: non è necessario passare alle macro per questo. Per ora assumerò le operazioni dello stack: per ottenere un valore semplice che puoi passare e mutare, tutto ciò di cui hai bisogno è un wrapper nell'elenco e il resto del codice rimane lo stesso (beh, con la piccola modifica che apporta esegue correttamente le operazioni dello stack). Nello schema PLT questo è esattamente ciò che serve per le caselle:

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

Nota anche che puoi usare begin0 invece di let:

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

Per quanto riguarda la trasformazione in una coda, è possibile utilizzare uno dei metodi sopra elencati, ma fatta eccezione per l'ultima versione scritta da Jonas, le soluzioni sono molto inefficienti. Ad esempio, se fai ciò che Sev suggerisce:

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

quindi questo copia la intera coda, il che significa che un ciclo che aggiunge elementi alla tua coda copierà tutto su ogni aggiunta, generando molta spazzatura per il GC (pensa ad aggiungere un carattere alla fine di una stringa in un ciclo). Il & Quot; sconosciuto (google) & Quot; la soluzione modifica l'elenco e aggiunge un puntatore alla fine, quindi evita di generare immondizia da raccogliere, ma è ancora inefficiente.

La soluzione che Jonas ha scritto è il modo comune per farlo - mantenendo un puntatore alla fine dell'elenco. Tuttavia, se si desidera farlo nello schema PLT, sarà necessario utilizzare coppie mutabili: mcons, mcar, mcdr, set-mcar!, set-mcdr!. Le solite coppie in PLT sono immutabili da quando è uscita la versione 4.0.

Answer 2

1. Stai solo impostando ciò che è legato alla variabile lessicale a-list. Questa variabile non esiste più dopo l'uscita della funzione.

2. cons crea una nuova cella contro. Una cella contro è composta da due parti, che sono chiamate car e cdr. Un elenco è una serie di celle contro le quali ogni macchina ha un certo valore e ogni cdr punta alla rispettiva cella successiva, l'ultimo cdr che punta a zero. Quando scrivi (cons a-list x), questo crea una nuova cella contro con un riferimento a x nell'auto e push nel cdr, che molto probabilmente non è quello che vuoi.

3. pop e (cons x a-list) sono normalmente considerati operazioni simmetriche. Quando si inserisce qualcosa in un elenco (funzionando come uno stack), ci si aspetta di recuperarlo quando si apre questo elenco subito dopo. Poiché un elenco viene sempre indicato all'inizio, si desidera spingerlo facendo define-syntax.

4. IANAS (non sono uno Schemer), ma penso che il modo più semplice per ottenere quello che vuoi sia fare (set! <lst> (cons <obj> <lst>)) una macro (usando <=>) che si espanda a <=>. Altrimenti, devi passare un riferimento al tuo elenco alla funzione <=>. Valori simili per <=>. Il passaggio di un riferimento può essere effettuato avvolgendolo in un altro elenco.

Answer 3

Svante è corretto, l'uso di macro è il metodo idiomatico.

Ecco un metodo senza macro, ma sul lato negativo non è possibile utilizzare elenchi normali come code. Funziona almeno con R5RS, dovrebbe funzionare in R6RS dopo l'importazione delle librerie corrette.

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

Suppongo che tu stia cercando di implementare a coda.Questo può essere fatto in diversi modi, ma se si desidera che sia l'operazione di inserimento che quella di rimozione vengano eseguite in tempo costante, O(1), è necessario mantenere un riferimento all'operazione davanti e dietro della coda.

Puoi conservare questi riferimenti in a cella contro o come nel mio esempio, avvolto in una chiusura.

La terminologia push E pop vengono solitamente utilizzati quando si ha a che fare con gli stack, quindi li ho cambiati in enqueue E dequeue nel codice qui sotto.

(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 restituisce una procedura che racchiude lo stato della coda nelle variabili front E back.Questa procedura accetta diversi messaggi che eseguiranno le procedure della struttura dati della coda.

Questa procedura può essere utilizzata in questo modo:

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

Questa è quasi una programmazione orientata agli oggetti in Scheme!Puoi pensare a front E back come membri privati ​​di una classe di coda e i messaggi come metodi.

Le convenzioni di chiamata sono un po' arretrate ma è facile racchiudere la coda in un'API più gradevole:

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

Modificare:

COME Eli sottolinea, le coppie lo sono immutabile per impostazione predefinita nello schema PLT, il che significa che non esiste set-car! E set-cdr!.Affinché il codice funzioni nello schema PLT è necessario utilizzare coppie mutevoli Invece.Nello schema standard (R4RS, R5RS o R6RS) il codice dovrebbe funzionare senza modifiche.

Answer 5

Quello che stai facendo è modificare la " coda " solo localmente, quindi il risultato non è disponibile al di fuori dell'ambito della definizione. Ciò si ottiene perché, nello schema, tutto viene passato per valore, non per riferimento. E le strutture dello schema sono immutabili.

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

Il problema si basa sulla questione che, nello Schema, i dati e la loro manipolazione seguono la nessuna regola sugli effetti collaterali

Quindi, per una vera coda, vorremmo la mutabilità, che non abbiamo. Quindi dobbiamo cercare di aggirarlo.

Poiché tutto è passato per valore nello schema, al contrario di come riferimento, le cose rimangono locali e rimangono invariate, nessun effetto collaterale. Pertanto, ho scelto di creare una coda globale, che è un modo per aggirare questo, applicando le nostre modifiche alla struttura a livello globale, piuttosto che passare qualsiasi cosa.

In ogni caso, se hai solo bisogno di 1 coda, questo metodo funzionerà bene, anche se richiede molta memoria, poiché stai creando un nuovo oggetto ogni volta che modifichi la struttura.

Per risultati migliori, possiamo usare una macro per automatizzare la creazione della coda.

Answer 6

Le macro push e pop, che operano su liste, si trovano in molte lingue Lispy: Emacs Lisp, Gauche Scheme, Common Lisp, Chicken Scheme (nell'uovo miscmacros), Arc, ecc.

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)

Nota che funziona anche se gli elenchi sono immutabili in Racket. Un oggetto è & Quot; spuntato & Quot; dall'elenco semplicemente regolando un puntatore.