Изменить часть списка, используя set?

Question

Использование set! Я хочу иметь возможность изменять локальное состояние list переменная lst, но только его часть

Например, я хочу вставить значения во внутренний список:

((1 2) (4 5))

становится

((1 2 3) (4 5))

Я хочу иметь возможность сделать что-то вроде set! (car lst) (append (car lst) 3)

Но, похоже, это только изменяет временную переменную, генерируемую (car lst).

Единственный способ, которым я могу придумать, - это создать новый список с новыми желаемыми значениями и установить lst в качестве нового списка, но это кажется расточительным и ненужным.Есть ли лучший способ сделать это?

Answer 1

попробуйте это:

(define lst (list (list 1 2) (list 4 5)))
lst
> ((1 2) (4 5))
(set-cdr! (cdar lst) (list 3))
lst
> ((1 2 3) (4 5))

при изменении cons / списков вы должны использовать set-cdr!и set-car!

РЕДАКТИРОВАТЬ: для ракетки

использовать изменяемый список:

(require racket/mpair)
(define lst (mlist (mlist 1 2) (mlist 4 5)))
lst
> (mcons (mcons 1 (mcons 2 '())) (mcons (mcons 4 (mcons 5 '())) '()))
(set-mcdr! (mcdr (mcar lst)) (list 3))
> (mcons (mcons 1 (mcons 2 #<promise:temp2>)) (mcons (mcons 4 (mcons 5 '())) '()))
lst

Answer 2

Стандартная схема в Scheme для создания списка по частям состоит в том, чтобы добавить элементы вперед, используя cons, а не пытаться set-cdr! последней cons-ячейки в списке. В конце, когда ваш список готов, вы можете использовать reverse, чтобы получить элементы в правильном порядке. Таким образом, мутация списка не нужна сама по себе.

Итак, если вы пытаетесь создать список (1 2 3) по частям:

• Начните с пустого списка, () и cons 1 к нему. Это дает вам (1).
• Затем cons 2 к списку: (2 1)
• Затем cons 3 к списку: (3 2 1)
• Наконец, когда вы закончите построение списка, переверните его: (1 2 3)

Вы можете спросить, почему это "лучше". Это потому, что доступ к последней паре к set-cdr! является операцией O (n); со связанными списками элементы не имеют произвольного доступа, а являются линейными в зависимости от позиции элемента, к которой осуществляется доступ. Принимая во внимание, что cons всегда является O (1).

reverse является операцией O (n), но до тех пор, пока вы делаете это только в конце (когда вы готовы построить список в правильном порядке), а не вызываете ее постоянно, это не повлияет на производительность.

Answer 3

В зависимости от того, какой интерпретатор Scheme вы используете, вам может потребоваться проделать немного больше работы. Например, в Racket примитивы списка не изменяемы по умолчанию, и вам придется использовать изменяемую версию процедур:

(require scheme/mpair)
(define lst (mlist (mlist 1 2) (mlist 4 5)))
lst
(set-mcdr! (mcdr (mcar lst)) (mlist 3))
lst