Комплект! в Схеме не ведет себя правильно

Question

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

;Priotiy Queue 
(define (create-queue) '()) 

(define (addq! q obj) 
    (if (or (null? q) (< obj (car q))) 
     (set! q (cons obj q)) 
     (set! q (cons (car q) (addq! q obj))))) 

(define getq! 
    (lambda (q) 
    (car q))) 

(define remq! 
    (lambda (q) 
    (set! q (cdr q)))) 

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

Answer 1

Другие ответы объяснили проблему очень хорошо. Я хочу представить вам решение, которое работает так, как вы ожидали, используя макросы. Макросы работают, преобразуя исходный код, и поэтому любые set! процедуры в макросе избегают проблемы создания промежуточной привязки.

Я также изменил некоторые формы, чтобы вернуть значение, которое более похоже на Схему.

Следующая остаются неизменными:

(define (create-queue) '()) 
(define (getq q) (car q)) 

addq! в основном без изменений, но переименован в addq_; она теперь возвращает новую очередь:

(define (addq_ q obj) 
    (if (or (null? q) (< obj (car q))) 
     (cons obj q) 
     (cons (car q) (addq_ (cdr q) obj)))) 

Для того, чтобы заставить его работать, как и ожидалось, мы создаем addq!макрос:

(define-syntax-rule (addq! q e) 
    (begin 
    (set! q (addq_ q e)) 
    q)) 

remq! просто превращается в макро:

(define-syntax-rule (remq! q) 
    (begin 
    (set! q (cdr q)) 
    q)) 

и вот как это работает:

(define qq (create-queue)) 
(addq! qq 2) 
=> '(2) 
(addq! qq 1) 
=> '(1 2) 
(addq! qq 3) 
=> '(1 2 3) 
(remq! qq) 
=> '(2 3) 
(getq qq) 
2 

и если вы посмотрите в macroexpander ракетку, это

(addq! qq 2) 
(addq! qq 1) 
(addq! qq 3) 
(remq! qq) 
(getq qq) 

трансформируется:

(begin (set! qq (addq_ qq 2)) qq) 
(begin (set! qq (addq_ qq 1)) qq) 
(begin (set! qq (addq_ qq 3)) qq) 
(begin (set! qq (cdr qq)) qq) 
(getq qq) 

Answer 2

set! q … внутри addq! определения изменяет значение внутреннего идентификатора q. Вы должны вернуть его значение, а затем захватить возвращаемое значение в вашем пользовательском коде.

Но ваша функция addq! возвращает неиспользованное значение.

Другими словами, нет необходимости использовать set!, просто верните результат вызова соответствующего cons …. Таким образом, ваша очередь равна persistent - наличие новой обновленной очереди не отменяет предыдущих копий, которые могут быть у вас.

Обычно в схеме, челка ! в имени функцию, указывает, что эта функция работает, мутирует структуру он получает в качестве аргумента (т.е. через set-car! или set-cdr!). Но для создания новой обновленной копии очереди будут аннулированы старые копии.

Если вы абсолютно уверены, что вы будете иметь только самую последнюю копию вашей очереди, вы можете не писать, как вы показываете, потому что set! изменит идентификатор внутреннего, как я уже говорил выше.

Путь вокруг это иметь структурировать и использование структурно-мутирует примитивов. Просто используйте с пометкой список для ваших очередей; то вы можете использовать set-cdr! на своем содержании - потому что передача аргумента схемы «по значению указателя» (или она «указателем значения»?) - указатель скопирован, но скопированный указатель все еще указывает на одно и то же место:

(define (make-empty-queue) (list 'queue)) 
(define (is-queue-empty? q) (null? (cdr q))) 

Теперь вам не нужно возвращать никаких значений, так же, как вы не хотели бы в первую очередь:

(define (addq! q x) 
    (if (or (is-queue-empty? q) (< x (cadr q))) 
    (set-cdr! q (cons x (cdr q))) 
    (addq! (cdr q) x))) 

Это немного «грязный», потому что последующие призываний addq! воны» t получает очередь в виде помеченного списка, с тегом QUEUE; хотя он все равно будет работать, так как ему требуется только поле cdr структуры.Но, чтобы быть хорошим, лучше сделать это внутреннее определение, инкапсулировать нечистоту:

(define (addq! q x) 
    (let g ((q q)) 
    (if (or (is-queue-empty? q) (< x (cadr q))) 
     (set-cdr! q (cons x (cdr q))) 
     (g (cdr q))))) 

Остальные процедуры изменяются соответственно:

(define (getq q)   ; no bang 
    (if (is-queue-empty? q) 
    (error " Empty Queue ") 
    (cadr q))) 

(define (remq! q) 
    (if (is-queue-empty? q) 
    (error " Empty Queue ") ; or make it some no-op like #f 
    (set-cdr! q (cddr q)))) 

Answer 3

set! синтаксическая форма изменяет объект , на который ссылается по q, но, что важно, возвращаемое значение set! не определено. Таким образом, каждый из ваших выражений set! возвращает что-то неопределенное, ваш if возвращает что-то неопределенное, а ваш addq! возвращает неопределенный.

Хотя я не обещаю, что это работает, улучшение вашего кода будет:

(define (addq q obj) 
    (if (or (null? q) (< obj (car q))) 
     (set! q (cons obj q)) 
     (set! q (cons (car q) (addq q obj)))) 
    q) ; return the newly set q 

Или, идиоматический,

(define (addq q obj) 
    (if (or (null? q) (< obj (car q))) 
     (cons obj q) 
     (cons (car q) (addq q obj)))) 

Уведомление Я переименовал вашу функцию addq, потому что это Безразлично 't изменить переданный в q; он возвращает расширенный.

Если вы хотите изменить очереди, а затем продлить его, а затем думать о переписывании create-queue как:

(define (create-queue) (cons 'QUEUE '())) 

, а затем иметь свой addq! процедуру использования set-cdr! на стоимость возвращенного выше create-queue. Как это:

(define (queue? obj) (and (pair? obj) (eq? 'QUEUE (car obj)))) 

(define (addq! q obj) 
    (assert (queue? q)) 
    (if (or (null? q) (< obj (car q))) 
     (set-cdr! q (cons obj q)) 
     (set-cdr! q (cons (car q) (addq! q obj)))) ; no guarantee this works... 
    q) 

Answer 4

set! изменение мутирует локальнейшее связывание символа. Он не меняет цель.

(define (addq! q obj) 
    (if (or (null? q) (< obj (car q))) 
     (set! q (cons obj q)) 
     (set! q (cons (car q) (addq! q obj))))) ; there is an error here 

(addq! queue 'test) 

Таким образом, в обеих ветвях эта процедура мутирует, что q есть, но это не меняет того, что queue есть. Когда q перестают существовать в конце процедуры, процедура ничего не выполнила. Два способа исправить это:

;; one that returns the new queue 
(define (addq q obj) 
    (if (or (null? q) (< obj (car q))) 
     (cons obj q) 
     (cons (car q) (addq q obj)))) ; there is still an error here! 

Что вы можете сделать, это иметь очередь в очереди. Возможно (cons 'queue '()). Вы можете использовать мутатор пары set-cdr! для изменения очереди. Голова такова, что вы всегда можете добавить к фронту, не беспокоясь о привязках к очереди (которая будет привязываться к голове).

Answer 5

мне понравилась идея списка тегов, другой способ это реализовать очередей и установить ! работа в качестве объектов с локальным состоянием

(define (create-queue) 
(let ((q '())) 
    (define (addq! obj) 
    (if (null? q) 
     (set! q (cons obj q)) 
     (let loop ((sub-q q)) 
      (cond ((< obj (car sub-q)) 
        (let ((temp (cons (car sub-q) (cdr sub-q)))) 
        (begin (set-cdr! sub-q temp) 
          (set-car! sub-q obj)))) 
       ((null? (cdr sub-q)) 
        (let ((temp (cons obj '()))) 
        (set-cdr! sub-q temp))) 
       (else (loop (cdr sub-q))))))) 
     ;;this lets you avoid setting every cons cell up to the place 
     ;;the ojbect is inserted as the overhead cost of one cons cell 
    (define getq ;;doesn't need a bang, doesn't change any data 
    (lambda() 
     (car q))) 
    (define remq! 
    (lambda() 
     (let ((temp (cdr q))) 
     (set! q temp)))) 
    (define (dispatch message) 
     (cond ((eq? message 'add) addq!) 
      ((eq? message 'get) getq) 
      ((eq? message 'rem) remq!) 
      (else "error operation not defined for queue" message))) 
    dispatch)) 

(define (addq! q-obj obj) 
((q-obj 'add) obj)) 

(define (getq q-obj) 
((q-obj 'get))) 

(define (remq! q-obj) 
((q-obj 'rem))) 

(define test-queue (create-queue)) 
;Value: test-queue 

(addq! test-queue 5) 
;Value:() 

(getq test-queue) 
;Value: 5 

(addq! test-queue 8) 

(addq! test-queue 7) 

(getq test-queue) 
;Value: 5 

(remq! test-queue) 

(getq test-queue) 
;Value: 7 

(remq! test-queue) 


(getq test-queue) 
;Value: 8 

(addq! test-queue 2) 

(getq test-queue) 
;Value: 2 

Answer 6

Схемы имеет только прохода по значению. Это означает, что когда вы передаете переменную функции, независимо от того, что делает функция, она не может вызвать присвоение (то есть set!) переменной в области вызова.

q внутри addq! - локальная переменная. Присвоение ему (set!) не влияет на внешность.