Как мне добавить к alist в scheme?

Question

Добавление элемента в начало alist (ассоциативного списка) достаточно просто:

> (cons '(ding . 53) '((foo . 42) (bar . 27)))
((ding . 53) (foo . 42) (bar . 27))

Однако добавление в хвост alist немного сложнее.После некоторых экспериментов я создал это:

> (define (alist-append alist pair) `(,@alist ,pair))
> (alist-append '((foo . 42) (bar . 27)) '(ding . 53))
'((foo . 42) (bar . 27) (ding . 53))

Однако мне кажется, что это не идиоматическое решение.Итак, как это обычно делается в scheme?Или так оно и есть на самом деле?

Answer 1

Вы не добавляетесь в список "а".Ты попадаешь в список "а".

A-list - это логически набор ассоциаций.Вас не волнует порядок элементов в наборе.Все, что вас волнует, - это наличие или отсутствие определенного элемента.В случае a-списка все, о чем вы заботитесь, это о том, существует ли ассоциация для данного тега (т. Е. пары, CAR которой является указанным значением), и, учитывая эту ассоциацию, связанное значение (т. Е., в этой реализации, CDR пары).

Answer 2

Common Lisp определяет вызываемую функцию ЖЕЛУДИ именно для этой цели, где

(acons key value alist)

эквивалентно:

(cons (cons key value) alist)

Это убедительно свидетельствует о том, что простое обращение к alist является идиоматическим.Обратите внимание, что это означает две вещи:

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