Схема: постоянный доступ к концу списка?

Question

В C вы можете иметь указатель на первый и последний элемент односвязного списка, обеспечивая постоянный доступ к концу списка.Таким образом, добавление одного списка в другой может быть выполнено за постоянное время.

Насколько мне известно, схема не обеспечивает эту функциональность (а именно постоянный доступ к концу списка) по умолчанию.Чтобы было ясно, я не ищу "указатель" функциональности.Я понимаю, что это не идиоматично по схеме и (как я полагаю) ненужно.

Может ли кто-то либо 1) продемонстрировать способность предоставлять способ добавления двух списков в постоянном времени, либо 2) заверить меня, что этоуже доступно по умолчанию в схеме или в ракетке (например, скажите мне, что append на самом деле является постоянной операцией, если я ошибаюсь, считая иначе)?

РЕДАКТИРОВАТЬ: я должен сделать себя более яснымЯ пытаюсь создать проверяемую очередь.Я хочу иметь список, который я могу 1) выдвинуть на фронт в постоянное время, 2) выскочить из спины в постоянное время и 3) перебрать, используя foldr Racket или что-то подобное (правый сгиб Lisp).

Answer 1

Стандартные списки Lisp нельзя добавлять в постоянное время.

Однако, если вы создадите свой собственный тип списка, вы можете сделать это. По сути, вы можете использовать тип записи (или просто минус) - давайте назовем это «заголовком» - который содержит указатели на начало и конец списка, и обновлять его каждый раз, когда кто-то добавляет в список .

Однако имейте в виду, что если вы это сделаете, списки больше не будут структурно индуктивными. то есть более длинный список не является просто расширением более короткого списка из-за задействованного дополнительного «заголовка». Таким образом, вы теряете большую часть простоты алгоритмов Лиспа, которые включают повторение в cdr списка на каждой итерации.

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

---

ETA для отражения редактирования OP

Вы можете создать очередь, но с противоположным поведением: вы добавляете элементы сзади и извлекаете элементы спереди. Если вы готовы работать с этим, такую ​​структуру данных легко внедрить в схему . (И да, легко добавлять две такие очереди в одно и то же время.)

Racket также имеет аналогичную структуру данных очереди , но использует вместо типа cons-ячейки тип записи, потому что cons-ячейки Racket являются неизменяемыми. Вы можете преобразовать свою очередь в список, используя queue->list (со сложностью O (n)) для случаев, когда вам нужно сложить.

Answer 2

Вы хотите очередь FIFO.user448810 упоминает стандартную реализацию для чисто функциональной очереди FIFO.

Ваша обеспокоенность по поводу потери «ключевого преимущества списков Lisp» должна быть немного распакована:

• Вы можете написатькомбинаторы для пользовательских структур данных в Лиспе.Если вы реализуете тип очереди, вы можете легко написать для него сгиб, карту, фильтр и т. Д.
• Схема, однако, не хватает в области обеспечения функций полиморфной последовательности, которые могут работать с несколькими типами последовательностей.Вы часто заканчиваете тем, что (а) преобразуете свои структуры данных обратно в списки, чтобы использовать богатую библиотеку функций списков, или (б) реализуете свои собственные версии различных из этих функций для своих пользовательских типов.
• Это очень обидно, потому что списки с односвязными ссылками, хотя они чрезвычайно полезны для множества вычислений, не являются универсальной структурой данных.
• Но что хуже, так это то, что есть много Lispлюди, которые любят делать вид, что списки являются «универсальным типом данных», который можно и нужно использовать для представления любых данных.Я запрограммировал Лисп на жизнь, и, боже мой, я ненавижу код, который создают эти люди;Я называю это «болезнью программиста на Лиспе», и мне слишком часто приходилось исправлять множество n ^ 2, которые используют списки для представления наборов или словарей для использования хеш-таблиц или деревьев поиска.Не попадитесь в эту ловушку.Используйте правильные структуры данных для поставленной задачи.Вы всегда можете создавать свои собственные непрозрачные типы данных, используя типы записей и модули в Racket;вы делаете их непрозрачными, экспортируя тип, но не полевые методы доступа для типа записи (вместо этого вы экспортируете пользовательские операции вашего типа).

Answer 3

Звучит так, будто вы ищете деку, а не список. Стандартная идиома для deque состоит в том, чтобы хранить два списка, передняя половина списка в обычном порядке и задняя половина списка в обратном порядке, таким образом предоставляя доступ к обоим концам deque. Если половина списка, к которому вы хотите получить доступ, пуста, переверните другую половину и поменяйте местами значения двух половинок. Смотрите здесь для более полного объяснения и примера кода.