Список (абстрактный тип данных)

редактировать

Абстрактный тип данных, используемый в информатике

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

Односвязная структура списка, реализующая список из трех целочисленных элементов.

Имя list также используется для нескольких конкретных структур данных, которые могут использоваться для реализации абстрактные списки, особенно связанные списки и массивы. В некоторых контекстах, например, в программировании на Lisp, термин список может относиться конкретно к связному списку, а не к массиву. В программировании на основе классов списки обычно предоставляются как экземпляры подклассов общего класса «список» и проходят через отдельные итераторы.

Многие программирование языки обеспечивают поддержку типов данных списка и имеют специальный синтаксис и семантику для списков и операций со списками. Список часто можно создать, записав элементы последовательно, разделенные запятыми, точками с запятой и / или пробелами, в пределах пары разделителей, например круглые скобки '()', квадратные скобки '', фигурные скобки '{}' или угловые скобки '<>'. Некоторые языки могут разрешать проиндексировать или разрезать типы списков, как типы массивов, и в этом случае тип данных более точно описывается как массив.

В теории типов и функциональном программировании абстрактные списки обычно определяются индуктивно с помощью двух операций: nil, который возвращает пустой список, и cons, который добавляет элемент в начало списка.

Содержание

1 Операции
2 Реализации
3 Поддержка языков программирования
4 Приложения
5 Абстрактное определение
- 5.1 Список монада
6 См. также
7 Ссылки

Операции

Реализация структуры данных списка может предоставлять некоторые из следующих операций :

a конструктор для создания пустого списка ;
операция для проверки того, является ли список пустым;
операция для добавления объекта в список
операция для добавления объекта в список
операция для определения первого компонента (или "заголовка") списка
операция для ссылки на список, состоящий из всех компонентов списка, кроме его первого (это называется "хвостом" списка.)
оператор Для доступа к элементу по заданному индексу.

Реализации

Списки обычно реализуются либо как связанные списки (односвязные, либо двусвязные), либо как массивы, обычно переменной длины или динамических массивов.

Стандартный способ реализации списков, исходящих из языка программирования Lisp, состоит в том, чтобы каждый элемент списка содержал как свое значение, так и указатель, указывающий на расположение следующего элемента в списке. В результате получается либо связанный список, либо дерево, в зависимости от того, есть ли в списке вложенные подсписки. Некоторые более старые реализации Лиспа (например, реализация Лиспа Symbolics 3600) также поддерживали «сжатые списки» (с использованием кодирования CDR ), которые имели особое внутреннее представление (невидимое для пользователя). Списками можно управлять с помощью итерации или рекурсии. Первый часто предпочтительнее в императивных языках программирования, тогда как последний является нормой в функциональных языках.

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

Поддержка языков программирования

Некоторые языки не предлагают список структуру данных, но предлагают использование ассоциативных массивов или какой-либо таблицы для имитации списков. Например, Lua предоставляет таблицы. Хотя Lua хранит списки с числовыми индексами в виде массивов внутри, они по-прежнему отображаются как словари.

В Lisp списки являются основным типом данных и могут представлять как программный код, так и данные. В большинстве диалектов список первых трех простых чисел может быть записан как (список 2 3 5). В нескольких диалектах Лиспа, включая Scheme, список представляет собой набор пар, состоящий из значения и указателя на следующую пару (или нулевое значение), составляющих односвязный список.

Приложения

Как следует из названия, списки могут использоваться для хранения списка элементов. Однако, в отличие от традиционных массивов , списки могут расширяться и сжиматься и динамически хранятся в памяти.

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

Списки также составляют основу для других абстрактных типов данных, включая очередь, стек и их варианты.

Абстрактное определение

Тип абстрактного списка L с элементами некоторого типа E (мономорфный список) определяется следующими функциями:

nil: () → L

минусы: E × L → L

сначала: L → E

остальное: L → L

с аксиомами

сначала (минусы ( e, l)) = e

rest (cons (e, l)) = l

для любого элемента e и любого списка l. Подразумевается, что

cons (e, l) ≠ l

cons (e, l) ≠ e

cons (e 1, l 1) = cons (e 2, l 2), если e 1 = e 2 и l 1 = l 2

Обратите внимание, что first (nil ()) и rest (nil ()) не определены.

Эти аксиомы эквивалентны аксиомам абстрактного типа данных stack.

В теории типов приведенное выше определение более просто рассматривается как индуктивный тип, определенный в терминах конструкторов: nil и cons. В алгебраических терминах это может быть представлено как преобразование 1 + E × L → L. сначала и остальные затем получаются с помощью сопоставления с образцом в конструкторе cons и отдельной обработки случая nil.

Монада списка

Тип списка образует монаду со следующими функциями (с использованием E вместо L для представления мономорфных списков с элементами типа E):

return: A → A * = a ↦ cons a nil {\ displaystyle {\ text {return}} \ двоеточие A \ to A ^ {*} = a \ mapsto {\ text {cons}} \, a \, { \ text {nil}}}

{\ text {return}} \ двоеточие A \ to A ^ {*} = a \ mapsto {\ text {cons}} \, a \, {\ text {nil}}

bind: A ∗ → (A → B ∗) → B ∗ = l ↦ f ↦ {nil, если l = nil, append (fa) (связать l ′ f), если l = cons al ′ {\ Displaystyle {\ text {bind}} \ двоеточие A ^ {*} \ to (A \ to B ^ {*}) \ to B ^ {*} = l \ mapsto f \ mapsto {\ begin {cases} {\ text {nil}} {\ text {if}} \ l = {\ text {nil}} \\ {\ text {append}} \, (f \, a) \, ({\ text {bind }} \, l '\, f) {\ text {if}} \ l = {\ text {cons}} \, a \, l' \ end {cases}}}

{\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f){\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

где добавление определяется как :

добавить: A ∗ → A ∗ → A ∗ = l 1 ↦ l 2 ↦ {l 2, если l 1 = nil cons a (добавить l 1 ′ l 2), если l 1 = cons al 1 ′ {\ displaystyle {\ text {append}} \ двоеточие A ^ {*} \ to A ^ {*} \ to A ^ {*} = l_ {1} \ mapsto l_ {2} \ mapsto {\ begin {cases} l_ {2 } {\ text {if}} \ l_ {1} = {\ text {nil}} \\ {\ text {cons}} \, a \, ({\ text {append}} \, l_ {1} '\, l_ {2}) и {\ text {если} } \ l_ {1} = {\ text {cons}} \, a \, l_ {1} '\ end {cases}}}

{\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2}){\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}

В качестве альтернативы, монада может быть определена в терминах операций return, fmap и join, с:

fmap: (A → B) → (A ∗ → B ∗) = f ↦ l ↦ {nil, если l = nil cons (fa) (fmap fl ′), если l = cons al ′ {\ displaystyle {\ text {fmap}} \ двоеточие (от A \ до B) \ to (A ^ {*} \ to B ^ {*}) = f \ mapsto l \ mapsto {\ begin {cases} {\ text {nil} } {\ text {if}} \ l = {\ text {nil}} \\ {\ text {cons}} \, (f \, a) ({\ text {fmap}} f \, l ') {\ text {if}} \ l = {\ text {cons}} \, a \, l '\ end {cases}}}

{\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l'){\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

join: A ∗ ∗ → A ∗ = l ↦ {nil, если l = nil добавить a (присоединиться к l '), если l = cons al ′ {\ displaystyle {\ text {join}} \ двоеточие {A ^ {*}} ^ {*} \ to A ^ {*} = l \ mapsto { \ begin {case} {\ text {nil}} {\ text {if}} \ l = {\ text {nil}} \\ {\ text {append}} \, a \, ({\ text {join }} \, l ') {\ text {if}} \ l = {\ text {cons}} \, a \, l' \ end {cases}}}

{\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l'){\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}

Обратите внимание, что fmap, join, append и bind четко определены, поскольку они применяются к более глубоким аргументам при каждом рекурсивном вызове.

Тип списка - это аддитивная монада, где nil является монадическим нулем, а добавление - монадической суммой.

Списки образуют моноид при операции добавления. Идентификационным элементом моноида является пустой список nil. Фактически, это свободный моноид над набором элементов списка.

См. Также

Найдите list в Wiktionary, бесплатном словаре.