Как получается эквивалент упорядоченного списка

3 ответа

Эта функция используется в NVu / Kompozer / SeaMonkey Composer с небольшой настройкой для непосредственного генерирования строчных букв:

Некоторое время назад мне нужно было то же самое в SQL, поэтому я задал (и ответил) вопрос Многоосновное преобразование — использование всех комбинаций для сокращения URL.

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

Я преобразовал функцию SQL в Javascript:

Вы должны убедиться, что вы используете правильное значение при принятии мода.

1. упорядоченный список

❖ Упорядоченный список — это своего рода элемент данных в соответствии с некоторыми сопоставимыми свойствами (такими как целочисленный размер, порядок в алфавитном порядке) для определения позиции в списке
❖ «Меньший» элемент данных находится ближе к заголовку списка и к «началу».

2. Абстрактный тип данных: упорядоченный список OrderedList

❖Операции, определенные OrderedList, следующие:

OrderedList (): создать пустой упорядоченный список
add (item): добавить элемент данных в таблицу и сохранить общий порядок, этот элемент не существует
remove (item): удалить элемент данных из упорядоченного списка, этот элемент должен существовать, а упорядоченный список изменяется.
search (item): найдите элемент данных в упорядоченном списке и верните, существует ли он.
isEmpty (): указывает, пуста ли таблица.
size (): возвращает количество элементов данных в таблице.
index (item): вернуть позицию элемента данных в таблице, этот элемент должен существовать
pop (): удалить и вернуть последний элемент в упорядоченном списке, хотя бы один элемент должен существовать в списке.
pop (pos): удалить и вернуть элемент данных в указанной позиции в упорядоченном списке, эта позиция должна существовать

3. Реализация упорядоченного списка OrderedList

❖При реализации упорядоченного списка необходимо помнить, что относительное положение элементов данных зависит от "размера" сравнения между ними.
Из-за расширяемости Python следующее обсуждение элементов данных применимо не только к целым числам, но также применимо ко всем типам данных, которые определяют метод __gt__ (то есть оператор ’> ‘)
❖ Если взять в качестве примера целочисленные элементы данных, на рисунке показана форма связанного списка (17,26,31,54,77,93).

❖Это также реализуется методом связанного списка
❖Определение узла такое же
❖OrderedList также устанавливает заголовок для сохранения ссылки заголовка связанного списка.

❖Для этих методов isEmpty / size / remove он не имеет ничего общего с порядком узлов, поэтому его реализация такая же, как и UnorderedList.
❖ метод поиска / добавления необходимо изменить

3.1 Реализация упорядоченного списка: метод поиска

❖При поиске неупорядоченного списка, если элемент данных, который необходимо найти, не существует, будет выполняться поиск всего связанного списка до конца списка.
❖Для упорядоченных списков можно использовать упорядоченное расположение узлов связанных списков, чтобы сэкономить время поиска для несуществующих элементов данных.
Если элемент данных текущего узла больше, чем элемент данных для поиска, это означает, что после связанного списка больше нет элемента данных для поиска, и вы можете напрямую вернуть False

3.2 Реализация упорядоченного списка: метод добавления

❖По сравнению с неупорядоченным списком, самый большой метод изменения — это добавление, потому что метод добавления должен гарантировать, что добавленные элементы данных добавляются в соответствующую позицию, чтобы поддерживать порядок всего связанного списка
Например, в упорядоченном списке (17, 26, 54, 77, 93) добавьте элемент данных 31, нам нужно проследить связанный список, чтобы найти первый элемент данных больше 31 54. Вставить 31 перед 54.
❖Поскольку задействованная позиция вставки находится перед текущим узлом, связанный список не может получить ссылку на узел "предшественник".
❖ Аналогично методу удаления, введите предыдущую ссылку, чтобы следовать за текущим текущим узлом.
❖Как только вы обнаружите, что первый элемент данных больше 31, вам пригодится предыдущий

4. Анализ алгоритма реализации связного списка.

❖ Анализ сложности связанного списка в основном зависит от того, предполагает ли соответствующий метод обход связанного списка.

❖Для связного списка, содержащего n узлов
isEmpty — O (1), потому что ему нужно только проверить, имеет ли head значение None
размер O (n), потому что нет другого способа узнать количество узлов, кроме перехода к концу таблицы.
поиск / удаление и метод добавления упорядоченного списка — это O (n), потому что задействован обход связанного списка, а среднее количество операций по вероятности равно n / 2.
Метод добавления неупорядоченного списка — O (1), потому что его нужно только вставить в заголовок.

❖ Временная сложность списка, реализованного связным списком, отличается от типа данных встроенного списка Python в реализации некоторых из тех же методов.
❖В основном потому, что встроенный в Python тип данных списка реализован на основе последовательного хранения и оптимизирован

Arend – язык с зависимыми типами, основанный на HoTT (часть 2)

В первой части статьи про язык Arend мы рассматривали простейшие индуктивные типы, рекурсивные функции, классы и множества.

2. Сортировка списков в Arend

2.1 Упорядоченные списки в Arend

Определим тип упорядоченных списков как пару, состоящую из списка и доказательства его упорядоченности. Как мы уже говорили, в Arend зависимые пары определяются при помощи ключевого слова \Sigma . Определение типа Sorted дадим через сопоставление с образцом, вдохновившись определением из уже упомянутой статьи про упорядоченные списки.

Обратите внимание: Arend сумел автоматически вывести, что тип Sorted содержится во вселенной \Prop . Это произошло потому, что все три образца в определении Sorted являются взаимно исключающими, а конструктор consSorted имеет два параметра, оба из которых принадлежат \Prop .
Докажем какое-нибудь очевидное свойство предиката Sorted , скажем, что хвост упорядоченного списка сам является упорядоченным списком (это свойство пригодится нам в дальнейшем).

В реализации tail-sorted мы использовали сопоставление с образцом одновременно по списку xs и предикату Sorted , кроме того, мы использовали символ пропуска «_», который можно подставлять вместо неиспользуемых переменных.

Можно спросить, возможно ли в Arend доказать свойство упорядоченных списков, упомянутое в разделе 1.3 как пример факта, который нельзя доказать в Agda без аннотаций несущественности. Напомним, что данное свойство утверждает, что для доказательства равенства упорядоченных списков, определенных через зависимые пары, достаточно проверить равенство первых компонент пар.

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

Свойство SigmaPropExt доказано в модуле Paths стандартной библиотеки, там же доказываются многие другие факты из второй главы книги HoTT, в том числе свойство функциональной экстенсиональности.

Оператор .n используется в Arend для обращения к проектору сигма-типа с номером n (в нашем случае сигма-типом является SortedList A , а выражение l1.1 означает первую компоненту этого типа — выражение типа List A ).

2.2 Реализация свойства «быть перестановкой»

Попробуем теперь реализовать функцию сортировки списка на Arend. Естественно, мы хотим иметь не простую реализацию алгоритма сортировки, а реализацию вместе с доказательством некоторых свойств.

Ясно, что у этого алгоритма должно быть по крайней мере 2 свойства:
1. Результат работы алгоритма должен быть упорядоченным списком.
2. Получившийся список должен являться перестановкой исходного списка.

Попробуем для начала реализовать на Arend свойство списков «быть перестановкой». Для этого мы адаптируем для Arend определение, взятое отсюда.

Введенный нами предикат InsertSpec имеет следующий интуитивный смысл: InsertSpec xs a ys в точности означает, что список ys является результатом вставки элемента a внутрь списка xs (на любую позицию). Таким образом, InsertSpec можно воспринимать как спецификацию функции вставки.

Ясно, что тип данных Perm действительно определяет отношение «быть перестановкой»: конструктор permInsert в точности утверждает, что xs и ys являются перестановкой друг друга, если xs и ys получаются при помощи вставки одного и того же элемента a в некоторые списки xs’ и ys’ меньшей длины, уже являющиеся перестановками друг друга.

Для выбранного нами определения свойства «быть перестановкой» несложно проверить свойство симметричности.

Свойство транзитивности также выполнено для Perm , однако его проверка существенно сложнее. Так как данное свойство не играет никакой роли в реализации нашего алгоритма сортировки, мы оставляем его проверку читателю в качестве упражнения.

2.3 Изменение гомотопических уровней при сопоставлении с образцом

Попробуем теперь реализовать функцию, вставляющую элемент в упорядоченный список так, чтобы получившийся список остался упорядоченным. Начнем со следующей наивной реализации.

Конструкция \case позволяет производить сопоставление с образцом произвольного выражения ( \elim может быть использована только на самом верхнем уровне определения функции и только для ее параметров). Если попросить Arend проверить тип insert , то будет выведено следующее сообщение об ошибке.

Проблема заключается в том, что в классе LinearOrder.Dec определение trichotomy даётся при помощи оператора || , который, в свою очередь, определен при помощи пропозиционального усечения. Как уже было сказано, для типов, принадлежащих вселенной \Prop , сопоставление с образцом в Arend разрешается только в том случае, если тип результирующего выражения сам является утверждением (у функции выше результат имеет тип List O.E , а данный тип является множеством).

Можно ли как-то обойти эту проблему? Самый простой способ решения заключается в том, чтобы изменить определение свойства трихотомии. Рассмотрим следующее определение трихотомии, использующее неусеченный тип Or вместо усеченного || :

Отличается ли это определение чем-то от исходного определения trichotomy через || ? Почему вообще мы использовали пропозиционально усеченный тип, если это только усложняет нам жизнь и мешает использовать сопоставление с образцом?

Попробуем ответить для начала на первый вопрос: для строгих порядков StrictPoset разницы между trichotomy и set-trichotomy на самом деле нет совсем. Заметим, что тип set-trichotomy является утверждением. Данный факт вытекает из того, что все три альтернативы в определении трихотомии взаимно исключают друг друга благодаря аксиомам порядка, а каждый из трех типов x = y, x < y, y < x сам по себе является утверждением ( x = y является утверждением, так как при определении класса BaseSet мы потребовали, чтобы носитель E являлся множеством!).

В листинге выше absurd — обозначение для принципа ex falso quodlibet, который определяется в модуле Logic. Так как тип Empty не имеет конструкторов в определении (см. раздел 1.2), не приходится перебирать случаи и в определении absurd :

Так как теперь мы знаем, что set-trichotomy является утверждением, мы можем вывести свойство set-trichotomy из обычного свойства trichotomy разрешимых порядков. Для этого мы можем воспользоваться конструкцией \return \level , сообщающей тайпчекеру Arend, что в данном месте сопоставление с образцом является разрешенной операцией (при этом нам приходится предъявить доказательство того факта, что результат функции set-trichotomy-property является утверждением).

Попробуем теперь ответить на второй вопрос, а именно почему при формулировке свойств математических объектов предпочтительнее использовать не обычные, а пропозиционально усеченные конструкции. Рассмотрим для этого фрагмент определения нестрогих линейных порядков (полные определения Lattice и TotalOrder можно найти в модуле LinearOrder):

Попробуем пофантазировать теперь, как изменился бы смысл класса TotalOrder в том случае, если бы мы написали определение поля totality через неусеченную конструкцию Or .

В данном случае тип (x <= y) `Or` (y <= x) уже не является утверждением, т.к. в случае равных значений x и y обе альтернативы в определении badTotality могут реализовываться, а выбор левой или правой ветви при доказательстве badTotality абсолютно произволен и остаётся на усмотрение пользователя — нет никакой причины предпочесть один конструктор Or другому.

Теперь понятно, в чём заключается отличие TotalOrder от BadTotalOrder . Два упорядоченных множества O1 O2 : TotalOrder равны всегда, когда можно доказать равенство множеств O1.E, O2.E и заданных на них порядков O1.<, O2.< (это является желаемым свойством). С другой стороны, для O1 O2 : BadTotalOrder доказать равенство O1 и O2 можно только в тех случаях, когда вдобавок для всех элементов x из E имеет место равенство O1.badTotality x x и O2.badTotality x x .

Таким образом, получается, что класс BadTotalOrder интуитивно уже нужно рассматривать не как «линейно упорядоченное множество», а как «линейно упорядоченное множество вместе с выбором для каждого элемента x поля E левой или правой ветви Or в реализации badTotality x x ».

2.4 Алгоритм сортировки

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

Попробуем теперь реализовать аналог данного определения для упорядоченных списков. Мы воспользуемся специальной конструкцией \let … \in , позволяющей добавить в контекст новые локальные переменные.

Мы оставили в доказательстве незаконченный фрагмент (обозначенный выражением ) в том месте, где нужно показать, что список x :-: result упорядочен. Хотя в контексте и имеется доказательство упорядоченности списка result , нам остаётся проверить, что x не превосходит значения первого элемента списка result , что не так уж и легко следует из имеющихся в контексте посылок (чтобы увидеть все посылки в текущей цели — так мы называем реализуемую в настоящий момент ветвь вычислений — нужно запросить проверку типов у функции insert ).

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

Для единственного оставленного без доказательства фрагмента Arend выведет следующее значение контекста:

Для завершения доказательства нам придётся использовать в полную силу возможности оператора \case : мы применим сопоставление с образцом по 5 различным переменным, а так как типы одних переменных могут зависеть от значений других переменных, мы воспользуемся зависимым сопоставлением с образцом (dependent pattern matching).

Конструкция с двоеточием явно указывает, как тип одних переменных, по которым ведется сопоставление, зависит от значения других переменных (таким образом, в тип переменных xs-sorted, result-spec и result-sorted в каждом из пунктов \case вместо переменных xs’ и result будут подставлены соответствующие образцы).

Конструкция \return связывает переменные, по которым ведется сопоставление с образцом, с типом ожидаемого результата. Иными словами, в текущей цели в каждом из пунктов \case вместо переменной result будет подставлен соответствующий образец. Без этой конструкции такая замена не осуществлялась бы, и цель у всех пунктов \case совпадала бы с целью на месте самого \case -выражения.

В приведенном выше блоке кода дополнительного комментария заслуживают сложные первые аргументы конструктора consSorted в двух последних пунктах сопоставления с образцом. Чтобы разобраться, что означают оба этих выражения, заменим их на выражение и попросим тайпчекер Arend определить цели на обеих позициях.

Можно видеть, что и там, и там текущей целью является тип (x = r) || O.< x r . При этом в контексте первой цели присутствуют посылки

а в контексте второй — посылки

Интуитивно ясно: чтобы доказать первую цель, достаточно подставить в верное утверждение Or (x = y) (O.< x y) вместо переменной y переменную r , а затем перейти к пропозиционально усеченному типу || при помощи определенной в разделе 1.3 функции Or-to-|| . Чтобы доказать вторую цель, достаточно подставить в (x = x’) || O.< x x’ вместо переменной x’ переменную r .

Для формализации описанной операции подстановки выражений в стандартной библиотеке Arend существует специальная функция transport . Рассмотрим ее сигнатуру:

В нашем случае вместо переменной A нужно подставить тип O.E (его можно явно не указывать, если указаны остальные аргументы transport ), а вместо B — выражение \lam (z : O) => (x = z) || (x < z) .

Реализация алгоритма сортировки вставками вместе со спецификацией уже не вызывает особых трудностей: для того чтобы отсортировать список x :-: xs’ , мы сначала сортируем хвост списка xs’ при помощи рекурсивного вызова insertSort , а затем вставляем внутрь этого списка элемент x с сохранением порядка при помощи обращения к уже реализованной функции insert .

Мы выполнили поставленную изначально цель и реализовали сортировку списков на Arend. Весь Arend-код, приведенный в настоящем параграфе, можно скачать одним файлом отсюда.

Можно было бы спросить, как пришлось бы изменить реализацию функции insert , если бы вместо строгих порядков LinearOrder.Dec мы использовали нестрогие порядки TotalOrder ? Как мы помним, в определении функции totality использование усеченной операции || было весьма существенно, то есть это определение не эквивалентно определению, в котором вместо || используется Or .

Ответ на этот вопрос выглядит так: построить аналог insert для TotalOrder по-прежнему возможно, однако для этого нам пришлось бы доказать, что тип функции insert является утверждением (это позволило бы нам в определении insert произвести сопоставление с образцом по утверждению totality x y ).

Иными словами, нам пришлось бы доказать, что существует только один с точностью до равенства упорядоченный список, являющийся результатом вставки элемента y в упорядоченный список xs . Несложно увидеть, что это верный факт, однако его формальное доказательство уже не столь тривиально. Мы оставляем проверку этого факта в качестве упражнения для заинтересованного читателя.

3. Заключительные замечания

В настоящем введении мы познакомились с основными конструкциями языка Arend, а также научились пользоваться механизмом классов. Мы сумели реализовать простейший алгоритм вместе с доказательством его спецификации. Таким образом, мы показали, что Arend вполне пригоден для решения «житейских» задач, таких как, например, верификация программ.

Мы упомянули далеко не все возможности и особенности Arend. Например, мы почти ничего не сказали про типы с условиями, позволяющие «склеить» различные конструкторы типа при некоторых специальных значениях параметров этих конструкторов. Например, реализация типа целых чисел в Arend даётся при помощи типов с условиями следующим образом:

В данном определении говорится, что целые числа состоят из двух копий типа натуральных чисел, в которых отождествлены «положительный» и «отрицательный» нули. Такое определение гораздо более удобно, чем определение из стандартной библиотеки Coq, где «отрицательную копию» натуральных чисел приходится «сдвигать на единицу», чтобы эти копии не пересекались (намного удобнее, когда нотация neg 1 обозначает число -1, а не -2).

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

Автор статьи: Сергей Синчук, старший исследователь группы HoTT и зависимых типов в JetBrains Research.