Как мне написать Push and Pop в схеме?

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)

Что я делаю не так? Есть ли лучший способ написать push, чтобы элемент был добавлен в конце, а pop - чтобы элемент был удален из первого?

Answer 1

Это пункт об использовании мутации в вашем коде: для этого не нужно переходить к макросам.Я пока возьмусь за операции со стеком: чтобы получить простое значение, которое вы можете передавать и изменять, все, что вам нужно, это обертка вокруг списка, а остальная часть вашего кода остается прежней (ну, с незначительным изменением, которое делаетон делает операции стека правильно).В схеме 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)))))

Что касается его превращения вочередь, вы можете использовать один из вышеперечисленных методов, но кроме последней версии, написанной Джонасом, решения очень неэффективны.Например, если вы делаете то, что предлагает Сев:

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

, то это копирует целую очередь - это означает, что цикл, который добавляет элементы в вашу очередь, будет копировать все в каждомКроме того, генерируя много мусора для GC (подумайте о добавлении символа в конец строки в цикле).Решение "unknown (google)" изменяет список и добавляет указатель на его конец, поэтому оно не создает мусор для сбора, но все равно неэффективно.

Решение, написанное Джонасом, является распространенным способом сделать это.- сохранить указатель на конец списка.Однако, если вы хотите сделать это в схеме PLT, вам нужно будет использовать изменяемые пары: mcons, mcar, mcdr, set-mcar!, set-mcdr!.Обычные пары в PLT являются неизменяемыми с момента выхода версии 4.0.

Answer 2

1. Вы просто устанавливаете, что связано с лексической переменной a-list. Эта переменная больше не существует после выхода из функции.

2. cons создает новую ячейку минусов. Минус ячейка состоит из двух частей, которые называются car и cdr. Список - это серия cons-ячеек, где каждая машина содержит некоторое значение, и каждый cdr указывает на соответствующую следующую ячейку, причем последний cdr указывает на ноль. Когда вы пишете (cons a-list x), это создает новую ячейку cons со ссылкой на a-list в машине и x в CDR, что, скорее всего, не то, что вам нужно.

3. push и pop обычно понимаются как симметричные операции. Когда вы помещаете что-то в список (функционирующий как стек), вы ожидаете получить его обратно, когда сразу же откроете этот список. Поскольку на список всегда ссылаются в его начале, вы хотите нажать туда, выполнив (cons x a-list).

4. IANAS (я не Schemer), но я думаю, что самый простой способ получить то, что вы хотите, это сделать push макросом (используя define-syntax), который расширяется до (set! <lst> (cons <obj> <lst>)). В противном случае вам нужно передать ссылку в ваш список в функцию push. Аналогично для pop. Передача ссылки может быть выполнена путем переноса в другой список.

Answer 3

Сванте правильно, использование макросов - идиоматический метод.

Вот метод без макросов, но с другой стороны вы не можете использовать обычные списки в качестве очередей. Работает как минимум с 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 4

Полагаю, вы пытаетесь реализовать очередь . Это можно сделать несколькими способами, но если вы хотите, чтобы операция вставки и удаления выполнялась в постоянное время, O (1), вы должны сохранить ссылку на спереди и сзади очередь.

Вы можете хранить эти ссылки в cons-ячейке или, как в моем примере, завернутыми в закрытие.

Терминология 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)

Это почти объектно-ориентированное программирование в Scheme! Вы можете думать о 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))

Edit:

Как указывает Eli , пары по умолчанию неизменны в схеме PLT, что означает отсутствие set-car! и set-cdr!. Чтобы код работал в схеме PLT, вы должны вместо этого использовать изменяемые пары . В стандартной схеме (R4RS, R5RS или R6RS) код должен работать без изменений.

Answer 5

Макросы push и pop, которые работают со списками, встречаются во многих языках Lispy: Emacs Lisp, Gauche Scheme, Common Lisp, Chicken Scheme (в яйце miscmacros), Arc и т.д.

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. Элемент «выталкивается» из списка, просто настраивая указатель.

Answer 6

То, что вы делаете, - это изменение «очереди» только локально, и поэтому результат недоступен за пределами области определения. Это происходит потому, что в схеме все передается по значению, а не по ссылке. И структуры 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)

Проблема заключается в том, что в Схеме данные и манипуляции с ними следуют правилу без побочных эффектов

Так что для настоящей очереди мы бы хотели изменчивости, которой у нас нет. Поэтому мы должны попытаться обойти это.

Так как все передается по схеме в схеме, в отличие от ссылки, вещи остаются локальными и остаются неизменными, без побочных эффектов. Следовательно, Я решил создать глобальную очередь, которая является способом обойти это, применяя наши изменения к структуре глобально, а не передавать что-либо внутрь.

В любом случае, если вам просто нужна 1 очередь, этот метод будет работать нормально, хотя он требует большого объема памяти, поскольку вы создаете новый объект каждый раз, когда изменяете структуру.

Для лучших результатов мы можем использовать макрос для автоматизации создания очереди.