Добавить или удалить элемент в середине списка (Схема)

Можно ли добавлять или удалять элементы в середине связанного списка в схеме? Кажется, я не могу придумать, как сделать это с помощью car/cdr/cons, но я думаю, что должен быть такой способ.

Если у меня есть список (1 3 5 6), и мне нужно поставить 4, например, между 5 и 6, это выполнимо?


list scheme r5rs
person user16655    schedule 25.03.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Добавление элемента в заданную позицию было выполнено в предыдущем ответе. Удаление элемента в заданной позиции аналогично:

(define (delete-at k lst)
  (cond ((null? lst)
         '())
        ((zero? k)
         (cdr lst))
        (else
         (cons (car lst)
               (delete-at (sub1 k) (cdr lst))))))
person Óscar López    schedule 25.03.2015
comment
Это даст новый список или изменит существующий? - person user16655; 26.03.2015
comment
@ user16655 это (как и в случае с большинством процедур списка в схеме) вернет новый список - person Óscar López; 26.03.2015

arrow_upward
0
arrow_downward

Вот две версии:

; list-insert : value index list -> list
;   return list where the ith element is x
(define (list-insert x i xs)
  (if (= i 0)
      (cons x xs)
      (cons (first xs) (list-insert x (- i 1) (rest xs)))))

(define (list-insert/version2 x i xs)
  (define-values (before after) (split-at xs i))
  (append before (list x) after))

(list-insert/version2 'x 2 '(a b c d))
(list-insert          'x 2 '(a b c d))

Обе версии будут выделять новый список. Для больших списков это станет неэффективным.

person soegaard    schedule 25.03.2015