Рекурсивные типы данных в программировании: определение, примеры (списки, деревья). Динамические структуры, растущие во время выполнения. Индуктивные типы.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип данных, который ссылается на себя в своем определении.
Data type that refers to itself in its definition
В языках программирования рекурсивный тип данных (также известный как рекурсивно определенный, индуктивно определенный или индуктивный тип данных) — это тип данных для значений, которые могут содержать другие значения того же типа. Данные рекурсивных типов обычно представляются в виде ориентированных графов. Важным применением рекурсии в информатике является определение динамических структур данных, таких как списки и деревья. Рекурсивные структуры данных могут динамически увеличиваться до произвольного размера в ответ на требования времени выполнения, в отличие от статических массивов, размер которых должен быть задан во время компиляции. Иногда термин "индуктивный тип данных" используется для алгебраических типов данных, которые не обязательно являются рекурсивными.
In computer programming languages, a recursive data type (also known as a recursively defined, inductively defined or inductive data type) is a data type for values that may contain other values of the same type. Data of recursive types are usually viewed as directed graphs. An important application of recursion in computer science is in defining dynamic data structures such as Lists and Trees. Recursive data structures can dynamically grow to an arbitrarily large size in response to runtime requirements; in contrast, a static array's size requirements must be set at compile time. Sometimes the term "inductive data type" is used for algebraic data types which are not necessarily recursive.
Изорекурсивные типы
При изорекурсивных типах рекурсивный тип и его разворачивание (или раскрутка) (где обозначение указывает, что все экземпляры Z заменяются на Y в X) являются различными (и непересекающимися) типами со специальными конструкциями термов, обычно называемыми сверткой и разворачиванием, которые образуют изоморфизм между ними. Точнее: и , и эти две функции являются обратными друг другу.
With isorecursive types, the recursive type and its expansion (or unrolling) (where the notation indicates that all instances of Z are replaced with Y in X) are distinct (and disjoint) types with special term constructs, usually called roll and unroll, that form an isomorphism between them. To be precise: and , and these two are inverse functions.
Типы с равнорекурсивным действием
Согласно правилам эквирекурсивности, рекурсивный тип и его развертка считаются равными – то есть, эти два выражения типов понимаются как обозначающие один и тот же тип. Фактически, большинство теорий эквирекурсивных типов идут еще дальше и, по сути, утверждают, что любые два выражения типов с одинаковым "бесконечным разложением" эквивалентны. В результате этих правил, эквирекурсивные типы вносят значительно большую сложность в систему типов, чем изорекурсивные типы. Алгоритмические задачи, такие как проверка типов и вывод типов, также более сложны для эквирекурсивных типов. Поскольку прямое сравнение не имеет смысла для эквирекурсивных типов, их можно преобразовать в каноническую форму за время O(n log n), которую легко сравнивать. Изорекурсивные типы отражают структуру самореференциальных (или взаимно референциальных) определений типов, встречающихся в номинальных объектно-ориентированных языках программирования, а также возникают в теоретической семантике типов объектов и классов. В функциональных языках программирования изорекурсивные типы (в виде типов данных) также широко используются.
Under equirecursive rules, a recursive type and its unrolling are equal – that is, those two type expressions are understood to denote the same type. In fact, most theories of equirecursive types go further and essentially specify that any two type expressions with the same "infinite expansion" are equivalent. As a result of these rules, equirecursive types contribute significantly more complexity to a type system than isorecursive types do. Algorithmic problems such as type checking and type inference are more difficult for equirecursive types as well. Since direct comparison does not make sense on an equirecursive type, they can be converted into a canonical form in O(n log n) time, which can easily be compared. Isorecursive types capture the form of self referential (or mutually referential) type definitions seen in nominal object oriented programming languages, and also arise in type theoretic semantics of objects and classes. In functional programming languages, isorecursive types (in the guise of datatypes) are common too.